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

Question

[Drak Lowell]

У меня есть к примеру граф с 5 точками, которые между собой все связаны. Мне нужно найти кратчайший путь, который обойдет каждую точку единожды. Конечная точка не имеет значения.

Comments

[Алан Гибизов]

Покажи хоть, как пытался.

[Wataru]

Drak Lowell, Очень непонятно написано условие. Уточните, пожалуйста.

"путь, который обойдет каждый граф единижны" - У вас что, несколько графов? Вроде как у вас один граф и в нем важные вершины. Вам надо пройтись по всем waypoint вершинам? Конечная точка не важна, но есть ли фиксированная начальная точка?
Waypoint-ы можно обходить в любом порядке? Можно ли заходить в waypoint несколько раз (допустим, кратчайший путь из B в C лежит уже через обойденную A)? Может ли путь заходить в уже обойденные не waypoint-ы (просто вершины графа)? Насколько у вас большой граф, сколько в нем может быть waypoint-ов?

[Drak Lowell]

wataru, Я имел ввиду обойти каждую вейпоинт ( а точнее все, там нет других вершин ) вершину. Есть начальная вершина. Конечная неважна. Повторно заходить в вершину нельзя!

Answer 1

[rPman]

Простейшие комбинаторные алгоритмы.

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

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

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

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

p.s. можно по хитрому реализовать хранение пути в бегунке, чтобы оптимизировать затраты на n*логарифм от размера лабиринта, вместо квадрата.

Comments

[Drak Lowell]

Сейчас проверить не могу, но идея нравиться!

Answer 2

[Wataru]

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

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

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