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

Question

Я создаю Java-программу, которая будет рассчитывать самый быстрый маршрут между всеми указанными пунктами назначения, начиная с выбранного пользователем. Это планировщик поездки - вы начинаете на базе, посещаете все пункты назначения и возвращаетесь на базу. Места и связи между ними представлены ориентированным взвешенным графом. Всегда есть оба маршрута A-> B и B-> A, но их длина может варьироваться. Места можно посещать несколько раз, особенно если это может помочь сократить общее расстояние.

Я совершенно запутался во всем этом. Я думал о реализации алгоритма DFS и приоритезации маршрутов по кратчайшей длине. Что бы вы предложили?

Answer 1

Это проблема NP-Hard , известная как Задача коммивояжера . По мере того, как количество городов для посещения растет, количество возможных путей растет в геометрической прогрессии.

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

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

Answer 2

Вы можете использовать Алгоритм сильной связи Тарьяна .