Пешие прогулки — хороший способ познакомиться с новым районом или городом. Однако туристу, не знакомому с местностью, может оказаться сложно выбрать маршрут для прогулки, ведь он не знает, что интересного есть поблизости. Особенно, если речь идет о не самом популярном у туристов районе, для которого не издают путеводители. А даже если список достопримечательностей и есть в наличии, то выбор оптимального маршрута их посещения может оказаться сложной задачей.
Помочь таким туристам может специальный навигационный сервис, который будет строить не более короткие (как это делают существующие популярные навигационные сервисы), а более интересные пешеходные маршруты. Такие маршруты могут быть длиннее, зато они ведут мимо местных достопримечательностей, по зеленым зонам и набережным.
В статье предлагается алгоритм, который использует данные о достопримечательностях из Open Street Map и использует модернизированный A* и генетический алгоритмы для построения таких маршрутов. Рассматривается построение двух вариантов маршрута: между двумя разными точками (если турист хочет добраться до какой-то конкретной цели, осмотрев достопримечательности по пути) и круговой с возвратом в точку старта за указанное время (например, если турист хочет погулять вокруг отеля или вокзала).