4.1.4 Поиск оптимального маршрута

Существует целый ряд алгоритмов поиска оптимального маршрута. Алгоритм поиска A* является наиболее интересным при решении задачи с большим количеством путей и вершин [22].

A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Как и все информированные алгоритмы поиска, он просматривает сначала те маршруты, которые «кажутся» ведущими к цели. От жадного алгоритма (который тоже является алгоритмом поиска по первому лучшему совпадению) его отличает то, что при выборе вершины он учитывает, помимо прочего, весь пройденный до неё путь (составляющая g(x) — это стоимость пути от начальной вершины, а не от предыдущей, как в жадном алгоритме). В начале работы просматриваются узлы, смежные с начальным; выбирается тот из них, который имеет минимальное значение f(x), после чего этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых (листовых) вершин графа («множеством частных решений»), которое размещается в очереди с приоритетом. Приоритет пути определяется по значению функции

f(x) = g(x) + h(x),

где g(x) – стоимость пути от начальной вершины;

h(x) – эвристика.

Алгоритм продолжает свою работу до тех пор, пока значение f(x) целевой вершины не окажется меньшим, чем любое значение в очереди (либо пока всё дерево не будет просмотрено). Из множественных решений выбирается решение с наименьшей стоимостью.

При работе с графом дорог OpenStreetMap, для реализации алгоритма поиска оптимального маршрута эффективно использовать сервис CloudMade.

CloudMade Maps – это англоязычный «облачный» картографический сервис, который тем не менее понимает и отыскивает кириллические обозначения. Его главное применение – поиск как адресов на карте, так и примерных маршрутов в пределах города или области, а также между городами и даже странами. Этот сервис поддерживает открытый формат OpenStreetMap.

Не так давно CloudMade выделил несколько приоритетных направлений, среди которых оказалась и навигация. Решено было создать специальный проект Navi Studio, который объединял бы в себе несколько более мелких сервисов и позволял пользоваться ими, для создания полноценного навигационного программного обеспечения [15].

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