Что такое алгоритм A *?

Алгоритм A * — это алгоритм поиска, который ищет кратчайший путь между начальным и конечным состоянием. Он используется в различных приложениях, таких как maps .

В maps алгоритм A * используется для вычисления кратчайшего расстояния между источником (начальное состояние) и пунктом назначения (конечное состояние).

Как это работает

Представьте себе квадратную сетку с множеством препятствий, разбросанных случайным образом. Предоставляются начальная и последняя ячейка. Цель состоит в том, чтобы достичь последней ячейки в кратчайшие сроки.

Здесь на помощь приходит A * алгоритм поиска:

Пояснение

Алгоритм A * имеет 3 параметра:

  • g: стоимость перехода из начальной ячейки в текущую. По сути, это сумма всех ячеек, которые были посещены с момента выхода из первой ячейки.
  • h: также известное как эвристическое значение , это оценочная стоимость перехода от текущей ячейки к последней. Фактическая стоимость не может быть рассчитана, пока не будет достигнута последняя ячейка. Следовательно, h — ориентировочная стоимость. Мы должны убедиться, что никогда не будет завышенной оценки стоимости.

  • f: это сумма g и h. Итак, f = g + h

Алгоритм принимает решения, принимая во внимание значение f. . Алгоритм выбирает ячейку с наименьшим значением f и переходит к этой ячейке. Этот процесс продолжается до тех пор, пока алгоритм не достигнет своей целевой ячейки.

Пример

Алгоритм A * также очень полезен при обходе графа. На следующих слайдах вы увидите, как алгоритм движется к достижению своего целевого состояния.

Предположим, у вас есть следующий график и вы применили к нему алгоритм A *. Начальный узел — это A , а целевой узел —

Чтобы объяснить обход графика выше, посмотрите слайды ниже.

На каждом шаге значение f пересчитывается с помощью сложение значений g и h. Узел с минимальным значением f выбирается для достижения целевого состояния. Обратите внимание на то, что узел B никогда не посещается.

1 из 4

Оцените статью
nanomode.ru
Добавить комментарий