Дейкстра находит кратчайший путь от одной вершины до всех остальных. A* = Дейкстра + эвристика. Оба используются в навигаторах, играх и сетевой маршрутизации.
ФГОСФОПЕГЭ №1, №3
01
Алгоритм Дейкстры
Алгоритм
- Всем вершинам dist[v] = ∞, кроме start: dist[start] = 0.
- Извлечь вершину u с минимальным dist.
- Для соседа v: если dist[u] + w(u,v) < dist[v], обновить.
- Повторять, пока очередь не пуста.
Сложность
O((V+E)·log V) с приоритетной очередью.
02
A* — Дейкстра + эвристика
A* использует f(v) = g(v) + h(v):
- g(v) — реальный путь от start до v (фактическое расстояние).
- h(v) — эвристика (оценка от v до цели).
Три эвристики — за что отвечает каждая:
Манхэттен
Работает когда можно двигаться только по осям (без диагоналей).
Пример: робот на складе, пешеход по кварталам.
|dx| + |dy|Работает когда можно двигаться только по осям (без диагоналей).
Пример: робот на складе, пешеход по кварталам.
Евклидова
Для свободного движения по любому направлению.
Пример: дрон в воздухе, корабль в море.
√(dx²+dy²)Для свободного движения по любому направлению.
Пример: дрон в воздухе, корабль в море.
Чебышёва
Когда можно двигаться и по диагоналям (шахматный король).
Пример: персонаж в игре с 8 направлениями.
max(|dx|,|dy|)Когда можно двигаться и по диагоналям (шахматный король).
Пример: персонаж в игре с 8 направлениями.
Допустимая эвристика
Если h(v) ≤ реального расстояния, A* находит оптимальный путь.
03
Подсчёт путей в ДАГ
Задача как в ЕГЭ №3 — рандомизированный генератор
ДАГ: подсчёт путей
Нажмите «Новая задача»
04
A* на сетке
Сетка 20×20 · рандомные старт/финиш · препятствия
A* визуализатор: 20×20
Легенда
Старт (S)
Цель (G)
Open (очередь)
Closed (обработано)
Стена
Путь