262
правки
Изменения
м
ПроблемаЕщё одна проблема нашего препроцессинга в том, что мы должны предполагать, что кратчайший путь может начинаться в вершине, отброшенной на одном из этапов поиска охвата. Для этого мы введём новую величину - <b>пенальти</b>(<i>penaltie</i>) - верхнюю оценку на длину кратчайшего пути в "отброшенной" зоне.
→Препроцессинг
* если же <tex>r'(v)\geq \varepsilon</tex>, то она нас не интересует: <tex>r(v)\geq r'(v)</tex>
Полезно будет рассматривать <b>частичные частично обработанные деревья</b> (<i>partial trees</i>)- деревья кратчайших путей, хранящие пути длиной, тогда меньшей определённого порога. Тогда дерево кратчайших путей будет глубиной порядка <tex>2\varepsilon</tex>:* Установим <tex>G'\leftarrow G</tex> и <tex>\varepsilon\leftarrow \varepsilon_{0}</tex>(маленькое число)
* Пока <tex>G'</tex> не пусто
** используем частичные деревьянайдём частичное дерево кратчайших путей, чтобы найти вершины с охватом <tex>\geq \varepsilon</tex>
** удалим из <tex>G'</tex> оставшиеся вершины (с охватом <tex>\textless\varepsilon</tex>, уже обработанные)
** установим <tex>\varepsilon\leftarrow 3\varepsilon</tex>
====Сокращение путей====
Представим последовательность вершин степени 2 с большим охватом, идущих подряд. Добавим, <b>сокращающий путь</b> (<i>shortcut</i>) - ребро, проходящее из начала пути в его конец с длиной, равной длине этого пути.
====Пенальти====
=Ссылки=
