Самый дешевый обход стоимости на полном графике

Question

Мне было интересно, есть ли алгоритм, который: учитывая полностью связанный граф из n-узлов (с разными весами) ... даст мне самый дешевый цикл для перехода от узла A (начального узла) ко всем остальным узлами вернуться к узлу A?Есть ли способ изменить алгоритм, такой как Primm, для достижения этой цели?

Спасибо за вашу помощь

РЕДАКТИРОВАТЬ: я забыл упомянуть, что я имею дело с неориентированным графом, так чтовыходной градус для каждой вершины.

Answer 1

Вы можете попробовать итерационный алгоритм поиска *1001*. Это всегда оптимально. Вам нужно определить эвристику, и это будет зависеть от проблемы, которую вы пытаетесь решить.

Answer 2

Не должно быть никакого такого пути.Он существует тогда и только тогда, когда степень каждого узла равна его степени.

То, что вы хотите, это самый дешевый путь Эйлера.Проблема ее поиска называется Проблема коммивояжера .Не существует и не может быть быстрого алгоритма для его решения.

Редактировать : Вторая мысль: проблема коммивояжера ищет поиск, который посещает каждый узел ровно один раз.Вы просите тур, который посещает каждый узел хотя бы один раз.Таким образом, ваша проблема может быть просто в P. Я в этом сомневаюсь.

Answer 3

Разве вы не можете изменить Dijkstra, чтобы найти вам кратчайший путь ко всем остальным узлам, а затем, когда вы его нашли, кратчайший путь обратно к A?