262
правки
Изменения
→Reach
Пусть вершина <tex>v \in P</tex> лежит на кратчайшем пути <tex>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>LB(w,t)</tex>?
* Явно: Евклидово расстояние, с помощью ориентиров
* Неявно: сделать поиск двунаправленным
Например, радиус <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>
Для улучшения результата, нам необходимо сбалансировать прямой и обратный поиск.
===Препроцессинг===
* на начальном этапе <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</tex>. Заметим также, что если <tex>r(v) \geq \varepsilon</tex>, то существует такой путь <tex>P</tex>, что на нем лежит вершина <tex>v \in P</tex>, для которой выполняется условие <tex>r(v,P)\geq \varepsilon</tex>
=Ссылки=
