251
правка
Изменения
м
→Reach
Эта эвристика основывается на интуитивном наблюдении: не стоит посещать "локальные" дороги, когда мы находимся достаточно далеко и от <tex>s</tex>, и от <tex>t</tex>
Пусть вершина <tex>v</tex> лежит на кратчайшем пути <tex>P: s \rightsquigarrow t</tex>. Тогда, назовём <b>охватом (reach)</b> (англ. ''reach'') вершины <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>r'(v)\geq \varepsilon</tex>, то она нас не интересует: <tex>r(v)\geq r'(v)</tex>
Полезно будет рассматривать <b>частично обработанные деревья</b> (<i>англ. ''partial trees</i>'') — деревья кратчайших путей, хранящие пути длиной, меньшей определённого порога. Тогда дерево кратчайших путей будет глубиной порядка <tex>2\varepsilon</tex>:
* Установим <tex>G'\leftarrow G</tex> и <tex>\varepsilon\leftarrow \varepsilon_{0}</tex> (маленькое число)
* Пока <tex>G'</tex> не пусто
[[Файл:reach6.jpg|right]]
====Пенальти====
Предыдущее улучшение создаёт проблему: мы должны предполагать, что кратчайший путь может начинаться в вершине с маленьким охватом, которые мы отбрасываем на каждой итерации. Для того, чтобы принять их во внимание, мы введём новую величину — <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> было как минимум одно выброшенное в процессе алгоритма входящее ребро, или ноль в противном случае.
====Сокращение путей====
Представим последовательность вершин степени 2 с большим охватом, идущих подряд. Добавим, <b>сокращающее ребро</b> (<i>англ. ''shortcut</i>'') — ребро, проходящее из начала пути в его конец с длиной, равной длине этого пути. Таким образом мы можем уменьшить охваты вершин на этом пути и ускорить препроцессинг (уменьшив количество проходимых рёбер), но увеличим память, необходимую для хранения нашего графа.
На этом шаге мы будем искать <b>пропускаемые</b> (англ. ''bypassable'') вершины. Назовём вершину <tex>v</tex> пропускаемой, если выполняется одно из двух условий:
* <tex>v</tex> имеет только одно входящее ребро <tex>(u,v)</tex> и одно исходящее ребро <tex>(v,w)</tex>
* <tex>v</tex> имеет два входящих ребра <tex>(u,v)</tex>, <tex>(w,v)</tex> и два исходящих ребра <tex>(v,w)</tex> ,<tex>(v,u)</tex>
В обоих случаях подразумевается, что <tex>u\neq w</tex>, то есть у <tex>v</tex> обязательно есть только два соседа. В первом случае, <tex>v</tex> — кандидат на односторонний пропуск (англ. ''one-way bypass''), во втором — на двухсторонний (англ. ''two-way bypass''). Мы будем использовать сокращающие рёбра, чтобы пропускать такие вершины.
Линия (line) — путь в графе, содержащий как минимум три вершины, так, что все вершины, кроме начальной и конечной, пропускаемые. Каждая пропускаемая вершина может принадлежать только одной линии. Линии также могут быть односторонне- и двухсторонне- пропускаемыми, в зависимости от типа вершин, которые они содержат. Легко заметить, что на линии могут лежать вершины только одного типа.
