Какой алгоритм использовать для поиска кратчайшего пути в ненаправленном графе через все вершины?

Question

[Paul Gubanov]

Всем, привет!

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

Спасибо!

Comments

[SeptiM]

А сколько у вас вершин в графе? Нужен точный ответ или разрешается погрешность?

[Paul Gubanov]

SeptiM: приближенный результат тоже подойдёт, вершин может быть до 100

Answer 1

[Sergej]

Вам 100% требует алгоритм Гамильтоновых путей.

Сам завершил его не так давно, писал на PHP.
Расчет происходит при кол-ве вершин от 500 до 1000.
В данном случае у меня используются координаты переведенные в радианы и разложенные в матреце смежности.
Ну а далее уже этот алгоритм.

Comments

[Paul Gubanov]

Похоже что Вы правы, спасибо! И... не поделитесь реализацией, пожалуйста, на том же PHP? Мне хоть пример будет...

[Sergej]

gubanovpa: Вот что, что, а делиться точно не буду.
Вы уж простите меня, но я горбатился оч. много времени над реализацией этого алгоритма и я еще под договором о неразглашении =)

[Sergej]

Но впринципе там нее чего сложного.
Просто надо понять что в формулах написанно.
Сначала вам надо перевести координаты в радианы.
RAD(1,0)=SQRT((x1 -x0)**2+(y1 - y0)**2)
Затем построить матрицу смежности.
На выходе вы получите таблицу графов.
Вам надо будет найти в этой таблице в столбиках 2 значения. Одно минимальное другое максимальное.
Это будут 2 самых удаленных точки друг от друга.
Ну а дальше самый гемор, алгоритм =)

[Sergej]

Sayber: Т.е. вы получите стартовую и финальную точку, а алгоритмом уже постоете их по кратчайшему пути.
Если будут вопросы, постараюсь ответить.

[Paul Gubanov]

Sayber: Я понимаю, спасибо в любом случае!

[Mrrl]

Sayber: Это правильно. Если алгоритм действительно работает, то он тянет не только на докторскую диссертацию, но и на какую-нибудь премию. Всё-таки, NP-полная задача :)

[Paul Gubanov]

Mrrl: ну я ж не отказываюсь )

[Sergej]

Mrrl: Алгоритм работает.
Из БД для X городa (их может быть 5) отбирается 500-1000 POI, различные параметры для расчетов (скорость, время и т.д.).
Далее алгорим смотрит, сколько человек может осмотреть POI в день в каждом городе.
Затем то что я писал выше и на выходе мы получаем карты для N городов, в каждом городе для Nd дня есть готовые маршруты по кратчайшему пути.
Там еще куча всего, но это основа.

[Sergej]

Mrrl: Сосбтвенно на хабре будет пост в декабре по сайту и этому алгориму =)
Вот тогда можно будет увидеть расписанный алгоритм в мельчайших подробностях.

Answer 2

[Артур Нуруллин]

A* продолжение алгоритма дейкстры, но с эвристикой

Answer 3

[Mrrl]

Гамильтонов путь тут ни при чём - ведь нет запрета проходить одну вершину дважды? Но это в чистом виде задача коммивояжера. Тоже входит в класс NP. Точное решение будет слишком долгим, надо искать приближённые.

Comments

[Paul Gubanov]

Не, как раз каждая вершина только один раз приходится )

[Mrrl]

gubanovpa: В условии этого не было сказано... Ну, тогда ещё сложнее. В любом случае, либо эвристика, либо решение динамическим программированием за экспоненциальное время и память (с шансами решить до 30 вершин)

[Евгений Бучинский]

Paul Gubanov, Интересно как он найдет Гамильтонов путь от a до c в графе ab, bc, bd?

Answer 4

[Vlad_Fedorenko]

Под ваше описание подходит алгоритм Флойда-Уоршелла. Они ищет кратчайшие пути из всех вершин во вск. Алгоритм имеет очень высокую сложность - O(n^3)

Comments

[Paul Gubanov]

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

Answer 5

[SeptiM]

Теория говорит, что точных алгоритмов быстрее 2^n не известно, а приближенные с ошибкой 229/228 не существуют, пока P != NP.

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

Есть простенькие приближенные эвристики. Например, отсортируем все ребра графа и будем их пробовать вставлять в наш путь в порядке возрастания веса. Пишут, что такое дает на практике ошибку по 15-20%.

Comments

[Артур Нуруллин]

Можно попробовать генетические алгоритмы, читал на хабре - habrahabr.ru/post/191596