251
правка
Изменения
м
→Сокращение области поиска
====Сокращение области поиска====
Заметим, что нам нужны только вершины с маленьким охватом <tex>r(v)\textless \varepsilon, \varepsilon=const</tex>. Заметим также, что если <tex>r(v) \geq geqslant \varepsilon</tex>, то существует такой путь <tex>P</tex>, что на нем лежит вершина <tex>v \in P</tex>, для которой выполняется условие <tex>r(v,P)\geq geqslant \varepsilon</tex>
Назовём кратчайший путь <tex>P_{s\rightsquigarrow t} = (s, s',...,v,...,t',t)</tex> <tex>\varepsilon</tex>-минимальным, если выполняются условия:
*<tex>dist(s,v)\geqgeqslant\varepsilon</tex>,
*<tex>dist(s',v)\textless\varepsilon</tex>,
*<tex>dist(v,t)\geqgeqslant\varepsilon</tex>,
*<tex>dist(v,t')\textless\varepsilon</tex>.
* найдём оценку охвата <tex>r'(v)</tex>, используя только <tex>\varepsilon</tex> — минимальные пути,
* если <tex>r'(v)<\varepsilon</tex>, то оценка корректна: <tex>r(v)=r'(v)</tex>,
* если же <tex>r'(v)\geq geqslant \varepsilon</tex>, то она нас не интересует: <tex>r(v)\geq geqslant r'(v)</tex>.
Полезно будет рассматривать <b>частично обработанные деревья</b> (англ. ''partial trees'') — деревья кратчайших путей, хранящие пути длиной, меньшей определённого порога. Тогда дерево кратчайших путей будет глубиной порядка <tex>2\varepsilon</tex>:
* установим <tex>G'\leftarrow G</tex> и <tex>\varepsilon\leftarrow \varepsilon_{0}</tex> (маленькое число),
* пока <tex>G'</tex> не пусто:
** найдём частично обработанное дерево кратчайших путей из <tex>v</tex>, чтобы найти вершины с охватом <tex>r(v) \geq geqslant \varepsilon</tex>,
** удалим из <tex>G'</tex> оставшиеся вершины (с охватом <tex>r(v) \textless\varepsilon</tex>, уже обработанные),
** установим <tex>\varepsilon\leftarrow 3\varepsilon</tex>.
[[Файл:reach5.jpg|right]]
[[Файл:reach6.jpg|right]]
====Пенальти====
Предыдущее улучшение создаёт проблему: мы должны предполагать, что кратчайший путь может начинаться в вершине с маленьким охватом, которые мы отбрасываем на каждой итерации. Для того, чтобы принять их во внимание, мы введём новую величину — <b>пенальти</b>(англ. ''penalty'') — верхнюю оценку на длину кратчайшего пути в "отброшенной" зоне.
