Кратчайший путь в полном взвешенном неориентированном графе с известным начальным узлом и посещением всех узлов без возврата к начальному узлу

Question

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

Я просмотрел проблему TSP и кратчайший гамильтонов путь, но не смог найти точный ответ на мою проблему.

Итак, как именно эта проблема называется или какой это вариант кратчайшего пути?

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

Каждый край представляет расстояние между двумя местоположениями для примерного края AB = 5, AC = 11 ......

Моя цель - начать с узла A и найти кратчайший путь, который охватывает все узлы (кратчайший возможный путь), а конечная точка может быть любой, кроме A. Например, этот путь заканчивается на E:

Answer 1

Это небольшое изменение в особом случае Проблема пути коммивояжера . В задаче о путях коммивояжера вам дается неориентированный граф, функция затрат по краям и две вершины s и t. Проблема состоит в том, чтобы найти Гамильтонов путь (то есть путь, который посещает каждую вершину ровно один раз) от s до t.

Ваша проблема - это особый случай, когда входной граф - это клика , а конечная вершина t является дополнительной фиктивной вершиной, соединенной со всеми остальными вершинами ребром с нулевой стоимостью. Очевидно, что решение задачи о пути пути коммивояжера для графа (с дополнительной фиктивной вершиной t) побуждает к решению вашей проблемы, получаемой простым игнорированием последнего дополнительного шага к месту назначения t.

К сожалению, точно так же, как и знаменитая задача коммивояжера , задача о пути коммивояжера не только NP-сложная, но и NP-трудная для приближения с точностью до любого постоянного фактора. Однако, поскольку ваши затраты представляют собой расстояния, возможно, вы могли бы предположить, что функция стоимости удовлетворяет Неравенство треугольника ?

Если функция стоимости удовлетворяет неравенству треугольника, то существует недавняя 1,5-аппроксимационный алгоритм . Если этот недавний алгоритм является избыточным, вы можете реализовать один из двух более простых алгоритмов, которые хорошо описаны в лекционных заметках профессором Райаном О'Доннеллом из CMU, и согласиться либо на 2-приближение, либо на 5 / 3-приближение.