Нахождение наименьшего поддерева

Question

Учитывая график из n узлов, которые все связаны на координатной плоскости, каков наилучший способ найти поддерево минимального расстояния, которое содержит m узлов?

Единственное решение, которое я нашел для этой проблемы, состоит в том, чтобы сгенерировать все комбинации узлов для соединения и попытаться соединить эти узлы с помощью алгоритма Крускала или Прима, игнорируя остальные, затем сравнить все созданные деревья и найти наименьшее , но это не совсем эффективно, когда дело доходит до больших деревьев.

Есть ли более быстрый и эффективный алгоритм / метод?

Answer 1

Вы спрашиваете о проблеме K-минимального связующего дерева (k-MST) , которая, как известно, является NP-полной. Так что вы не добьетесь большего успеха, чем ваш текущий алгоритм.

Однако в комментариях вы говорите, что ваш график генерируется из координатной плоскости, поэтому я могу только предположить, что у вас есть некоторая геометрическая информация об узлах в графике. В сборнике статей *1005* WWW упоминается, что вы можете использовать схему аппроксимации полиномиального времени для евклидова k-MST. Этот документ описывает один:

Арора, Санжеев. (1996), Полиномиальное время аппроксимационная схема для евклидова TSP и другие геометрические проблемы , В Слушания 37-ой Анны. IEEE Symp. по основам компьютера Наука , стр. 2-11.

Там прямо упоминается k-MST, так что я думаю, что вы можете попробовать этот алгоритм, если вам действительно нужна большая скорость.