Кратчайший путь: Дейкстра и A*

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 19 · страница 19.3
Кратчайший путь: Дейкстра и A*
Алгоритм Дейкстры и A* с эвристикой. Пошаговая визуализация на графе.
Дейкстра
находит кратчайший путь от одной вершины до всех остальных.
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²)
Для свободного движения по любому направлению.
Пример: дрон в воздухе, корабль в море.
Чебышёва
max(|dx|,|dy|)
Когда можно двигаться и по диагоналям (шахматный король).
Пример: персонаж в игре с 8 направлениями.
Допустимая эвристика
Если h(v) ≤ реального расстояния, A* находит оптимальный путь.
03
Подсчёт путей в ДАГ
Задача как в ЕГЭ №3 — рандомизированный генератор
🎲
ДАГ: подсчёт путей
Нажмите «Новая задача»
Ответ:
04
A* на сетке
Сетка 20×20 · рандомные старт/финиш · препятствия
🎯
A* визуализатор: 20×20
Эвристика
Легенда
Старт (S)
Цель (G)
Open (очередь)
Closed (обработано)
Стена
Путь
XP: 0
К praktike
Графовые алгоритмы (Дейкстра, A*) отрабатываются в
практикуме
и в
главе 24 (ДАГ)
.