262
правки
Изменения
м
Кратчайший Назовём кратчайший путь <tex>P_{s\rightsquigarrow t} = (s, s',...,v,...,t',t)</tex> будет <tex>\varepsilon</tex>-минимальным тогда и только тогда, когда если выполняются условия
→Reach
Эта эвристика основывается на интуитивном наблюдении: не стоит посещать "локальные" дороги, когда мы находимся достаточно далеко и от <tex>s</tex>, и от <tex>t</tex>
Пусть вершина <tex>v \in P</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>.
[[Файл:reach1.jpg|right]]
Заметим, что вершины с большим охватом находятся вблизи середины некоторого длинного кратчайшего пути, то есть
Во время обработки ребра <tex>(v,w)</tex>:
* удалим вершину <tex>w</tex>, если <tex>r(w)<\min\{d(s,v)+\ell(v,w), LB(w,t)\}</tex>
* оценка <tex>LB(w,t)</tex> должна быть подобрана таким образом, чтобы, если бы <tex>P=(s,..,v,w,...,t)</tex> было кратчайшим путём, <tex>r(w)</tex> было бы больше.
[[Файл:reach2.jpg|right]]
Например, радиус <tex>R_{t}</tex> поиска в обратную сторону может быть нижней оценкой, т.к. если вершина <tex>w</tex> не была посещена поиском в обратную сторону, то <tex>d(w,t)\geq R_{t}</tex>
Таким образом, будем удалять <tex>w</tex>, если <tex>r(w)\textless \min\{d(s,v)+\ell(v,w), R_{t}\}</tex>
Для улучшения результата, нам необходимо сбалансировать прямой и обратный поиск.
====Препроцессинг====
[[Файл:reach3.jpg|right]]
* на начальном этапе <tex>\forall v \hspace{1px} : r(v)\leftarrow 0</tex>
* для каждой вершины <tex>s \in V</tex> рассмотрим дерево кратчайших путей до всех других вершин <tex>T_{s}</tex>.
**найдём наиболее длинный путь <tex>P_{s\rightsquigarrow t}</tex>, содержащий <tex>v</tex>.
**Назовём глубиной вершины <tex>d_{s}(v)</tex> расстояние от <tex>s</tex>, высотой вершины <tex>h_{s}(v)</tex> - расстояние до наиболее далёкого потомка вершины
** Тогда, охватом вершины в этом дереве будет величина <tex>r_{s}(v) = \min\{d_{s}(v),h_{s}(v)\}</tex>** Тогда обновим значение охвата <tex>r(v) \leftarrow \max\{r(v),r_{s}(v)\}</tex>
Такой препроцессинг занимает порядка 12 часов даже на небольшом графе(~300K вершин), поэтому его необходимо ускорить.
=====Сокращение области поиска=====
Заметим, что нам нужны только вершины с маленьким охватом <tex>r(v)\textless \varepsilon, \varepsilon=const</tex>. Заметим также, что если <tex>r(v) \geq \varepsilon</tex>, то существует такой путь <tex>P</tex>, что на нем лежит вершина <tex>v \in P</tex>, для которой выполняется условие <tex>r(v,P)\geq \varepsilon</tex>
*<tex>dist(s,v)\geq\varepsilon</tex>; *<tex>dist(s',v)\textless\varepsilon</tex>; *<tex>dist(v,t)\geq\varepsilon</tex>; *<tex>dist(v,t')\textless\varepsilon</tex>
Таким образом, алгоритм будет выглядеть так:
* Установим <tex>G'\leftarrow G</tex> и <tex>\varepsilon\leftarrow \varepsilon_{0}</tex> (маленькое число)
* Пока <tex>G'</tex> не пусто
** найдём частичное дерево кратчайших путей, чтобы найти вершины с охватом <tex>r(v) \geq \varepsilon</tex>** удалим из <tex>G'</tex> оставшиеся вершины (с охватом <tex>r(v) \textless\varepsilon</tex>, уже обработанные)
** установим <tex>\varepsilon\leftarrow 3\varepsilon</tex>
[[Файл:reach5.jpg|right]]
Ещё одна проблема нашего препроцессинга в том, что мы должны предполагать, что кратчайший путь может начинаться в вершине, отброшенной на одном из этапов поиска охвата. Для этого мы введём новую величину - <b>пенальти</b>(<i>penalty</i>) - верхнюю оценку на длину кратчайшего пути в "отброшенной" зоне.
Пусть <tex>G_{i} = (V_{i},E_{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> было как минимум одно выброшенное в процессе алгоритма входящее ребро, или ноль в противном случае.
Аналогично определим исходящее пенальти для исходящих из вершины рёбер.
