Дискретные игры: стратегии, минимакс, Дейкстра, A*

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

← Вернуться к оглавлению
Alterna · глава 19
Дискретные игры: стратегии, минимакс, Дейкстра, A*
Фундамент для ЕГЭ №19, 20, 21 (игры) и №1 (графы).
Дискретные игры — задачи, где два игрока делают ходы по правилам, пока кто-то не выиграет. На ЕГЭ это №19, 20, 21 (стратегии). Главный приём:
анализ с конца
— помечаем проигрышные позиции (L) и выигрышные (W). Также в главе — алгоритм Дейкстры для кратчайшего пути (ЕГЭ №1).
ФГОС · 11 класс
ФОП · базовый
ЕГЭ №1, 19, 20, 21
19
Страницы главы
5 страниц с теорией, интерактивами и банком заданий.
19.1
Выигрышные позиции
Анализ с конца, L/W-разметка.
Игра с ИИ
«Камешки +1 или ×2». Мини-тест 5/50.
19.2
Дерево игры
Алгоритм минимакс с альфа-бета отсечением.
Визуализатор
для деревьев глубины 3.
20.3
Кратчайший путь
Алгоритмы Дейкстры и A*.
Визуализатор
пошагово на 6-вершинном графе.
19.4
Практикум
Банк 50+ заданий: ОГЭ + ЕГЭ №1,19-21,23 с разборами.
19.5
Экзамен-полигон
Квест 800 XP + тест 10 мин +
2 развёрнутых задачи
(игра + дерево).
🔗
Связи с другими главами
Глава 17 (Графы)
— ДАГ и поиск путей. Дейкстра работает на взвешенных графах.
Подсчёт путей в ДАГ
использует динамическое программирование — как и анализ игр с конца.
Глава 24
ДАГ, топсорт, подсчёт путей
. Дейкстра — расширение поиска кратчайшего пути на взвешенные графы. Формула dp[v] = Σdp[u] похожа на анализ с конца.
Глава 18
Алгебра логики
. Минимакс использует логические операции AND/OR при выборе хода. L-позиция = FALSE (проигрыш), W-позиция = TRUE (выигрыш).
Глава 25
Деревья, BST
. Дерево игры — такое же бинарное дерево, как BST. Листья = терминальные позиции. Обход inorder = вычисление минимакса.
ОГЭ/ЕГЭ связи
ОГЭ №4
— схемы, графы, пути
ЕГЭ №1
— Дейкстра (кратчайший путь)
ЕГЭ №3
— графы, поиск пути
ЕГЭ №19-21
— теория игр, анализ с конца
ЕГЭ №23
— системы логических уравнений (минимакс на деревьях)