Краткое содержание: Параграф § 11 / Информатика 11 класс

Моделирование на графах: Основные концепции, Алгоритмы и Теория Игр

Данный раздел учебника освещает широкое применение графов как мощной информационной модели в различных областях, включая планирование логистики, проектирование сетей и микроэлектроники. Ключевая задача, решаемая с помощью графов, – это нахождение кратчайшего пути между заданными вершинами. Кратчайший путь может определяться как путь с минимальным числом рёбер (в невзвешенном графе) или путь с наименьшей суммой весов рёбер (во взвешенном графе).

Для определения кратчайшего пути используются следующие алгоритмы:

• Алгоритм построения дерева решений;
• Алгоритм Дейкстры: Применяется для поиска кратчайшего пути от одной начальной вершины до всех остальных вершин в графах с неотрицательными весами. Он работает итеративно, последовательно находя кратчайшие расстояния и обновляя метки вершин.
• Метод динамического программирования: Используется для задач, которые могут быть разбиты на последовательные этапы, где на каждом этапе принимается оптимальное решение для достижения конечной цели. Примером является задача о минимальном числе штрафных баллов в лабиринте.

Значительное внимание уделено теории игр, которая играет важную роль в решении задач экономики, социологии, биологии и искусственного интеллекта. Игра, как математическая модель, характеризуется следующими признаками:

• Наличие нескольких игроков;
• Неопределённость поведения игроков (наличие нескольких вариантов действий);
• Несовпадение интересов игроков;
• Взаимосвязанность поведения (результат каждого зависит от действий всех игроков);
• Наличие правил, известных всем игрокам.

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

Центральное понятие – выигрышная стратегия. Это правило, позволяющее игроку гарантированно победить, независимо от ходов противника. Игровые позиции классифицируются как выигрышные (В), если из них есть ход, ведущий в проигрышную позицию для противника, и проигрышные (П), если любой ход ведёт в выигрышную позицию для противника. В разделе подробно анализируются задачи с кучами камней, где победа определяется достижением определенного количества камней (\( \geq 46 \) или \( \geq 47 \)), а ходы включают \( +1 \), \( +2 \) или \( \times 3 \). Эти задачи демонстрируют построение дерева выигрышной стратегии и поиск начальных значений \( S \), при которых победа возможна первым или вторым ходом.