z17
@z17
Java, PHP

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

Есть определённый граф ( города ), есть на этом графе некоторое кол-во ключевых точек (скажем 1000 штук).
Есть точки А и Б - начало и конец маршрута.
Нужно проложить маршрут из А в Б через некоторое количество ключевых точек.
Некоторое кол-во - т.е. провести только через те точки, что более-менее по пути.
На практике будут строиться туристические маршруты через достопримечательности.

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

Возможно кто-то знает более подходящий алгоритм, который можно взять за основу?
  • Вопрос задан
  • 8307 просмотров
Решения вопроса 1
tsarevfs
@tsarevfs
C++ developer
Очень похоже на динамику. Можно попробовать построить граф (полный?) из ключевых точек. Предпосчитать расстояние между вершинами по карте (A*).
Далее вы либо можете либо просто придумать хитрые веса для ребер на основе длинны и рейтинга достопримечательностей в инцидентных вершинах. В этом случае нужен путь максимального веса.
Иначе надо искать путь максимального веса с ограничением на длину. Наверняка люди не захотят обходить весь город. Вроде бы по ссылке описывается что-то подобное.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
maaGames
@maaGames
Погроммирую программы
Алгоритма два: поиск в глубину и поиск в ширину.
В зависимости от прямизны рук, поиск в глубину потребует меньше памяти и отработает быстрее, зато поиск в глубину найдёт оптимальный (кратчайший по количеству хопов) путь. Для поиска в ширину потребуется либо модификация данных в графе, либо отдельно хранить уже посещённые узлы и узлы, которые обрабатываются на текущей итерации.
Ну и хорошо бы не впадать в шок при слове "рекурсия".)
Ответ написан
Ваш ответ на вопрос

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

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