Какой лучший алгоритм для поиска оптимального пути через определённые точки?
Есть определённый граф ( города ), есть на этом графе некоторое кол-во ключевых точек (скажем 1000 штук).
Есть точки А и Б - начало и конец маршрута.
Нужно проложить маршрут из А в Б через некоторое количество ключевых точек.
Некоторое кол-во - т.е. провести только через те точки, что более-менее по пути.
На практике будут строиться туристические маршруты через достопримечательности.
Я смог нагуглить задачу коммивояжёра, в незамкнутом варианте задачи делается почти что нужное. Проблема остаётся одна - выбор оптимальных точек, через которые пройдёт маршрут.
Возможно кто-то знает более подходящий алгоритм, который можно взять за основу?
Очень похоже на динамику. Можно попробовать построить граф (полный?) из ключевых точек. Предпосчитать расстояние между вершинами по карте (A*).
Далее вы либо можете либо просто придумать хитрые веса для ребер на основе длинны и рейтинга достопримечательностей в инцидентных вершинах. В этом случае нужен путь максимального веса.
Иначе надо искать путь максимального веса с ограничением на длину. Наверняка люди не захотят обходить весь город. Вроде бы по ссылке описывается что-то подобное.
tsarevfs: да я не думаю что имеет какое-либо значение кол-во точек. Рассчитать всё заранее (пусть работает сколько угодно, разово же), записать в базу и радоваться.
Алгоритма два: поиск в глубину и поиск в ширину.
В зависимости от прямизны рук, поиск в глубину потребует меньше памяти и отработает быстрее, зато поиск в глубину найдёт оптимальный (кратчайший по количеству хопов) путь. Для поиска в ширину потребуется либо модификация данных в графе, либо отдельно хранить уже посещённые узлы и узлы, которые обрабатываются на текущей итерации.
Ну и хорошо бы не впадать в шок при слове "рекурсия".)
Максим: От точки А ищется ближайшая ключевая точка. Потом от этой точки следующая и так до точки Б.
При поиске в ширину сразу все варианты рассматриваешь, при поиске в глубину по одному находишь и можно на не оптимальном прерваться.
Где я был не прав?
maagames.ru: в случае, если ближайшая ключевая точка от предыдущей точки уходит куда-нибудь далеко - получится плохо. К тому-же количество ключевых точек в каждом маршруте не константное.
Можно, конечно, вводить коэффициенты отдалённости и прочее, но мне не кажется это хорошей идеей
> При поиске в ширину сразу все варианты рассматриваешь
Как раз чтобы исключить вот такие неприятные ситуации, которые почти наверняка при поиске в глубину возникнут.
Максим: В ширину ищется "мгновенно", но сжирает кучу памяти. Не помню, какой там рассчитать память для худшего случая. Допустим N^2 * размер_хранимого_элемента (это если из каждой вершины в каждую перейти можно). Если есть веса, то можно не все рёбра проверять, а только наиболее подходящие. Ну и если поиск вести сразу и из А и из Б, то площадь покрытия графом будет вдвое меньше, чем если только из А искать (памяти меньше зажрёт).
Простой
Простой
Простой
