🌐 Графы используются везде, где есть:

• Навигация — Google Maps, Яндекс.Карты
• Социальные сети — кратчайший путь между пользователями
• Игровой ИИ — поиск пути персонажа
• Сетевая маршрутизация — как пакеты данных путешествуют по интернету
• Логистика — оптимизация цепочек поставок
• Анализ данных — поиск зависимостей в больших данных

🎮 Пример из жизни

Ты планируешь цепочку стримов на неделю. Каждый день ты можешь выбрать одну из нескольких игр. Сколько различных последовательностей игр ты можешь создать за неделю?

Это типичная задача на дерево решений. Каждый узел дерева — это день, каждая ветка — выбор игры, листья дерева — возможные комбинации.

⚠️ Важный момент

Этот метод хорош для подсчёта вариантов, но не всегда даёт самый быстрый способ найти оптимальный путь.

❓ Когда использовать?

Когда нужно найти кратчайший путь от одной вершины до всех остальных.

🎯 Суть алгоритма

Представь, что ты исследуешь карту в RPG, где каждая локация соединена с другими дорогами разной длины. Ты начинаешь в стартовой точке и постепенно «открываешь» ближайшие локации, всё время запоминая кратчайший известный путь до каждой из них.

💚 Ключевая идея

Мы всегда двигаемся от «ближайших» вершин к «дальним», при этом гарантируя, что найденное расстояние — действительно кратчайшее.

🎮 Пример из программирования

Алгоритм Дейкстры используется в игровых движках для поиска пути врагов к игроку. Вес ребра может означать не только расстояние, но и «опасность» маршрута или затраты энергии.

⚠️ Важное ограничение

Алгоритм Дейкстры не работает с отрицательными весами рёбер! Для таких случаев используют алгоритм Беллмана-Форда.

📋 Решение:

1. Создаём таблицу, где каждая ячейка соответствует клетке лабиринта
2. Заполняем таблицу снизу вверх и слева направо
3. Для каждой ячейки выбираем минимум из двух путей (снизу или слева) и прибавляем штраф текущей ячейки

🎲 Что такое игра в математическом смысле?

Это не обязательно шахматы или крестики-нолики. Это любая ситуация, где:

1. Есть несколько участников (игроков)
2. У каждого есть варианты действий
3. Результат зависит от выбора всех участников
4. Интересы участников могут не совпадать

📜 Условия:

• Начальное состояние: 9 голов
• Ход: срубить 1, 2 или 3 головы
• Победа: срубить последнюю голову (довести до 0)
• Игроки: Алёша (первый) и Добрыня (второй)

✅ Вывод

Алёша выигрывает, если первым ходом срубит 1 голову (переведя Добрыню в позицию 8).

🎯 Выигрышная стратегия Алёши:

• Первый ход: срубить 1 голову (9 → 8)
• После любого хода Добрыни перевести его в позицию 4 (проигрышную)
• Далее на каждый ход Добрыни отвечать так, чтобы поддерживать проигрышные позиции для него

📜 Условия:

• Начальное состояние: S камней в куче (1 ≤ S ≤ 45)
• Ходы: +1, +2 или ×3
• Цель: довести до 46+ камней
• Игроки: Петя (первый), Ваня (второй)

Шаг 1: Выигрыш первым ходом

Петя может выиграть сразу, если S ≥ 16:

S ×3 ≥ 48 (для S ≥ 16)

Позиции 16–45 — выигрышные для Пети.

Шаг 2: Проигрышные позиции для Пети

Позиция S = 15:

15 + 1 = 16 (В для Вани)
15 + 2 = 17 (В для Вани)
15 × 3 = 45 (В для Вани)

Любой ход Пети переводит Ваню в выигрышную позицию. Значит, S = 15 — проигрышная для Пети.

Шаг 3: Выигрыш Пети вторым ходом

Если Петя может перевести Ваню в позицию 15, то после хода Вани Петя окажется в выигрышной позиции.

Как получить 15?

• 14 + 1 = 15 ✓
• 13 + 2 = 15 ✓
• 5 × 3 = 15 ✓

Позиции 5, 13, 14 — выигрышные для Пети (выигрыш вторым ходом).

Шаг 4: Проигрышная позиция для Пети

S = 12:

12 + 1 = 13 (В для Вани вторым ходом)
12 + 2 = 14 (В для Вани вторым ходом)
12 × 3 = 36 (В для Вани первым ходом)

Любой ход Пети приводит к выигрышу Вани. Значит, S = 12 — проигрышная для Пети.

💡 Важный паттерн

Заметь закономерность:

• Позиции, из которых можно попасть только в выигрышные — проигрышные
• Позиции, из которых можно попасть хотя бы в одну проигрышную — выигрышные

Это принцип минимакса: игрок выбирает ход, минимизирующий максимально возможный проигрыш.