Пошаговое руководство по внедрению алгоритма поиска * с примерами расчетов
Алгоритм поиска A* — это популярная техника поиска и прохождения графов, используемая в различных приложениях, таких как робототехника, разработка игр и маршрутизация сети. Он сочетает в себе функции поиска по единой стоимости и жадного поиска наилучшим образом, чтобы эффективно найти кратчайший путь от начального узла до целевого узла. Это руководство обеспечивает пошаговый процесс для реализации алгоритма A* с примерами вычислений для иллюстрации каждого этапа.
Понимание алгоритма A*
Алгоритм A* использует функцию затрат, f(n) = g(n) + h(n), где:
- g(n): Фактическая стоимость от начального узла до узла n.
- h(n): Эвристическая оценка стоимости от узла n до цели.
Алгоритм исследует узлы с наименьшим значением f(n), балансируя фактические и предполагаемые затраты для эффективного поиска оптимального пути.
Пошаговая реализация
Выполните следующие действия для реализации алгоритма A*:
1. Инициировать открытые и закрытые списки
Открытый список содержит узлы, подлежащие оценке, начиная с исходного узла.Закрытый список содержит узлы, которые уже оценены.
2.Выберите узел с наименьшим f(n)
Удалите этот узел из открытого списка и добавьте его в закрытый список.
3. генерировать соседние узлы
Вычислите g(n) и h(n) для каждого соседа. Если сосед не находится в открытом списке или имеет более низкий g(n), обновите его значения и установите его родительский узел на текущий узел.
4 Повторять до достижения цели
Продолжайте процесс до тех пор, пока узел цели не будет добавлен в закрытый список, что указывает на кратчайший путь.
Примерные расчеты
Рассмотрим простую сетку с начальным узлом A и целевым узлом G. Эвристическое h(n) — прямолинейное расстояние. Первоначальные расчеты следующие:
Начиная с узла A, g(A) = 0, h(A) = 4. F(A) = 4. Оцениваются соседние узлы B и C:
Для узла B: g(B) = g(A) + стоимость(A, B) = 0 + 1 = 1, h(B) = 3, f(B) = 4.
Для узла C: g(C) = 1, h(C) = 2, f(C) = 3. Узел C имеет наименьший f(n), поэтому он выбирается следующим.
Этот процесс продолжается, обновляя значения g, h и f, пока не будет достигнут целевой узел G с самым коротким идентифицированным путем.