Определение допустимой эвристики (координатный график)

Question

Я пытаюсь понять, как определить истинную стоимость координатного графа (h * (n)), чтобы определить допустимую эвристику.

В нормальном графике координат истинная стоимость должна быть от одной координаты к другой - расстояние Манхэттена (Предполагая, что движение ограничено соседними квадратами сетки)? Если да, то будет ли расстояние по прямой линии приемлемой эвристикой для такого рода проблем?

т.е. (0,1) до (21,35) MHD = 55 и SLD = 39,96 единиц

Если бы препятствия на пути (то есть формы, которые заставляют путь перенаправлять вокруг них) между координатами , будет ли Манхэттенская дистанция вместо «истинной стоимости» действительной в качестве допустимой эвристики (истинная стоимость должна быть подсчитана вручную, я думаю?)? SLD также должен быть допустимой эвристикой, но не был бы таким доминирующим, как MHD.

Итак, чтобы на графике координат была бы истинная стоимость MHD и действительной эвристикой SLD? И в координатном графе с препятствиями истинная стоимость, как правило, была бы равна = МГД?

Answer 1

Предположим, вы находитесь в мире сетки, где разрешены только разрешенные движения N,S,W,E (или адиаторные ячейки в целом) да.

Манхэттенский расстояние будет истинная стоимость (и даже самые лучшие эвристики!)

SLD бы, конечно, меньше, но также менее информативен, чем MHD, который представляет h*.

В случае, если на вашем пути есть препятствия MHD никогда не будет преувеличивать истинную стоимость цели, допустимо. Вы можете использовать его для решения проблемы, но, конечно, решение не будет таким же хорошим, как в случае отсутствия препятствий, с точки зрения расширения узла.

Это не выполняется, когда вы можете перемещаться по диагонали, но это совсем другая история.

Наконец, MHD доминирует над SLD для каждого состояния, таким образом, это лучшая эвристическая функция, поскольку они оба допустимы.