Запрограммировать эвристическую функцию для алгоритма A *
Я должен запрограммировать робота, чтобы найти кратчайшее расстояние до места цели. На арене, которая содержит препятствия в случайных местах (заранее не известно).
Проблема в том, что мне дадут массив, представляющий сетку. В этой сетке 0 обозначает подвижное пространство, 1 — препятствие. Я должен запрограммировать его, чтобы найти кратчайший путь к выбранной цели, избегая всех препятствий (стен).
Является ли A * хорошим подходом к этой проблеме или есть даже лучший подход?
Решение
Как сказал @Vesper в комментариях, A * — это путь. Что касается эвристики …
Если ваш робот ограничен в движении влево / вправо и вверх / вниз, как правило, Манхэттен (или Такси или же L1) расстояние используется как эвристическая функция:
h(x,y) = |x - x_goal| + |y - y_goal|
Должно быть очевидно, что если нет никаких препятствий, то движение |x - x_goal| шаги вправо или влево, затем |y - y_goal| шаги вверх или вниз (или y, то x) не могут быть длиннее фактического кратчайшего пути к цели с препятствиями, поэтому эвристика допустима.
Если ваш робот может двигаться по диагонали, то манхэттенское расстояние больше не допустимо, поэтому вы можете использовать евклиды (или же L2) расстояние:
h(x,y) = sqrt( (x - x_goal)^2 + (y - y_goal)^2 )
Это прямое расстояние между двумя точками, которое никогда не будет длиннее любого другого возможного пути.
Это делает евклидово расстояние не только допустимым для диагонального движения (под любым углом), но также допустимым для случая выше, где движение ограничено направлениями x и y. Но в случае ограниченного перемещения расстояние на Манхэттене обычно дает длину пути, которая ближе к фактической длине пути, и, таким образом, может ускорить поиск путей и ускорить вычисления.
Другие решения