A * Поиск модификаций

Question

В листинге Википедии для A * search указано:

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

Однако впри этом я обнаружил, что получаю ошибочные результаты в иначе функциональной реализации поиска A *.Может кто-нибудь пролить свет на то, как можно сделать эту модификацию?

Answer 1

Убедитесь, что ваша эвристика соответствует следующему:

ч (х) <= д (х, у) + ч (у) </p>

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

Например, если вы находитесь в сетке и пытаетесь добраться от А до Б, обе точки на этой сетке. Хорошей эвристической функцией является евклидово расстояние между текущим местоположением и целью:

h (x) = sqrt [(crtX -goalX) ^ 2 + (crtY -goalY) ^ 2]

Эта эвристика не переоценивает из-за неравенства треугольника.

Подробнее о неравенстве треугольника: http://en.wikipedia.org/wiki/Triangle_inequality

Подробнее о евклидовом расстоянии: http://mathworld.wolfram.com/Distance.html