Кратчайший путь

С каждым днем автомобильные gps навигаторы получают все большее распространение среди людей. Нахождение кратчайшего пути — одна из главных функций этого устройства. Давайте попробуем разобраться, по какому алгоритму устройства находят кратчайший путь.

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

Алгоритм позиционирования довольно прост. На средней околоземной орбите находятся 30 спутников, передающих одинаковый сигнал. Сообщения состоят из трех основных частей: точного время передачи, точных данных орбиты спутника (эфемерид) и общесистемной информации. Устройство GPS принимает и анализирует передаваемые спутниками сообщения. Зная время отправки, навигатор определяет, как долго сигнал находился в пути и как далеко расположен спутник.

Как навигатор определяет местоположение

Используя данные только с одного спутника, устройство GPS определяет свое положение на поверхности виртуальной сферы с центром на этом спутнике. В таких данных полезной информации крайне мало.

Анализ данных с двух спутников дает область пересечения двух сфер с центрами на каждом спутнике. Пытаясь представить пересечение двух сфер геометрически, можно выделить три возможных случая: сферы не пересекаются вообще, сферы пересекаются в одной точке (возможно только при касании сфер), либо сферы пересекаются в виде окружности. Чтобы было легче представить это, сопоставьте мысленно сферы с мыльными пузырями. Но информации для позиционирования и в этом случае недостаточно.

В случае с тремя случаями мы имеем область пересечения сферы и окружности, рассмотренной ранее. Геометрически такое пересечение может дать до двух точек.

Так, для определения своей позиции GPS устройство использует по меньшей мере четыре различных спутника. Спутники GPS расположены над Землей таким образом, что из любой точки Земли одновременно видно их около 10 (если, конечно, не мешает рельеф или другие непрозрачные для радиоволн препятствия). Нетрудно догадаться, что такое расположение является достаточным для определения позиции. Положение приемника, вычисляемое по данным только GPS спутников, рассчитывается с точностью до 15 м.

Помехи

Причин возникновения сравнительно большой погрешности позиционирования несколько. Среди них влияние атмосферы на скорость распространения электромагнитных волн, отражения сигнала от препятствий и т.д. Однако, как мы знаем, возможно (и широко применяется) более точное позиционирование. Это возможно в тех случаях, когда для вычисления позиции навигатор использует не только данные спутников, но и корректирующие (как правило, наземные) сигналы.

Если как часть навигационной системы рассматривать приемное устройство, расположенное в автомобиле, то оно может использовать в работе дополнительную информацию с автомобиля, такую как скорость, пройденный путь, ускорение и другие данные. Это существенно помогает в городах, где путь распространения сигналов со спутника перекрывается зданиями, а из-за плотной застройки на приемник приходим многократно отраженный от стен сигнал.

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

Прокладывание пути

Итак, мы пришли к тому, что работа навигатора с картами, представляющими собой модели местности, имеет большое значение. Рассмотрим второй алгоритм: поиск кратчайшего пути из текущего положения (определенного как точка с конкретными координатами) в пункт назначения (определенного так же).

Главным условием для работы такого алгоритма является наличие векторной карты. Векторная карта представляет собой набор объектов (в основном дорог), которые отображаются на дисплее устройства. Благодаря этому можно учитывать ориентацию и положение машины в текущий момент времени.

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

Рассмотрим вектора на векторной карте как прямые участки дорог. Они задаются двумя точками с четкими координатами (начало и конец), а также содержат дополнительную информацию о названии улицы и типе покрытия. Реальная дорога состоит из нескольких векторов, причем конец последующего обычно совпадает с началом предыдущего.

Алгоритм Дейкстры

А теперь самое интересное. У нас есть две точки: начало и конец маршрута. Также у нас есть карта, представляющая собой большой массив векторов. Мы должны использовать его и рассчитать оптимальный маршрут.

Кратчайший путь

Обычно для таких случаев используется алгоритм Дейкстры для расчета оптимального пути между двумя узлами взвешенного графа или сети. Напомним, что граф – связанная структура данных, состоящая из вершин (узлов), со связями между ними (обычно называемых ребрами). Взвешенный граф характеризуется неким весом ребра.

Векторная карта представляет собой взвешенный граф, в качестве ребер которого выступают векторы, а их концы можно рассматривать в качестве узлов. Поскольку дорога представляет собой несколько векторов, соединенных концами, Вы можете увидеть, что большинство узлов на карте имеет два ребра. Не обобщая всё, предположим, что начальная и конечная точки определяются по широте и долготе пар и соответствуют концам векторов (таким образом, мы рассмотрим наиболее простой для понимания случай).

В качестве примера рассмотрим небольшую векторную карту. На ней отмечены длины векторов (участков дорог) и узлы, являющиеся соединением векторов. Также есть еще важный параметр, влияющий на вес ребра в графе – тип покрытия участка дороги. Например, передвижение по автомагистрали будет куда быстрей, чем по дороге с грунтовым покрытием. Длина вектора также влияет на вес ребра графа.

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

Все это обуславливает необходимость усовершенствования алгоритма Дейкстры. Узлы необходимо каким-то образом кодировать, и исключить из рассмотрения те, что находятся дальше от цели или в противоположном от нее направлении.

Алгоритм А*

Перечисленным выше особенностям удовлетворяет алгоритм, называемый А*. Это алгоритм для анализа графов, который находит наименее затратный путь от начальной точки до пункта назначения. Он был разработан американскими математиками еще в 1968 г.

Для расчета оптимального пути алгоритм А* использует два параметра, рассчитываемых для каждого узла: путь от предыдущего узла (обычно обозначают g) и эвристическая оценка расстояния от текущего узла к конечному (h). Определяющей величиной для каждого узла будет сумма f = g + h. Для сравнения, алгоритм Дейкстры соответствует алгоритму А* с h = 0 в каждой точке.

Рассмотрим, как это работает, на нашем примере. Пусть нам нужно переместиться из точки А в точку Z. Для начального узла g = 0, а h – расстояние «по прямой» до пункта назначения. Взяв к рассмотрению все соседние узлы и посчитав для них значение f, мы должны выбрать такой узел (и отметить путь к нему), для которого f будет минимальным. Естественно, те узлы, которые были рассмотрены на предыдущем шаге (и которые уже содержатся в результирующем пути) мы не должны включать в рассмотрение, а это в свою очередь несколько упростит задачу и время на вычисления.

Кратчайший путь

Такая последовательность итераций, в конечном счете, приведет нас к цели – точке Z.

Конечно, в реальном мире для реализации этого алгоритма нужно иметь точную карту, представляющую модель местности, которая бы учитывала не только длину отрезков дорог, но и состояние покрытия, рельеф местности и другие факторы. Помимо этого, сейчас все с большим успехом применяются алгоритмы выбора пути с учетом загруженности дорог (заторов). Но это уже тема другой статьи.