262
правки
Изменения
→Reach
==Reach==
Эта эвристика основывается на интуитивном наблюдении: не стоит посещать "локальные" дороги, когда мы находимся достаточно далеко и от <tex>s</tex>, и от <tex>t</tex>
Пусть вершина <tex>v \in P</tex> лежит на кратчайшем пути <tex>s \rightsquigarrow t</tex>. Тогда, назовём <b>охватом (reach)</b> вершины <tex>v</tex> относительно <tex>P</tex> величину <tex>r(v,P) = min\{dist(s,v), dist(v,t)\}</tex>. Охватом вершины относительно всего графа назовём величину <tex>r(v) = \max\limits_{P} r(v,P)</tex> - максимум по всем кратчайшим путям, содержащим <tex>v</tex>.
Заметим, что вершины с большим охватом находятся вблизи середины некоторого длинного кратчайшего пути, то есть
* на больших автомагистралях вершины имеют большой охват
* на локальных перекрёстках (внутри населённых пунктов) вершины имеют маленький охват
=Ссылки=
