@felopil
Python Software Engineer

Как найти кратчайший путь по графу с waypoint-ми?

У меня есть к примеру граф с 5 точками, которые между собой все связаны. Мне нужно найти кратчайший путь, который обойдет каждую точку единожды. Конечная точка не имеет значения.
  • Вопрос задан
  • 67 просмотров
Пригласить эксперта
Ответы на вопрос 2
@rPman
Простейшие комбинаторные алгоритмы.

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

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

Если путей нет бегунок удаляется.

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

p.s. можно по хитрому реализовать хранение пути в бегунке, чтобы оптимизировать затраты на n*логарифм от размера лабиринта, вместо квадрата.
Ответ написан
wataru
@wataru
Разработчик на С++, экс-олимпиадник.
У вас задача коммивояжера с небольшим изменением - нужен не цикл, а путь начинающийся в заданной вершине и граф у вас полный.

Тут нет простого и быстрого решения задачи. Есть полный перебор: перебирайте все перестановки (из n-1 вершины) и считайте длину пути в таком порядке. Перебор работает очень медленно (O(n*n!)) и неприменим при больших n. Если у вас, скажем, 20 вершин - вы уже ответа не дождетесь. Для 5, как в примере будет работать моментально.

Можно какой-нибудь метод отжига или генетический алгоритм использовать, но может не найти оптимальное решение, если не повезет. Если подойдет не самое-самое оптимальное решение, а просто хорошее, то можно проще: Генерируйте случайные перестановки и жадно локально меняйте порядок вершин, если он уменьшает ответ (переставляйте местами 2 вершины, или разворачивайте кусок пути). Еще можно какую-нибудь наивную жадность сделать: Каждый раз следующей берите самую близкую из не обойденных пока вершин. Повторю, что это будет не оптимальное решение, а лишь какая-то аппроксимация.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы