262
правки
Изменения
м
→Сокращение путей
Как только мы нашли линию, самым простым решением будет добавить одно сокращающее ребро из начала в конец. Но практика показывает, что лучше сократить ещё и входящие в её состав линии меньшего размера, это ещё более уменьшит охваты пропускаемых вершин. Для этого перед добавлением сокращающего ребра по линии, рекурсивно найдём вершину, которая находится примерно на её середине и обработаем левый и правый отрезки как полноценные линии.
====Удаление пропущенных вершин====
Представим одностороннюю линию, состоящую из трёх вершин <tex>u</tex>, <tex>v</tex>, <tex>w</tex>. Когда мы добавили сокращающее ребро <tex>(u,w)</tex>, мы знали, что ребро <tex>(u,v)</tex> больше никогда не будет использоваться на кратчайшем пути содержащем подпуть <tex>u\rightsquigarrow w</tex>. Кроме того, любой кратчайший путь, содержащий <tex>(u,v)</tex>, будет оканчиваться либо в <tex>v</tex>, либо в близлежащей вершине с низким охватом.
Тогда, корректной верхней оценкой охвата <tex>(u,v)</tex> является <tex>\overline{r}(u,v)=\ell(u,v)+out\textrm{-}penalty(v)</tex>. Аналогично, <tex>\overline{r}(v,w)=\ell(v,w)+in\textrm{-}penalty(v)</tex>. Зная это, мы можем удалить вершину <tex>v</tex> и смежные ей рёбра из графа и обновить соответствующие значения пенальти для её соседей.
Такую же процедуру можно проделать с двусторонней линией, т.к. помимо оценок, указанных выше можно добавить:
* <tex>\overline{r}(w,v)=\ell(w,v)+out\textrm{-}penalty(v)</tex>
* <tex>\overline{r}(v,u)=\ell(v,u)+in\textrm{-}penalty(v)</tex>
==Ссылки==
