Алгоритм A*: от теории к практике с подробными примерами кода на Python

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

Основная идея A* — вести поиск не вслепую, а с «пониманием» направления к цели. Для каждой рассматриваемой вершины (или узла) алгоритм вычисляет две стоимости:

• **g(n)** — стоимость пути от стартовой точки до текущего узла `n`. Это точная, известная стоимость.
• **h(n)** — эвристическая оценка стоимости от узла `n` до цели. Это предполагаемая, а не точная стоимость.

Итоговый приоритет узла определяется функцией **f(n) = g(n) + h(n)**. Алгоритм всегда расширяет узел с наименьшим значением `f(n)`, что гарантирует движение по наиболее перспективному пути.
Ключевым элементом является эвристика `h(n)`. Она должна быть допустимой (admissible), то есть никогда не переоценивать истинную стоимость достижения цели. Для сеток часто используют:

• **Манхэттенское расстояние**: `abs(x1 - x2) + abs(y1 - y2)`. Подходит для движения в 4-х направлениях (вверх, вниз, влево, вправо).
• **Евклидово расстояние**: `sqrt((x1 - x2)^2 + (y1 - y2)^2)`. Подходит для движения в любом направлении.
• **Расстояние Чебышева**: `max(abs(x1 - x2), abs(y1 - y2))`. Подходит для движения в 8-ми направлениях (включая диагонали).

Давайте реализуем A* для поиска пути на двумерной сетке с препятствиями. Мы создадим класс `Node` для представления каждой клетки.

```python
import heapq
import math

class Node:
 def __init__(self, x, y, walkable=True):
 self.x = x
 self.y = y
 self.walkable = walkable
 self.g = float('inf')  # Стоимость от старта
 self.h = 0  # Эвристическая оценка до цели
 self.f = float('inf')  # Общая стоимость: f = g + h
 self.parent = None  # Узел, из которого пришли

 def __lt__(self, other):
 # Необходимо для работы кучи (heapq). Сравниваем по f.
 return self.f < other.f

 def reset(self):
 self.g = float('inf')
 self.f = float('inf')
 self.parent = None
```

Теперь реализуем сам алгоритм A*.

```python
def a_star(start, goal, grid):
 # Сбрасываем значения узлов (если используется повторно)
 for row in grid:
 for node in row:
 node.reset()

 # Инициализируем стартовый узел
 start.g = 0
 start.h = heuristic(start, goal)
 start.f = start.g + start.h

 open_set = []
 heapq.heappush(open_set, start)
 closed_set = set()

 while open_set:
 current = heapq.heappop(open_set)

 if current == goal:
 # Путь найден, восстанавливаем его
 path = []
 while current:
 path.append((current.x, current.y))
 current = current.parent
 return path[::-1]  # Разворачиваем, чтобы путь был от start к goal

 closed_set.add((current.x, current.y))

 # Получаем соседей (в 4-х направлениях)
 for dx, dy in [(0,1), (1,0), (0,-1), (-1,0)]:
 nx, ny = current.x + dx, current.y + dy

 # Проверяем границы и проходимость
 if 0