Алгоритм нахождения линейного пути минимального веса в графе, который соединяет все вершины ровно один раз

Question

Учитывая взвешенный неориентированный граф с n вершинами, я сталкиваюсь с проблемой нахождения пути минимального веса, который соединяет каждую из вершин в линии.Сначала я думал, что это проблема поиска минимального остовного дерева, но это не так.В случае связующего дерева в вершине могут быть ветви или степень может быть больше двух.Что мне нужно найти, так это линейный путь, т.е. все вершины, кроме конечных, имеют ровно две степени.Начальная и конечная вершины могут быть любыми из n вершин.

Мой подход был жадным, т. Е.

first chose any vertex, maintain a sum 
    check all its neighbors such that the cost of reaching it is 
    least among all the neighbors
    mark this neighbor as visited
    add the cost to sum
repeat the procedure above until all the points have been visited.

Мне придется сделать это для всех вершин в качестве начальной точки.Я не уверен, что этот алгоритм правильный, а также его сложность высока.Какой должен быть лучший подход к этой проблеме?

Answer 1

Известно, что эта задача является NP-трудной из-за сокращения от задачи о гамильтоновом пути , поскольку, если вы задаете вес всех ребер 1 и спрашиваете, существует ли линейный путьвеса не более п?тогда ответ «да» точно, если граф содержит гамильтонов путь.В результате вы вряд ли найдете алгоритм, который работает лучше, чем чисто грубая сила, поскольку, если P = NP, нет решений за полиномиальное время.

Извините, что попал на ваш парад, и надеюсь, что это поможет!

Answer 2

Хотя я думаю, что @templatetypedef верен, и это действительно является примером проблемы Гамильтониана, вы, вероятно, получите лучшие результаты, если поиск в Google будет для задачи коммивояжера - он достаточно близок, чтобы большинство (все?) Эвристик TSP работалии для вас (единственное отличие состоит в том, что TSP обычно описывается как добавление пути от конца к началу, поэтому он образует «кольцо», а не просто линию).TSP также обычно предполагает полный граф (то есть каждый узел соединяется с любым другим);если ваш график неполон, вы все равно можете использовать обычные алгоритмы, добавив бесконечную связь между любыми неподключенными узлами.

Жадный подход, который вы дали, обычно известен как эвристика "ближайшего соседа".,Это первый подход, который встречается почти со всеми.Его неоптимальные решения известны уже более века.К сожалению, все, что выполняется в разумные сроки, также будет иметь, по крайней мере, возможность получения неоптимальных решений (по крайней мере, при отсутствии ограничений на проблему).A *, вероятно, является наиболее распространенным алгоритмом для получения разумных (только слегка неоптимальных) результатов за разумное время.