Лабораторная работа № 6
Деревья принятия решений
Цель работы: Ознакомиться с древовидными структурами данных, которые позволяют моделировать ситуации, где допустима множественность решений, а каждая ветвь представляет собой определенный выбор..
Краткие теоретические сведения
Деревья игры хорошо подходят для моделирования игры в шахматы, шашки, го и крестики-нолики. В них каждая ветвь отражает действие одного из игроков, другими словами, если в какой-то момент у игрока появится 10 возможных ходов, то и у дерева будет 10 возможных ветвей. Полное следование по дереву соответствует законченной игре. Как и все остальные деревья принятия решений, эти структуры растут очень быстро. Например, если в игре в шахматы состоялось 40 ходов (оба игрока совершили по 20) и на каждом этапе возможно в среднем около 30 вариантов действий, то общее количество прохождений по дереву будет 3040 ≈ 1,2х1059. Исчерпывающий компьютерный поиск, осуществляющий 1 млн. прохождений в секунду, продлится около 2,3х1044 лет. (Об оценке неповторяющихся шахматных партий можно прочитать по ссылке ru.wikipedia.org/wiki/Число_Шеннона.)
Минимакс — поисковая стратегия, при которой на каждом ходе игры пытаются минимизировать выгоду противника. Так, если есть два возможных хода, где первый позволяет выиграть вашему сопернику, а второй сулит проигрыш, следует предпочесть второй.
Уменьшить размеры дерева игры помогает сохранение заранее рассчитанных начальных шагов и реакций. Если вы уже провели предварительный поиск возможного первого хода, то программа может сделать его сразу, а не тратить время на просчеты.
Для всех игр, кроме, пожалуй, самых простых, деревья получаются довольно большими и не позволяют вести полный поиск. Именно поэтому нет возможности узнать, какой конкретно ход приведет к лучшему решению. В таких ситуациях значение для шага определяют с помощью эвристики.
Эвристика — это алгоритм, который находит возможный хороший результат, но не гарантирует, что тот будет наилучшим. Она не осуществляет поиск по всему дереву игры, но помогает сформулировать правила для принятия решения — какие части дерева нужно пропустить, а какие заслуживают особого внимания. Один из видов игровой эвристики — поиск шаблонных позиций на доске. Например, некоторые шахматные игроки пользуются негласным правилом: «Когда побеждаешь, меняй беспощадно». Это значит следующее: если у вас есть преимущество и вы можете обменяться равнозначными фигурами — сделайте это. Подобным образом вам удастся укрепить свои шансы на победу и уменьшить дерево игры, что, в свою очередь, облегчит поиск по нему в будущем. К шаблонам также относятся длинная последовательность обменов, рокировка и ход, представляющий угрозу нескольким фигурам, королю или ферзю, вскрытый шах, превращение пешки и ее взятие на проходе и т.д.
В игре с помощью дерева выбирают наилучший ход. В общем случае это выглядит как поиск самого оптимального пути по дереву. Подобным образом можно смоделировать и некоторые другие процессы принятия решений.
Такие задачи, как задача о разбиении, зачастую принимают две формы: в первой устанавливается возможность того или иного решения, а во второй располагается лучшее. Применительно к вышеуказанному набору предметов первая форма должна определить, можно ли в принципе образовать две группы с равными суммарными весами, а вторая найти такое допустимое разделение, когда обе группы окажутся максимально близки по весу, — так называемая задача оптимизации. В одном случае требуется строгий ответ — да или нет, в другом предоставляется приближенное решение, поэтому оптимизационная версия в некотором смысле легче.
Самый простой способ исследовать дерево принятия решений — проследовать по всем его вершинам и найти лучший ответ к задаче, то есть провести исчерпывающий поиск. Следует отметить, что для этого само дерево строить не нужно, необходим лишь путь, который поможет определить, в каком месте структуры данных вы пребываете. Многие алгоритмы в таком случае используют рекурсию — она помогает выбирать ветви на разных уровнях, а сами вызовы отслеживают текущую позицию.
Метод ветвей и границ. Это более эффективный метод, чем исчерпывающий поиск. Когда алгоритм доходит до конца ветви, он рассчитывает лучший результат, который может достичь на данном пути. Если полученное значение не превосходит последнее найденное лучшее, ветвь игнорируется и поиска по ее поддереву не происходит. Иногда такой способ значительно экономит время.
Исчерпывающий поиск и метод ветвей и границ находят наилучшее возможное решение, но, к сожалению, работают только с относительно небольшими задачами. Для поиска в больших деревьях удобнее использовать эвристику. Она не обязательно найдет наилучший возможный ответ, но даст неплохую версию хотя бы для оптимизационной версии задачи. В следующих пунктах рассматриваются четыре эвристических метода применительно к задаче о разбиении.
Случайный поиск. Одна из наиболее простых эвристик для поиска по дереву решений - следование по случайным путям. В этом случае в каждой вершине выбирается произвольная ветвь. Пересмотрев достаточное их количество, можно найти относительно неплохое решение.
Усовершенствование путей. Предыдущий эвристический метод можно сделать более эффективным: начните с выбора произвольного пути, затем случайным образом определите элемент и переместите его из текущей группы в другую. Если это улучшит разбиение, продолжайте обмен, если нет, отмените действия и предпримите следующую попытку. Повторяйте процесс, пока усовершенствование остается возможным.
Имитация отжига. Это улучшенная версия усовершенствования путей. В ходе нее в исходное решение вначале вносятся большие изменения, а затем все меньшие и меньшие, пока алгоритм не достигнет нужной тестовой версии, которая и сравнивается с последним найденным лучшим решением. Идея имитации отжига заимствована из поведения молекул в охлаждающемся металле или минерале. Когда вещество нагревается слишком сильно, молекулы перемещаются быстро и беспорядочно. По мере снижения температуры это движение замедляется и формируются устойчивые структуры, которые благодаря излишкам энергии продолжают сливаться с другими образованиями, формируя более стабильные связи. Когда вещество полностью остывает, избыточная энергия, которая смогла бы спровоцировать структурные разрушения, сходит на нет. В результате, если процесс протекает достаточно медленно, образуется лишь несколько больших кристаллов с очень устойчивым соединением молекул.