В статье this, в которой объясняется алгоритм A *, говорится, что для этой задачи (нахождения кратчайшего расстояния между двумя точками, где есть стена как препятствие), расстояние Манхэттена недопустимо. См. this
Почему это? Означает ли он завышение расстояния в любом случае? Если да, то когда?Почему этот манхэттенский эвристический недопустимый?
Вот кусок из aStarLibrary.bb (по ссылкам с вашей ссылке)
; Выяснить его G стоимость Если Abs (а-parentXval) = 1 и Abs (б-parentYVal) = 1 Тогда addedGCost = 14; стоимость будет диагональных квадратов
Else
addedGCost = 10; стоимость будет недиагональных квадратов
End If Gcost (а, Ь) = Gcost (parentXval, parentYVal) + addedGCost
;Figure out its H and F costs and parent
Hcost(openList(m)) = 10*(Abs(a - targetx) + Abs(b - targety)) ; record the H cost of the new square
Эвристический (Hcost) для перемещения от (0, 0) до (1,1) будет 10 * (1 + 1) = 20. GCost (стоимость хода) рассматривает это одно диагональное перемещение стоимость 14. Да, это чрезмерная оценка.
Да, в некоторых случаях это переоценивает. Я думаю, что это, вероятно, виноват коэффициент «10». – keyser