262
правки
Изменения
→Препроцессинг
===Препроцессинг===
[[Файл:reach3.jpg|right]]
* на начальном этапе <tex>\forall v \hspace{1px} r(v)\leftarrow 0</tex>
* для каждой вершины <tex>s \in V</tex> рассмотрим дерево кратчайших путей до всех других вершин <tex>T_{s}</tex>.
Такой препроцессинг занимает порядка 12 часов даже на небольшом графе(~300K вершин), поэтому его необходимо ускорить.
====Сокращение области поиска====
Заметим, что нам нужны только вершины с маленьким охватом <tex>r(v)\textless \varepsilon</tex>. Заметим также, что если <tex>r(v) \geq \varepsilon</tex>, то существует такой путь <tex>P</tex>, что на нем лежит вершина <tex>v \in P</tex>, для которой выполняется условие <tex>r(v,P)\geq \varepsilon</tex>
Кратчайший путь <tex>P_{s\rightsquigarrow t} = (s, s',...,v,...,t',t)</tex> будет <tex>\varepsilon</tex>-минимальным тогда и только тогда, когда выполняются условия
<tex>dist(s,v)\geq\varepsilon</tex>; <tex>dist(s',v)\textless\varepsilon</tex>; <tex>dist(v,t)\geq\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 \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>
====Пенальти====
=Ссылки=
