Меню

Что такое кротчайший путь и как его найти



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

С каждым днем автомобильные 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.

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

Источник статьи: http://av-gps.com/articles/871-kratchajshij-put.html

Базовые алгоритмы нахождения кратчайших путей во взвешенных графах

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

Сформулируем определения и задачу.
Графом будем называть несколько точек (вершин), некоторые пары которых соединены отрезками (рёбрами). Граф связный, если от каждой вершины можно дойти до любой другой по этим отрезкам. Циклом назовём какой-то путь по рёбрам графа, начинающегося и заканчивающегося в одной и той же вершине. И ещё граф называется взвешенным, если каждому ребру соответствует какое-то число (вес). Не может быть двух рёбер, соединяющих одни и те же вершины.
Каждый из алгоритмов будет решать какую-то задачу о кратчайших путях на взвешенном связном. Кратчайший путь из одной вершины в другую — это такой путь по рёбрам, что сумма весов рёбер, по которым мы прошли будет минимальна.
Для ясности приведу пример такой задачи в реальной жизни. Пусть, в стране есть несколько городов и дорог, соединяющих эти города. При этом у каждой дороги есть длина. Вы хотите попасть из одного города в другой, проехав как можно меньший путь.

Считаем, что в графе n вершин и m рёбер.
Пойдём от простого к сложному.

Алгоритм Флойда-Уоршелла

Находит расстояние от каждой вершины до каждой за количество операций порядка n^3. Веса могут быть отрицательными, но у нас не может быть циклов с отрицательной суммой весов рёбер (иначе мы можем ходить по нему сколько душе угодно и каждый раз уменьшать сумму, так не интересно).
В массиве d[0… n — 1][0… n — 1] на i-ой итерации будем хранить ответ на исходную задачу с ограничением на то, что в качестве «пересадочных» в пути мы будем использовать вершины с номером строго меньше i — 1 (вершины нумеруем с нуля). Пусть идёт i-ая итерация, и мы хотим обновить массив до i + 1-ой. Для этого для каждой пары вершин просто попытаемся взять в качестве пересадочной i — 1-ую вершину, и если это улучшает ответ, то так и оставим. Всего сделаем n + 1 итерацию, после её завершения в качестве «пересадочных» мы сможем использовать любую, и массив d будет являться ответом.
n итераций по n итераций по n итераций, итого порядка n^3 операций.
Псевдокод:

Алгоритм Форда-Беллмана

Находит расстояние от одной вершины (дадим ей номер 0) до всех остальных за количество операций порядка n * m. Аналогично предыдущему алгоритму, веса могут быть отрицательными, но у нас не может быть циклов с отрицательной суммой весов рёбер.
Заведём массив d[0… n — 1], в котором на i-ой итерации будем хранить ответ на исходную задачу с ограничением на то, что в путь должно входить строго меньше i рёбер. Если таких путей до вершины j нет, то d[j] = 2000000000 (это должна быть какая-то недостижимая константа, «бесконечность»). В самом начале d заполнен 2000000000. Чтобы обновлять на i-ой итерации массив, надо просто пройти по каждому ребру и попробовать улучшить расстояние до вершин, которые оно соединяет. Кратчайшие пути не содержат циклов, так как все циклы неотрицательны, и мы можем убрать цикл из путя, при этом длина пути не ухудшится (хочется также отметить, что именно так можно найти отрицательные циклы в графе: надо сделать ещё одну итерацию и посмотреть, не улучшилось ли расстояние до какой-нибудь вершины). Поэтому длина кратчайшего пути не больше n — 1, значит, после n-ой итерации d будет ответом на задачу.
n итераций по m итераций, итого порядка n * m операций.
Псевдокод:

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

Находит расстояние от одной вершины (дадим ей номер 0) до всех остальных за количество операций порядка n^2. Все веса неотрицательны.
На каждой итерации какие-то вершины будут помечены, а какие-то нет. Заведём два массива: mark[0… n — 1] — True, если вершина помечена, False иначе, d[0… n — 1] — для каждой вершины будет храниться длина кратчайшего пути, проходящего только по помеченным вершинам в качестве «пересадочных». Также поддерживается инвариант того, что для помеченных вершин длина, указанная в d, и есть ответ. Сначала помечена только вершина 0, а g[i] равно x, если 0 и i соединяет ребро весом x, равно 2000000000, если их не соединяет ребро, и равно 0, если i = 0.
На каждой итерации мы находим вершину, с наименьшим значением в d среди непомеченных, пусть это вершина v. Тогда значение d[v] является ответом для v. Докажем. Пусть, кратчайший путь до v из 0 проходит не только по помеченным вершинам в качестве «пересадочных», и при этом он короче d[v]. Возьмём первую встретившуюся непомеченную вершину на этом пути, назовём её u. Длина пройденной части пути (от 0 до u) — d[u]. len >= d[u], где len — длина кратчайшего пути из 0 до v (т. к. отрицательных рёбер нет), но по нашему предположению len меньше d[v]. Значит, d[v] > len >= d[u]. Но тогда v не подходит под своё описание — у неё не наименьшее значение d[v] среди непомеченных. Противоречие.
Теперь смело помечаем вершину v и пересчитываем d. Так делаем, пока все вершины не станут помеченными, и d не станет ответом на задачу.
n итераций по n итераций (на поиск вершины v), итого порядка n^2 операций.
Псевдокод:

Источник статьи: http://habr.com/ru/post/119158/


Adblock
detector