A* поиск

Оптимизация Дейкстры для поиска пути к конкретной цели: добавляем эвристическую функцию h(v) (оценка расстояния от v до цели), используем f(v) = g(v) + h(v) для приоритета (g(v) — реальное расстояние от старта). Требования к h: admissible (не переоценивает, h(v) ≤ истинное расстояние), consistent (h(u) ≤ cost(u,v) + h(v)). Эвристики: Euclidean distance (√[(x₁-x₂)²+(y₁-y₂)²]) для 2D grid, Manhattan distance (|x₁-x₂|+|y₁-y₂|) для grid с 4 направлениями. Применение: игры (pathfinding), навигация (Google Maps), роботы