Изменения

Эта эвристика хорошо работает, на дорожных графах, для которых верно следующее: как правило, кратчайший путь затрагивает небольшое количество локальных дорог, потом крупную автомагистраль и снова некоторое количество локальных дорог.

Сложности в выборе ориентиров:

* хороший ориентир для запроса <tex>s \rightsquigarrow t</tex> должен находиться "до" <tex>s</tex> (точно не будет общих рёбер на кратчайшем пути) или "за" <tex>t</tex> (чем острее угол, тем меньше отклонение от предварительно посчитанного кратчайшего пути до искомого)

Существуют различные алгоритмы выбора ориентиров:

[[Файл:planarLandmarks.jpg|right]]

Как следует из названия, ориентиры выбираются случайным образом

* разделим карту на <tex>k</tex> секторов одинаковой площади

* возьмём ориентиром наиболее удалённую точку от центра в каждом секторе

Такой способ подходит, только если граф имеет относительно правильную форму. На практике обычно используется оптимизированная версия этого алгоритма.

Этот алгоритм добавляет ориентиры по одному, глядя на вершины, которые плохо покрыты текущим набором ориентиров <tex>S</tex>.

Начиная с максимальной по размеру вершины, пойдём вниз по дереву <tex>T_{r}</tex> и найдём лист с максимальным размером. Примем его за новый ориентир.

Основным минусом избирательного метода является то, что первый ориентир выбирается случайным образом и выбор последующих ориентиров будет сильно зависеть от первоначального.