262
правки
Изменения
→Препроцессинг
** удалим из <tex>G'</tex> оставшиеся вершины (с охватом <tex>\textless\varepsilon</tex>, уже обработанные)
** установим <tex>\varepsilon\leftarrow 3\varepsilon</tex>
[[Файл:reach5.jpg|right]]
[[Файл:reach6.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> было как минимум одно выброшенное в процессе алгоритма входящее ребро, или ноль в противном случае.
Аналогично определим исходящее пенальти для исходящих из вершины рёбер.
Изменим алгоритм, чтобы заменить вершины на их пенальти. Для этого переопределим глубину и высоту вершины.
* Глубиной вершины <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>) - ребро, проходящее из начала пути в его конец с длиной, равной длине этого пути. ====Пенальти====Ещё одна проблема нашего препроцессинга в том, что Таким образом мы должны предполагать, что кратчайший путь может начинаться в вершине, отброшенной можем уменьшить охваты вершин на одном из этапов поиска охвата. Для этого мы введём новую величину - <b>пенальти</b>этом пути и ускорить препроцессинг(<i>penaltie</i>уменьшив количество проходимых рёбер) - верхнюю оценку на длину кратчайшего пути в "отброшенной" зоне, но увеличим память, необходимую для хранения нашего графа.
=Ссылки=
