Кратчайший маршрут навигатора, победная стратегия в игре — всё это задачи на графах. Познакомимся с ними.
Чему ты научишься. находить кратчайший путь в графе алгоритмом Дейкстры и разбираться в выигрышных стратегиях по дереву игры.
Кратчайший путь: алгоритм Дейкстры
Частая задача — найти кратчайший путь между вершинами взвешенного графа (например, самый быстрый маршрут по карте). Её решает алгоритм Дейкстры: он шаг за шагом находит кратчайшие расстояния от начальной вершины до всех остальных, каждый раз выбирая ближайшую ещё не обработанную вершину.
КРАТЧАЙШИЙ ПУТЬ (веса рёбер — расстояния):
2 3
(A)─────(B)─────(D)
│ ╱
5 │ 1 ╱
└──(C)──┘
A→B→D = 2+3 = 5 A→C→D = 5+1 = 6
кратчайший путь A→D = 5 (через B)
Теория игр
Игры с полной информацией (например, ним) моделируют деревом игры — все возможные ходы. Позицию называют выигрышной, если у игрока есть ход в проигрышную для соперника позицию, и проигрышной — если любой ход ведёт соперника к выигрышу. Так находят выигрышную стратегию.
Контрольный вопрос. Алгоритм поиска кратчайшего пути между вершинами взвешенного графа называется алгоритмом…
Подсказка: Кратчайшие расстояния.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Задача найти самый короткий маршрут между двумя вершинами взвешенного графа называется задачей поиска ______ пути. Впиши слово.
Подсказка: Противоположность самому длинному пути.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Что нужно знать про рёбра графа, чтобы вообще можно было искать кратчайший путь между вершинами?
Подсказка: Без этого нельзя сравнить, какой путь короче.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Позицию в игре называют ______, если у игрока есть ход в проигрышную для соперника позицию. Впиши слово.
Подсказка: Противоположность проигрышной позиции.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Позицию в игре называют проигрышной, если…
Подсказка: Как ни ходи из этой позиции — соперник в итоге победит.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Все возможные ходы в игре с полной информацией моделируют…
Подсказка: От каждой позиции — ветви ходов.
Онлайн-проверка ответа появится позже
Контрольный вопрос. В графе A→B→D веса рёбер 2 и 3, а путь A→C→D весит 6. Чему равен кратчайший путь из A в D? Впиши число.
Подсказка: Путь A→B→D состоит из двух рёбер весом 2 и 3 — сложи их и сравни с весом 6.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Алгоритм Дейкстры на каждом шаге выбирает…
Подсказка: Жадный принцип: сначала обрабатываем то, что ближе всего.
Онлайн-проверка ответа появится позже
Контрольный вопрос. В игре у игрока есть два хода: один ведёт в выигрышную для соперника позицию, другой — в проигрышную для соперника. Какой ход стоит выбрать?
Подсказка: Цель — поставить СОПЕРНИКА в невыгодное положение.
Онлайн-проверка ответа появится позже
Задание. Построй взвешенный граф минимум из 4 вершин и 5 рёбер (например, схема дорог между городами с расстояниями).
1) Опиши свой граф: вершины и веса всех рёбер.
2) Найди (посчитай вручную) кратчайший путь между двумя выбранными вершинами, перечислив хотя бы 2 возможных маршрута и сравнив их суммарный вес.
3) Объясни, какую вершину алгоритм Дейкстры обработает первой из начальной точки и почему.Подсказка: Сравнивай суммы весов рёбер по разным маршрутам; алгоритм Дейкстры всегда сначала обрабатывает ближайшую необработанную вершину.
Онлайн-проверка ответа появится позже
Итог. На графах решают серьёзные задачи. Кратчайший путь между вершинами взвешенного графа находит алгоритм Дейкстры. Игры с полной информацией моделируют деревом игры и по нему определяют выигрышные и проигрышные позиции, находя выигрышную стратегию.
Что дальше
Особая и важнейшая модель данных — база данных. О ней следующий урок.