D * lite: какую эвристическую функцию мне использовать?

Question

Я пытаюсь реализовать алгоритм поиска пути D * -Lite, как описано в статье 2002 года Кенига и Лихачева для навигационного графа на основе сетки.

Но я не вижу никаких эвристических функций в этой статье,Итак, какие функции я должен выбрать? Могу ли я использовать расстояние по прямой или расстояние до Манхэттена?

Answer 1

Это зависит от графика. Он должен удовлетворять равенству регулярного треугольника для допустимости эвристики, такой же, как для поиска A *. Евклидово расстояние будет хорошо работать в большинстве случаев. Отличие от A * состоит лишь в том, что расстояния вычисляются между текущим узлом, который мы ищем, и начальным узлом (поскольку лучший первый поиск выполняется от цели до начала для D * lite).