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].
При поиске оптимального маршрута важно учитывать не только протяженность пути, но и качество дорог, возможность прохода тем или иным видом транспорта, и по возможности выбирать наиболее приемлемый вариант из множества возможных.
- Содержание
- Введение
- 1 Анализ предметной области
- 2 Определение способа реализации
- 2.1 Выбор аппаратной платформы
- 2.2 Выбор операционной системы
- 2.2.1 Особенности архитектуры ос Android
- 2.3 Выбор средств разработки и тестирования
- 2.3.1 Язык Java
- 2.3.3 Интегрированная среда разработки Eclipse
- 3 Функциональные требования к системе
- 4 Разработка проекта
- 4.1 Обзор и решение ключевых задач
- 4.1.1 Определения текущего местоположения
- 4.1.2 Прокладка оптимального маршрута
- 4.1.3 Особенности построения графа дорог в OpenStreetMap
- 4.1.4 Поиск оптимального маршрута
- 4.1.5 Прогнозирование времени прохождения маршрута
- 4.1.6 Диспетчеризация
- 4.2 Графический интерфейс системы
- 4.2.1 Интерфейс арм Курьера
- 4.2.2 Интерфейс арм Диспетчера
- 4.3 Развертывание системы
- 5 Технико-экономическое обоснование дипломного проекта
- 5.1 Swot-анализ
- 5.2 Pest-анализ
- 5.3 Расчет экономических показателей
- 5.4 Расчет затрат на разработку программы
- 5.5 Расчет цены разработанной программы
- 5.6 Расчет капитальных вложений
- 5.7 Расчет эксплуатационных расходов
- 5.8 Расчет денежного годового экономического эффекта
- 6 Безопасность и экологичность дипломного проекта
- 6.1 Электробезопасность
- 6.2 Электромагнитные излучения
- 6.3 Требования к эргономике, освещенности, уровню шума и
- 6.4 Пожарная безопасность
- Заключение
- Список использованных источников
- Приложение а
- Исходний код программы. Курьерская часть
- Приложение б
- Исходний код программы. Диспетчерская часть
- Приложение в
- Графический материал