262
правки
Изменения
→Удаление пропущенных вершин
* <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>
====Фаза отладки====
Тот факт, что мы используем пенальти, для ускорения вычисления корректных верхних оценок охвата, приводит к тому, что оценки становятся менее точными в процессе работы алгоритма и с ростом пенальти. Следовательно, для вершин, которые дольше находятся в графе, ошибки накапливаются. Это плохо, потом что такие вершины и являются самыми важными в графе - у них высокий охват, их посещает большое количество кратчайших путей. Если бы мы могли сделать их более точными, во время запроса можно было бы пропустить большее количество вершин.
В этом и заключается цель фазы отладки. После того, как мы найдём верные значения верхних оценок, используя частично обработанные деревья, во время фазы отладки мы пересчитаем охват <tex>\delta = const</tex> вершин с наибольшими значениями охвата (в них больше всего ошибок).
Пусть <tex>V_{\delta} \subset G</tex> - множество вершин с высоким охватом мощностью <tex>\delta</tex>. Чтобы пересчитать их охваты, сначала необходимо найти подграф <tex>G_{\delta} = (V_{\delta},A_{\delta})</tex>. Этот граф содержит не только первоначальные рёбра, но и добавленные во время основной фазы сокращающие рёбра. Затем мы запустим поиск точных значений охвата для каждой вершины этого подграфа. Так как деревья кратчайших путей будут содержать только вершины из <tex>G_{\delta}</tex>, то нам всё ещё нужно использовать входящие и исходящие пенальти для остальных вершин. Но, тем не менее, они будут меньше, т.к. для самых больших мы подсчитали точное значение охвата.
Во время фазы отладки мы заботимся о точности, а не о скорости, поэтому не добавляем новых сокращающих рёбер и используем точный алгоритм.
Поэтому, время работы алгоритма как минимум <tex>\Omega(\delta^{2})</tex>
==Ссылки==
