Изменения

* отправная точка - — вершина <tex>s</tex>, пункт назначения - — вершина <tex>t</tex>

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

Можно заметить, что при такой реализации, все операции с приоритетной очередью будут выполняться за <tex>O(1)</tex>. Тогда, для одноуровневой реализации время работы алгоритма Дейкстры можно оценить как <tex>O(m+nC)</tex>, где <tex>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>\mu</tex> - — минимальное из текущих значений <tex>d(v):v \in V</tex>. Тогда, если существует такая вершина <tex>u</tex>, что <tex>\mu + c(u) \geqslant d(u)</tex>, то текущее значение <tex>d(u)</tex> точно.

Модифицируем нашу MLB - — структуру: будем хранить помеченные вершины в двух структурах: дерево поиска <tex>F</tex> и приоритетная очередь <tex>B</tex>, реализованная на MLB.

Рассмотрим механизм релаксации: пусть мы уменьшаем <tex>d(u)</tex>. Заметим, что в этом случае <tex>u</tex> не могло лежать в <tex>F</tex> (иначе <tex>d(u)</tex> было не точно). Если <tex>u \in B</tex> - — применим <tex>\mathtt{decrease - — key}</tex> к <tex>u</tex>. Эта операция либо переместила <tex>u</tex> внутри <tex>B</tex>, либо определила, что метка <tex>d(u)</tex> точна и переместила <tex>u</tex> в <tex>F</tex>.

Создадим две приоритетных очереди и запустим на одной из них алгоритм Дейкстры, ищущий <tex>d_{forward}(v)</tex> из <tex>s</tex>, а на другой - — ищущий <tex>d_{reverse}(v)</tex> из <tex>t</tex>. Алгоритм завершит свою работу, когда какая-нибудь вершина <tex>z</tex> будет удалена из обоих очередей.

вершины с <tex>d_{reverse}(v)</tex> и найти ребро <tex>uv</tex> с минимальным <tex>d_{forward}(u)+\ell(uv)+ d_{reverse}(v) </tex>. Если эта величина меньше, чем длина первоначально найденного пути - — то это и есть результат работы алгоритма.

Возьмём функцию <tex>h(v): V \rightarrow \mathbb{R} </tex> - — <b><i>потенциал (potential)</i></b> вершины. Тогда, с её помощью можно определить <b><i>потенциальную стоимость (reduced cost)</i></b> каждого ребра как <tex>\ell_{h}(v,w) = \ell(v,w)-h(v)+h(w)</tex>

Назовём функцию <tex>h</tex> <b>правдоподобной (<i>feasible</i>)</b>, если <tex>\forall (u,v): \ell_{h}(u,v) \geqslant 0</tex>. Известно, что, если <tex>h(t)\leqslant 0</tex> и <tex>h</tex> правдоподобна, то для любого <tex>v</tex>, <tex>h(v)</tex> - — нижняя граница <tex>d(v,t)</tex>

Главное отличие от алгоритма Дейкстры в том, что A* является <b>информированным</b> алгоритмом - — он обрабатывает в первую очередь те вершины, которые находятся ближе к результату.

* в худшем случае - — <tex>h(v)=0</tex> - вырождается в алгоритм Дейкстры* в лучшем случае - — <tex>\forall v: h(v)=d(v,t)</tex>

*<tex>\ell_{p_{f}}(v,w) = \ell(v,w)-p_{f}(v)+p_{f}(w)</tex> - — если ребро обрабатывается в обходе, начатом в <tex>s</tex>*<tex>\ell_{p_{r}}(v,w) = \ell(v,w)-p_{r}(w)+p_{r}(v)</tex> - — если ребро обрабатывается в обходе, начатом в <tex>t</tex>

Решение - — использовать усреднённые потенциальные функции:

* Алгоритм Дейкстры: препроцессинг - — ничего не делать, запрос - — выполнение алгоритма Дейкстры;* Полный перебор: препроцессинг - — посчитать таблицу расстояний размером <tex>n \times n</tex> (займёт порядка 5 лет времени и 1 петабайта памяти для карты Европы), запрос - — обратиться к элементу таблицы.

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

* если некоторое ребро находится на кратчайшем пути между исходной точкой и ориентиром - — по нему идём в первую очередь

Будем использовать неравенство треугольника для нижних оценок пути (см. рис. 1). Пусть <tex>A</tex> - — один из ориентиров, тогда:

Пусть вершина <tex>v</tex> лежит на кратчайшем пути <tex>P: s \rightsquigarrow t</tex>. Тогда, назовём <b>охватом (reach)</b> вершины <tex>v</tex> относительно <tex>P</tex> величину <tex>r(v,P) = \min\{dist(s,v), dist(v,t)\}</tex>. Охватом вершины относительно всего графа назовём величину <tex>r(v) = \max\limits_{P} r(v,P)</tex> - — максимум по всем кратчайшим путям, содержащим <tex>v</tex>.

Помимо этого, будет полезным ввести понятие охвата ребра. Назовём охватом ребра <tex>(v,w)\in P</tex> относительно <tex>P</tex> величину <tex>\min\{dist(s,v), dist(w,t)\}</tex>. Аналогично, охватом ребра относительно всего графа назовём величину <tex>r(v,w) = \max\limits_{P} r((v,w),P)</tex> - — максимум по всем кратчайшим путям, содержащим <tex>(v,w)</tex>.

**Назовём глубиной вершины <tex>d_{s}(v)</tex> расстояние от <tex>s</tex>, высотой вершины <tex>h_{s}(v)</tex> - — расстояние до наиболее далёкого потомка вершины

*фаза отладки (вершины с большим охватом обрабатываются указанным выше алгоритмом - — их гораздо меньше, поэтому обработка будет быстрой)

*найдём оценку охвата <tex>r'(v)</tex>, используя только <tex>\varepsilon</tex> - — минимальные пути

Полезно будет рассматривать <b>частично обработанные деревья</b> (<i>partial trees</i>) - — деревья кратчайших путей, хранящие пути длиной, меньшей определённого порога. Тогда дерево кратчайших путей будет глубиной порядка <tex>2\varepsilon</tex>:

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

Пусть <tex>G_{i} = (V_{i},A_{i})</tex> - — подграф исходного графа, полученный на <tex>i</tex>-й итерации алгоритма, описанного выше. Назовём входящим пенальти (<i>in-penalty</i>) вершины <tex>v\in V_{i}</tex> величину <tex>\max\{ \overline{r}(u,v) : u,v \in A \backslash A_{i}\}</tex>, если у <tex>v</tex> было как минимум одно выброшенное в процессе алгоритма входящее ребро, или ноль в противном случае.

* Глубиной вершины <tex>v\in T_{x}</tex>, где <tex>T_{x}</tex> - — частично обработанное дерево с корнем в <tex>x</tex> величину <tex>depth(v)=d(v)+in\textrm{-}penalty(x)</tex> , где <tex>d(v)</tex> - — длина пути от корня до вершины в дереве.* Чтобы определить высоту вершины, нам нужно понятие "ложных листьев". Для каждой вершины <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>) - — ребро, проходящее из начала пути в его конец с длиной, равной длине этого пути. Таким образом мы можем уменьшить охваты вершин на этом пути и ускорить препроцессинг (уменьшив количество проходимых рёбер), но увеличим память, необходимую для хранения нашего графа.

В обоих случаях подразумевается, что <tex>u\neq w</tex>, то есть у <tex>v</tex> обязательно есть только два соседа. В первом случае, <tex>v</tex> - — кандидат на односторонний пропуск (one-way bypass), во втором - — на двухсторонний (two-way bypass). Мы будем использовать сокращающие рёбра, чтобы пропускать такие вершины.

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

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

Пусть <tex>V_{\delta} \subset G</tex> - — множество вершин с высоким охватом мощностью <tex>\delta</tex>. Чтобы пересчитать их охваты, сначала необходимо найти подграф <tex>G_{\delta} = (V_{\delta},A_{\delta})</tex>. Этот граф содержит не только первоначальные рёбра, но и добавленные во время основной фазы сокращающие рёбра. Затем мы запустим поиск точных значений охвата для каждой вершины этого подграфа. Так как деревья кратчайших путей будут содержать только вершины из <tex>G_{\delta}</tex>, то нам всё ещё нужно использовать входящие и исходящие пенальти для остальных вершин. Но, тем не менее, они будут меньше, т.к. для самых больших мы подсчитали точное значение охвата.

* зелёный квадрат - — начало пути* синий квадрат - — конец пути* зелёные линии - — пути, пройденные прямым обходом* синие линии - — пути, пройденные обратным обходом* красные ромбы - — ориентиры* жёлтые ромбы - — выбранные при поиске пути ориентиры