Разбор A* за 1 день: от теории к практической реализации на Python

Алгоритм A* (произносится как «А стар») — это краеугольный камень в мире поиска путей и искусственного интеллекта. Он находит кратчайший путь из точки А в точку Б, умно оценивая варианты, и применяется в навигационных системах, играх и робототехнике. Если у вас есть день на его освоение, эта статья проведет вас от базовой теории до рабочего кода, разложив всё по полочкам.

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

Сердце A* — это функция оценки F(n) для каждой рассматриваемой вершины (ноды). Она вычисляется как сумма двух величин: F(n) = G(n) + H(n). G(n) — это реальная стоимость пути от стартовой точки до текущей ноды n. H(n) — это эвристическая оценка стоимости от ноды n до цели. Вот где кроется магия: эвристика H(n) направляет алгоритм, не давая ему исследовать заведомо бесперспективные направления. Ключевое требование к эвристике — она должна быть допустимой (admissible), то есть никогда не переоценивать реальную стоимость достижения цели. Чаще всего используется манхэттенское расстояние (для сеток с движением в четырех направлениях) или евклидово расстояние.

Теперь представим, как алгоритм шагает. Он оперирует двумя списками: open list (открытый список) и closed list (закрытый список). Open list содержит ноды, которые предстоит исследовать, отсортированные по значению F(n). Closed list содержит уже обработанные ноды, чтобы не ходить по кругу. Алгоритм начинается со стартовой ноды в open list.

Шаг 1: Из open list извлекается нода с наименьшим F(n). Изначально это старт.
Шаг 2: Эта нода переносится в closed list.
Шаг 3: Для каждого соседа этой ноды (достижимого за один шаг) вычисляется его потенциальный новый G-стоимость. Если сосед уже в closed list, он игнорируется.
Шаг 4: Если сосед еще не в open list, он добавляется туда. Вычисляется его F, G, H, а также записывается ссылка на родительскую ноду (откуда мы пришли).
Шаг 5: Если сосед уже в open list, проверяется: не является ли новый путь до него короче (с меньшим G)? Если да, то обновляются его G, F и родитель.
Шаг 6: Алгоритм повторяет шаги 1-5, пока целевая нода не будет добавлена в closed list (путь найден!) или пока open list не опустеет (пути нет).

Давайте перейдем от псевдокода к реальному Python. Создадим простой лабиринт 5x5, где 0 — проходимая клетка, а 1 — стена.

Сначала определим класс для ноды:
class Node:
 def __init__(self, parent=None, position=None):
 self.parent = parent
 self.position = position
 self.g = 0  # стоимость от старта
 self.h = 0  # эвристическая стоимость до цели
 self.f = 0  # сумма g + h

 def __eq__(self, other):
 return self.position == other.position

Теперь реализуем функцию A*. Для эвристики используем манхэттенское расстояние.
def astar(maze, start, end):
 start_node = Node(None, start)
 end_node = Node(None, end)
 open_list = []
 closed_list = []
 open_list.append(start_node)

 while open_list:
 current_node = open_list[0]
 current_index = 0
 for index, item in enumerate(open_list):
 if item.f < current_node.f:
 current_node = item
 current_index = index

 open_list.pop(current_index)
 closed_list.append(current_node)

 if current_node == end_node:
 path = []
 current = current_node
 while current is not None:
 path.append(current.position)
 current = current.parent
 return path[::-1]  # возвращаем путь от старта к цели

 children = []
 for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0)]:  # соседи по горизонтали/вертикали
 node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])
 if (node_position[0] > (len(maze) - 1) or node_position[0] < 0 or
 node_position[1] > (len(maze[len(maze)-1]) -1) or node_position[1] < 0):
 continue  # вышли за границы лабиринта
 if maze[node_position[0]][node_position[1]] != 0:
 continue  # наткнулись на стену
 new_node = Node(current_node, node_position)
 children.append(new_node)

 for child in children:
 if child in closed_list:
 continue
 child.g = current_node.g + 1
 child.h = ((child.position[0] - end_node.position[0]) ** 2) + ((child.position[1] - end_node.position[1]) ** 2)  # евклидово расстояние для простоты
 child.f = child.g + child.h
 if len([open_node for open_node in open_list if child == open_node and child.g > open_node.g]) > 0:
 continue
 open_list.append(child)

 return None  # путь не найден

Теперь создадим лабиринт и вызовем функцию:
maze = [
 [0, 1, 0, 0, 0],
 [0, 1, 0, 1, 0],
 [0, 0, 0, 1, 0],
 [0, 1, 1, 1, 0],
 [0, 0, 0, 0, 0]
]
start = (0, 0)
end = (4, 4)
path = astar(maze, start, end)
print(path)  # Выведет путь в виде списка координат.

Это базовая реализация. В оставшееся время дня можно углубиться в оптимизацию: использовать приоритетную очередь (heapq) для open list вместо списка, что значительно ускорит поиск минимального F. Также можно поэкспериментировать с разными эвристиками или добавить диагональное движение.

Понимание A* открывает двери к более сложным алгоритмам. Вы увидите его вариации в стратегических играх (Pathfinding), в системах GPS-навигации и даже в AI для решения головоломок. Потратив один день на его разбор и написание кода, вы не просто выучите алгоритм, а приобретете мощный инструмент для решения широкого класса задач поиска.