251
правка
Изменения
м
→ALT
[[Файл:ALT.jpg|right|frame|рис. 1]]
Будем использовать неравенство треугольника для нижних оценок пути (см. рис. 1). Пусть <tex>A</tex> — один из ориентиров, тогда:
*<tex>dist(v,w)\ge geqslant dist(A,w)-dist(A,v)</tex>,*<tex>dist(v,w)\ge geqslant dist(v,A)-dist(w,A)</tex>,*<tex>dist(v,w)\ge geqslant \max\{dist(A,w)-dist(A,v),dist(v,A)-dist(w,A)\}</tex>.
Эта эвристика хорошо работает, на дорожных графах, для которых верно следующее: как правило, кратчайший путь затрагивает небольшое количество локальных дорог, потом крупную автомагистраль и снова некоторое количество локальных дорог.
