Урок №11. Деревья. Дискретные игры двух игроков с полной информацией.
Дерево — одна из наиболее распространенных структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Узел — это элемент дерева, который может содержать значение, состояние или представление отдельной информационной структуры или самого дерева.
Каждый узел дерева имеет ноль или более узлов-потомков, которые располагаются ниже по дереву. Узел, не имеющий предков (самый верхний), называется корневым узлом. Узел, не имеющий дочерних элементов (самый нижний), называется листовым (терминальным) узлом. Узел, имеющий потомка, называется узлом-родителем относительно своего потомка (или узлом-предшественником, или старшим). Каждый узел дерева можно рассматривать как корневой узел поддерева, растущего из этого узла.
Для представления деревьев в памяти компьютера существуют разные способы. Общий способ изображает узлы как записи, расположенные в динамически выделяемой памяти с указателями на своих потомков, предков (или и тех и других), или как элементы массива, связанные между собой отношениями, определенными их позициями в массиве (например, двоичная куча).
Упорядоченные деревья являются наиболее распространенными среди древовидных структур. В упорядоченном дереве каждому из элементов соответствует порядковый номер: 1, 2, 3 и т. д. На рисунках упорядоченные братья-узлы представляются слева направо. Пример упорядоченного дерева — книга, которая имеет деление на разделы, темы и вопросы.
Поддеревом называется часть древообразной структуры данных, которая может быть представлена в виде отдельного дерева. Любой узел дерева T вместе со всеми его узлами-потомками является поддеревом дерева T. Для любого узла поддерева либо должен быть путь в корневой узел этого поддерева, либо сам узел должен являться корневым.
Деревья в информатике имеют много разных применений. Например:
- Деревья используются для организации индексов во многих современных СУБД. Индексы позволяют быстро находить данные по заданному ключу или условию.
- Деревья используются для структурирования (индексирования) информации на жестком диске. Деревья позволяют сократить количество обращений к диску при поиске нужного блока памяти.
- Деревья используются для создания деревьев решений. Деревья решений — это инструменты поддержки принятия решений, которые показывают возможные исходы и последствия различных выборов.
- Деревья используются для составления автоматизированных моделей прогнозирования, которые применяются в машинном обучении, добыче данных и статистике. Деревья позволяют анализировать большие объемы данных и выявлять закономерности и зависимости.
Операции над деревьями — это действия, которые можно выполнять с деревьями или их элементами. Например:
- Построение дерева — это процесс создания дерева из данных, соблюдая определенные правила упорядочивания или структурирования.
- Поиск узла с заданным значением ключа — это процесс нахождения узла в дереве, который содержит искомое значение или удовлетворяет заданному условию.
- Добавление узла в дерево — это процесс вставки нового узла в дерево таким образом, чтобы сохранить его свойства и упорядоченность.
- Удаление узла из дерева — это процесс извлечения узла из дерева и перестройки дерева таким образом, чтобы сохранить его свойства и упорядоченность.
- Обход дерева — это процесс посещения всех узлов дерева в определенном порядке. Существуют разные способы обхода дерева: префиксный, инфиксный и постфиксный.
Теория игр — это раздел науки, изучающий решение конфликтов между игроками и оптимальность их стратегий. Деревья в теории игр используются для представления игр с последовательными ходами, когда каждый игрок знает ходы, сделанные до него. Деревья позволяют визуально и аналитически оценить результаты выбора различных решений и прогнозировать исходы игры.
Вот один пример дерева в теории игр.
Представь, что ты играешь в игру с колесом, которое разделено на две области: белую и красную. Ты можешь выбрать одну из двух кнопок: сильное или легкое вращение. В белой области колесо останавливается с вероятностью 0,3, а в красной — с вероятностью 0,7. Твой выигрыш зависит от кнопки, которую ты нажал, и цвета области. Таблица выигрышей выглядит так:
Дерево решений для этой игры показано на рисунке ниже.
Дерево показывает твое действие (выбор кнопки), возможные исходы (цвет области), вероятности исходов (0,3 и 0,7) и твой выигрыш при каждом исходе. Анализ дерева помогает тебе выбрать оптимальную стратегию для себя.
Разберем еще один пример.
Выполни следующие задания. Во всех случаях объясни свой ответ.
- Укажи все значения числа S, при которых Коля может выиграть в один ход. Объясни, что найдены все нужные значения S, и укажи выигрывающие ходы.
- Укажи значение S, при котором Коля не может выиграть за один ход, но при любом ходе Коли Толя может выиграть своим первым ходом. Опиши выигрышную стратегию Толи.
Пример решения.
