Если поиск A * с эвристическим евклидовым расстоянием допускает диагональные перемещения, будет ли он по-прежнему оптимальным?

Question

Так что, если у меня есть поиск A * в лабиринте 10х10 с 10 препятствиями, и я позволю себе диагональные перемещения внутри него, будет ли он по-прежнему оптимальным?

Мой ответ таков: он все равно будет оптимальным,и это потому, что Евклидово расстояние вычисляет расстояние по прямой линии между двумя точками, так что оно в любом случае пересекает пространство поиска по диагонали, так что я не думаю, что это будет иметь значение, или оно может даже улучшить его?Не уверен, правильно ли я думаю.

Answer 1

Это зависит от стоимости диагональных ходов.

Рассмотрим ситуацию равномерной стоимости : стоимость диагонального перемещения такая же, как и стоимость не диагональной ( Чебышеврасстояние ).

В этом случае расстояние между зеленой и красной точкой составляет 6.В общем:

def chebyshev_distance(node):
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return max(dx, dy)

, в то время как эвристическое евклидово расстояние:

def heuristic(node):
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return sqrt(dx * dx + dy * dy)

дает heuristic ≅ 6.71 и переоценивает стоимость пути, что приводит к недопустимой эвристике ( может ненайти оптимальный путь ).

В общем:

max (| d _x |, | d _y |) = | Макс |= sqrt (Макс ² ) ≤ sqrt (Макс ² + min ² ) = sqrt (d _x ² + d _y ² )