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