Реализация любого алгоритма задачи о гамильтониане

Question

Вот моя проблема: у меня есть массив точек, точки имеют три свойства: координаты "x" и "y" и порядковый номер "n". «X» и «y» определены для всех точек, «n» - нет. Вы можете получить к ним доступ и написать вызывающие точки [i] -> x, points [i] -> y, points [i] -> n. т.е.:

points[i]->n = var
var = points[i]->n

Так что заголовок, возможно, испортил сюрприз, но я ищу возможную реализацию решения задачи о гамильтоновом пути: мне нужно установить число «n» для каждой точки, чтобы последовательность была кратчайший путь (не цикл, ребра должны быть непересекающимися) , который проходит ровно один раз через каждую точку. Я искал решение и нашел Алгоритм Беллмана Форда , но я думаю, что он не работает, так как проблема не указывает, что он должен пройти через все пункты, это правильно?

Если это так, есть ли у кого-то другой алгоритм и реализация? Если алгоритм Беллмана Форда работает, как бы я его реализовал?

Большое спасибо,

Julien

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

Редактировать : Вот изображение: Моя задача о гамильтоновом пути http://www.stoeffler.cc/hpp.png

Answer 1

Это называется Евклидовый коммивояжёр (в 2-х измерениях) и также NP-Complete, как TSP.

Другие ответы неточны , так как они делают противоположное: свести вашу проблему к гамильтонианскому пути, в то время как это должно быть наоборот, чтобы показать NP-Полноту. Извините, что говорю это, но, похоже, это довольно распространенная проблема на этом сайте.

Можно сказать, что это принципиально отличается от обычного TSP в следующем смысле:

Если P! = NP,

• Не существует PTAS для TSP (фактически также для метрической TSP, где расстояния удовлетворяют неравенству треугольника).

• Существует PTAS для евклидовых TSP. Посмотрите эту статью Ароры, в которой приводится алгоритм приближения 1 + 1 / c, а время выполнения равно O (n (logn) ^ O (c)): Схемы аппроксимации полиномиального времени для евклидова TSP и другие геометрические задачи , Обратите внимание, что евклидово TSP - это специальный случай метрического TSP, и, тем не менее, он отличается в этом отношении.

Существуют другие алгоритмы, которые гарантируют 2-аппроксимацию (используя минимальные остовные деревья) и 3/2-аппроксимацию и могут быть проще. В документе Арора упоминается об этом, и вы должны быть в состоянии отследить, используя ссылки в документе Арора.

Answer 2

Алгоритм Беллмана-Форда часто используется для решения задач кратчайшего пути из одного источника.

Кратчайшая задача о гамильтоновом пути относится к классу задач, известных как NP-hard. Это означает, что вам нужно попробовать все перестановки, чтобы гарантировать поиск кратчайшего пути. Этот подход практичен только для небольших проблем в течение нормальной человеческой жизни.

Вы можете использовать алгоритм Беллмана-Форда для создания набора кратчайших путей из одного источника для каждого узла, чтобы помочь вам решить проблему, но вы можете найти алгоритм Флойда-Варшалла предпочтительным. Floyd-Warshall даст вам кратчайший путь от каждого узла в графе до каждого из других узлов. Это алгоритм O (N ^ 3) с требованиями к памяти O (N ^ 2).

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

У меня был некоторый успех с Имитацией отжига и Табу Поиск. Был также довольно интересный подход, основанный на следах муравьев, который был опубликован примерно в прошлый раз, когда мне пришлось решать этот тип проблемы.

Удачи.

Answer 3

Гамильтонова задача о пути NP-полная , поэтому очевидно, что вы не можете найти решение с использованием полиномиального алгоритма Беллмана-Форда.

Для решения задачи о гамильтоновом пути вы можете использовать следующие шаги:

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

• Затем преобразуйте задачу о гамильтоновом цикле в Задачу коммивояжера , создав полный график и присвоив вес = 0 ребрам, присутствующим в предыдущий график и вес = 1 до остальных ребер.

• Наконец, решите TSP, используя известный алгоритм (например, динамическое программирование).

Редактировать : Я только что понял, что ты ищешь кратчайший путь. С учетом вышесказанного вы можете ответить только в том случае, если у графа есть гамильтонов путь (и, возможно, он найден).