algorithm
A * Pathfinding

Введение в A *

A * (звезда) - это алгоритм поиска, который используется для поиска пути от одного узла к другому. Таким образом, его можно сравнить с Breadth First Search , или с алгоритмом Дейкстры , или с глубиной первого поиска , или с помощью Best First Search. Алгоритм A * широко используется в поиске графов для повышения эффективности и точности, где предварительная обработка графа не является вариантом.

A * является специализацией Best First Search, в которой функция оценки f определяется определенным образом.

f (n) = g (n) + h (n) - минимальная стоимость с начального узла до целей, обусловленных движением мыслительного узла n .

g (n) - минимальная стоимость от начального узла до n .

h (n) - минимальная стоимость от n до ближайшей цели до n

A * - это информированный алгоритм поиска, и он всегда гарантирует наименьший путь (путь с минимальной стоимостью) в наименьшее возможное время (если используется допустимая эвристика ). Таким образом, он является полным и оптимальным . Следующая анимация демонстрирует A * search-

Решение 8-головоломок с использованием алгоритма A *

Определение проблемы :

8-головоломка - простая игра, состоящая из сетки 3 x 3 (содержащей 9 квадратов). Один из квадратов пуст. Объект состоит в том, чтобы перемещаться в квадраты в разные положения и иметь номера, отображаемые в «состоянии цели».

Учитывая начальное состояние игры с 8 играми и конечное состояние, которое нужно достичь, найдите наиболее рентабельный путь для достижения конечного состояния из исходного состояния.

Исходное состояние :

_ 1 3
4 2 5
7 8 6

Конечное состояние :

1 2 3
4 5 6
7 8 _

Предполагается эвристика :

Рассмотрим Манхэттенское расстояние между текущим и конечным состоянием как эвристику для этой постановки задачи.

h(n) = | x - p | + | y - q |
where x and y are cell co-ordinates in the current state
      p and q are cell co-ordinates in the final state

Общая функция затрат :

Таким образом, общая функция стоимости f(n) задается,

f(n) = g(n) + h(n), where g(n) is the cost required to reach the current state from given initial state

Решение проблемы :

Сначала мы находим эвристическое значение, необходимое для достижения конечного состояния из начального состояния. Функция стоимости, g (n) = 0, поскольку мы находимся в начальном состоянии

h(n) = 8

Вышеуказанное значение получается, так как 1 в текущем состоянии равно 1 горизонтальному расстоянию, чем 1 в конечном состоянии. То же самое касается 2 , 5 , 6 . _ 2 горизонтальных расстояния и 2 вертикальных расстояния. Таким образом, общее значение для h(n) равно 1 + 1 + 1 + 1 + 2 + 2 = 8. Общая стоимость f(n) равна 8 + 0 = 8.

Теперь, возможные состояния , которые могут быть достигнуты из начального состояния встречаются и случается , что мы можем либо двигаться _ вправо или вниз.

Таким образом, состояния, полученные после перемещения этих ходов, следующие:

1 _ 3    4 1 3
4 2 5    _ 2 5
7 8 6    7 8 6
 (1)      (2)

Опять же, общая функция стоимости вычисляется для этих состояний с использованием метода, описанного выше, и получается, что она равна 6 и 7 соответственно. Мы выбрали состояние с минимальной стоимостью, которая является состоянием (1). Следующие возможные шаги могут быть влево, вправо или влево. Мы не будем двигаться влево, как мы были ранее в этом состоянии. Таким образом, мы можем двигаться вправо или влево.

Снова мы находим состояния, полученные из (1).

1 3 _    1 2 3
4 2 5    4 _ 5
7 8 6    7 8 6
 (3)      (4)

(3) приводит к функции стоимости, равной 6, и (4) приводит к 4. Кроме того, мы рассмотрим (2), полученную до того, какая функция стоимости равна 7. Выбор минимального из них приводит к (4). Следующие возможные перемещения могут быть влево или вправо или влево. Мы получаем состояния:

1 2 3    1 2 3    1 2 3
_ 4 5    4 5 _    4 8 5
7 8 6    7 8 6    7 _ 6
 (5)      (6)      (7)

Мы получаем затраты, равные 5, 2 и 4 для (5), (6) и (7) соответственно. Кроме того, мы имеем предыдущие состояния (3) и (2) с 6 и 7 соответственно. Мы выбрали минимальное состояние затрат, которое равно (6). Следующие возможные шаги: Вверх, Вниз и ясно вниз приводят нас к окончательному состоянию, приводящему к значению эвристической функции, равному 0.

A * Прослеживание через лабиринт без препятствий

Предположим, у нас есть следующая сетка 4 на 4:

Предположим, что это лабиринт . Однако никаких препятствий нет. У нас есть только начальная точка (зеленый квадрат) и конечная точка (красный квадрат). Предположим также, что для перехода от зеленого к красному мы не можем двигаться по диагонали. Итак, начиная с зеленой площади, давайте посмотрим, на какие квадраты мы можем переместиться, и выделим их синим цветом:

Чтобы выбрать квадрат для перехода к следующему, нам нужно учитывать 2 эвристики:

1. Значение «g» - это то, как далеко этот узел находится от зеленого квадрата.
2. Значение «h» - это то, как далеко этот узел находится от красного квадрата.
3. Значение «f» - это сумма значения «g» и «h». Это окончательное число, которое указывает нам, к какому узлу нужно перейти.

Чтобы вычислить эти эвристики, это формула, которую мы будем использовать: distance = abs(from.x - to.x) + abs(from.y - to.y)

Это называется формулой «Манхэттен Дистанция» .

Вычислим значение «g» для синего квадрата сразу слева от зеленого квадрата: abs(3 - 2) + abs(2 - 2) = 1

Большой! У нас есть значение: 1. Теперь давайте попробуем вычислить значение «h»: abs(2 - 0) + abs(2 - 0) = 4

Отлично. Теперь давайте получим значение «f»: 1 + 4 = 5

Итак, окончательное значение для этого узла равно «5».

Давайте сделаем то же самое для всех остальных синих квадратов. Большое число в центре каждого квадрата - это значение «f», а число в левом верхнем углу - это значение «g», а число в правом верхнем углу - это значение «h»:

Мы вычислили значения g, h и f для всех синих узлов. Теперь, что мы выбираем?

Какое бы ни было наименьшее значение f.

Однако в этом случае мы имеем 2 узла с одинаковым значением f, 5. Как мы можем выбрать между ними?

Просто выберите либо наугад, либо установите приоритет. Обычно я предпочитаю иметь такой приоритет: «Вправо> Вверх> Вниз> Влево»

Один из узлов с значением f 5 принимает нас в направлении «Вниз», а другой берет нас «влево». Поскольку Down имеет более высокий приоритет, чем Left, мы выбираем квадрат, который берет нас «вниз».

Теперь я отмечаю узлы, для которых мы вычислили эвристику, но не переместились в оранжевый цвет и узел, выбранный нами как голубой:

Хорошо, теперь давайте рассчитаем ту же эвристику для узлов вокруг голубого узла:

Опять же, мы выбираем узел, идущий вниз от голубого узла, так как все параметры имеют одно и то же значение f:

Давайте вычислим эвристику для единственного соседа, который имеет голубой узел:

Хорошо, поскольку мы будем следовать той же схеме, которую мы придерживаемся:

Еще раз, давайте вычислим эвристику для соседа узла:

Перейдем туда:

Наконец, мы видим, что у нас есть квадрат победы рядом с нами, поэтому мы переезжаем туда, и мы закончили.