Ответ 1
Я просто попытаюсь переписать предыдущий ответ с более подробной информацией о том, почему он оптимален.
Алгоритм A *, взятый непосредственно из wikipedia,
function A*(start,goal)
closedset := the empty set // The set of nodes already evaluated.
openset := set containing the initial node // The set of tentative nodes to be evaluated.
came_from := the empty map // The map of navigated nodes.
g_score[start] := 0 // Distance from start along optimal path.
h_score[start] := heuristic_estimate_of_distance(start, goal)
f_score[start] := h_score[start] // Estimated total distance from start to goal through y.
while openset is not empty
x := the node in openset having the lowest f_score[] value
if x = goal
return reconstruct_path(came_from, came_from[goal])
remove x from openset
add x to closedset
foreach y in neighbor_nodes(x)
if y in closedset
continue
tentative_g_score := g_score[x] + dist_between(x,y)
if y not in openset
add y to openset
tentative_is_better := true
elseif tentative_g_score < g_score[y]
tentative_is_better := true
else
tentative_is_better := false
if tentative_is_better = true
came_from[y] := x
g_score[y] := tentative_g_score
h_score[y] := heuristic_estimate_of_distance(y, goal)
f_score[y] := g_score[y] + h_score[y]
return failure
function reconstruct_path(came_from, current_node)
if came_from[current_node] is set
p = reconstruct_path(came_from, came_from[current_node])
return (p + current_node)
else
return current_node
Итак, позвольте мне заполнить все подробности здесь.
heuristic_estimate_of_distance
- функция & Sigma; d (x i), где d (.) - расстояние Манхэттена каждого квадрата x i от его целевого состояния.
Итак, настройка
1 2 3
4 7 6
8 5
будет иметь heuristic_estimate_of_distance
1 + 2 + 1 = 4, так как каждый из 8,5 один вдали от своей позиции цели с d (.) = 1 и 7 равен 2 от его целевого состояния с d (7 ) = 2.
Набор узлов, которые ищет A *, определяется как начальная позиция, за которой следуют все возможные юридические позиции. Это означает, что начальная позиция x
такова, как указано выше:
x =
1 2 3
4 7 6
8 5
то функция neighbor_nodes(x)
создает два возможных юридических хода:
1 2 3
4 7
8 5 6
or
1 2 3
4 7 6
8 5
Функция dist_between(x,y)
определяется как число квадратных шагов, которые имели место для перехода из состояния x
в y
. Это в основном будет равным 1 в * всегда для целей вашего алгоритма.
closedset
и openset
являются специфичными для алгоритма A * и могут быть реализованы с использованием стандартных структур данных (приоритетные очереди, на которые я верю.) came_from
- используемая структура данных
для восстановления найденного решения с помощью функции reconstruct_path
, сведения о которой можно найти в википедии. Если вы не хотите помнить решение, вам не нужно это реализовывать.
Наконец, я рассмотрю вопрос об оптимальности. Рассмотрим выдержку из статьи A * wikipedia:
"Если эвристическая функция h допустима, что означает, что она никогда не переоценивает фактическую минимальную стоимость достижения цели, то A * сама допустима (или оптимальна), если мы не будем использовать замкнутое множество. Если замкнутое множество, то h также должно быть монотонным (или последовательным) для оптимального A *. Это означает, что для любой пары соседних узлов x и y, где d (x, y) обозначает длину ребра между ними, мы должны иметь: h (x) <= d (x, y) + h (y) "
Итак, достаточно показать, что наша эвристика допустима и монотонна. Для первого (допустимости) обратите внимание, что при любой конфигурации наша эвристика (сумма всех расстояний) оценивает, что каждый квадрат не ограничивается только юридическими движениями и может свободно перемещаться к своей позиции цели, что явно оптимистично оценивает, следовательно, наша эвристическая допустим (или он никогда не переоценивает, так как достижение позиции цели всегда будет занимать как минимум столько ходов, сколько эвристических оценок.)
Требование монотонности, сформулированное словами: "Эвристическая стоимость (расчетное расстояние до цели цели) любого node должна быть меньше или равна стоимости перехода на любой смежный node плюс эвристическая стоимость этого node."
В основном это предотвращает возможность отрицательных циклов, когда переход к несвязанному node может уменьшить расстояние до цели node больше, чем стоимость фактического перехода, что указывает на низкую эвристику.
Чтобы показать монотонность, это довольно просто в нашем случае. Любые смежные узлы x, y имеют d (x, y) = 1 по нашему определению d. Таким образом, нам нужно показать
h (x) <= h (y) + 1
что эквивалентно
h (x) - h (y) <= 1
что эквивалентно
& Sigma; d (x i) - & Sigma; d (y i) <= 1
что эквивалентно
& Sigma; d (x i) - d (y i) <= 1
Мы знаем по нашему определению neighbor_nodes(x)
, что два соседних узла x, y могут иметь не более чем положение одного квадрата, что означает, что в наших суммах член
d (x i) - d (y i) = 0
для всех, кроме 1 значения i. Скажем без ограничения общности, это верно для я = k. Кроме того, мы знаем, что при я = k node перемещалось не более одного места, поэтому его расстояние до состояние цели должно быть не более одного, чем в предыдущем состоянии, таким образом:
& Sigma; d (x i) - d (y i) = d (x k) - d (y k) <= 1
показывает монотонность. Это показывает, что нужно было показать, таким образом доказав, что этот алгоритм будет оптимальным (в нотации с большими О или асимптотическими способами).
Обратите внимание, что я показал оптимальность в терминах записи большого О, но есть еще много возможностей для игры с точки зрения эвристики. Вы можете добавить к нему дополнительные повороты, чтобы приблизиться к фактическому расстоянию до состояния цели, однако вы должны убедиться, что эвристика всегда недооценивается, иначе вы теряете оптимальность!