Изменения

Дано:

* ориентированный граф <tex>G=(V,E)</tex>

* <tex>l(u,v)</tex> - среднее время, которое занимает проезд по дороге

основная статья: [[Алгоритм Дейкстры]]

* на каждом шаге выбирает из множества непросмотренных вершин вершину с наименьшим расстоянием до старта и релаксирует рёбра, исходящие из неё

Но на практике чаще используются 2-, 4- и 8-ичные кучи: они более простые, оценка времени работы содержит меньшее количество скрытых констант.

<div >[[Файл:multilevel_buckets.jpg ]]</div>

При такой реализации, время работы алгоритма Дейкстры можно оценить как <tex>O(m+n(1+ \sqrt{C}))</tex>

Введём величину <b><i>калибр (caliber)</i></b> вершины <tex>c(v)</tex> - вес минимального ребра, входящего в <tex>v</tex> , или <tex>\infty</tex>, если в вершину не входит ни одно ребро. Будем говорить, что текущее значение <tex>d(v)</tex> точно, если оно равно длине пути <tex>s \rightsquigarrow v</tex>.

{{Лемма

<tex>F</tex> или <tex>B</tex>, в зависимости от того, выполняется ли условие леммы.

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

На практике, такой двунаправленный поиск быстрее обычного алгоритма Дейкстры примерно в два раза.

основная статья: [[Алгоритм A*]]

**<tex>\ell_{h}(v,w)=0</tex>, если ребро <tex>(v,w)</tex> лежит на кратчайшем пути, иначе потенциальная стоимость положительна

**все посещённые вершины будут лежать на кратчайшем пути

Для двунаправленной версии алгоритма нам нужны две потенциальные функции:

При таком выборе потенциальных функций, выполняется <tex>\forall u : h_{f}(u)+h_{r}(u)=0</tex> и тогда двунаправленный A* становится аналогичен двунаправленному алгоритму Дейкстры

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

Оба эти примера - крайние случаи. Нам нужно нечто более гибкое: препроцессинг за часы/минуты, рост количества предпосчитанных данных линейно от размера графа и запросы в реальном времени.

Аббревиатура ALT расшифровывается как <b>A</b>* +<b>L</b>andmarks + <b>T</b>riangle inequality : A* + ориентиры + неравенство треугольника.

Существуют различные алгоритмы выбора ориентиров:

[[Файл:planarLandmarks.jpg|right]]

Как следует из названия, ориентиры выбираются случайным образом

* разделим карту на <tex>k</tex> секторов одинаковой площади

* возьмём ориентиром наиболее удалённую точку от центра в каждом секторе

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

Этот алгоритм добавляет ориентиры по одному, глядя на вершины, которые плохо покрыты текущим набором ориентиров <tex>S</tex>.

Начиная с максимальной по размеру вершины, пойдём вниз по дереву <tex>T_{r}</tex> и найдём лист с максимальным размером. Примем его за новый ориентир.

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

Этот метод является наилучшим, но является наиболее медленным. Задача выбора ориентиров в этом случае становится NP-полной.

Эта эвристика основывается на интуитивном наблюдении: не стоит посещать "локальные" дороги, когда мы находимся достаточно далеко и от <tex>s</tex>, и от <tex>t</tex>

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

[[Файл:reach3.jpg|right]]

* на начальном этапе <tex>\forall v \hspace{1px} r(v)\leftarrow 0</tex>

Такой препроцессинг занимает порядка 12 часов даже на небольшом графе(~300K вершин), поэтому его необходимо ускорить.

Заметим, что нам нужны только вершины с маленьким охватом <tex>r(v)\textless \varepsilon</tex>. Заметим также, что если <tex>r(v) \geq \varepsilon</tex>, то существует такой путь <tex>P</tex>, что на нем лежит вершина <tex>v \in P</tex>, для которой выполняется условие <tex>r(v,P)\geq \varepsilon</tex>

[[Файл:reach5.jpg|right]]

[[Файл:reach6.jpg|right]]

Ещё одна проблема нашего препроцессинга в том, что мы должны предполагать, что кратчайший путь может начинаться в вершине, отброшенной на одном из этапов поиска охвата. Для этого мы введём новую величину - <b>пенальти</b>(<i>penalty</i>) - верхнюю оценку на длину кратчайшего пути в "отброшенной" зоне.

* Чтобы определить высоту вершины, нам нужно понятие "ложных листьев". Для каждой вершины <tex>v</tex> в дереве кратчайших путей добавим потомка <tex>v'</tex> - ложный лист, и ребро <tex>(v,v') = out\textrm{--}penalty(v)</tex>. В некотором смысле, <tex>v'</tex> будет выступать в роли всех рёбер, изначально инцидентных вершине <tex>v</tex>, которые мы отсекли. Тогда высотой вершины <tex>v</tex> будет расстояние от неё, до наиболее далёкого ложного листа. Подчеркнём, что в данный момент ложные листья добавляются неявно, и только после того, как дерево будет частично обработано.

Представим последовательность вершин степени 2 с большим охватом, идущих подряд. Добавим, <b>сокращающий путь</b> (<i>shortcut</i>) - ребро, проходящее из начала пути в его конец с длиной, равной длине этого пути. Таким образом мы можем уменьшить охваты вершин на этом пути и ускорить препроцессинг(уменьшив количество проходимых рёбер), но увеличим память, необходимую для хранения нашего графа.

*[http://research.microsoft.com/pubs/64511/tr-2004-24.pdf A* meets graph theory]

*[http://algo2.iti.kit.edu/schultes/hwy/hhStarSubmit.pdf Highway Hierarhies Star*]