Структуры данных и алгоритмы (1021739), страница 76
Текст из файла (страница 76)
10.11,а сначала выбирается ребро (d, e), поскольку оно является кратчайшим, имея длину 3. Затем рассматриваются ребра (Ь, с), (а, Ь) и (e, f) — длинавсех этих ребер равна 5. В каком порядке они будут рассмотрены, значения не имеет — все они удовлетворяют условиям для выбора, и мы должны выбрать их, еслисобираемся строго следовать "жадному методу". Следующим кратчайшим ребром является ребро (а, с), длина которого равна 7.08. Однако это ребро может образоватьцикл с ребрами (а, Ь) и (Ь, с), поэтому принимаем решение отвергнуть его. Затем потой же причине отвергаем ребро (d, f). Далее надо рассмотреть ребро (Ь, е), но еготакже придется отвергнуть, поскольку оно повышает степени вершин Ь и е до трех ине образует маршрут с теми ребрами, которые уже о.тобраны.
Точно так же отвергается ребро (b, d). Затем рассматриваем ребро (с, а) и принимаем его. Итак, уже образовался путь а —» Ь — > с — > d - » e - > / , и, завершая маршрут, выбираем ребро (a, f). Врезультате получаем маршрут, показанный на рис. 10.11,6. Он по своей"оптимальности" находится на четвертом месте среди всех возможных маршрутов;его стоимость всего лишь на 4% больше стоимости оптимального маршрута.10.4. Поиск с возвратомИногда приходится иметь дело с задачей поиска оптимального решения, когда невозможно применить ни один из известных методов, способных помочь отыскать оптимальный вариант решения, и остается прибегнуть к последнему средству — полномуперебору. Этот раздел посвящен систематическому описанию метода полного перебора,называемого поиском с возвратом, а также метода, называемого альфа-бета отсечением,который зачастую позволяет существенно сократить объем операций поиска.Рассмотрим какую-либо игру с участием двух игроков, например шахматы, шашкиили "крестики-нолики".
Игроки попеременно делают ходы, и состояние игры отражаетсясоответствующим положением на доске. Допустим, что есть конечное число позиций надоске и в игре предусмотрено определенное "правило остановки", являющееся критериемее завершения.
С каждой такой игрой можно ассоциировать дерево, называемое деревом1Степенью вершины называется количество ребер, инцидентных этой вершине. — Прим. ред.10.4. ПОИСК С ВОЗВРАТОМ291игры. Каждый узел такого дерева представляет определенную позицию на доске. Начальная позиция соответствует корню дерева. Если позиция х ассоциируется с узлом п, тогдапотомки узла п соответствуют совокупности допустимых ходов из позиции л;, и с каждымпотомком ассоциируется соответствующая результирующая позиция на доске.
Например,на рис. 10.12 показана часть дерева для игры в "крестики-нолики".Ход игрока XХод игрока XХод игрока ОХод игрока XXоXXXXоX00 0 00XX00 X 0-1X0 XXX00 X0оО XОXX0|XОX0 X 0ОиX0 X00 X01Рис. 10.12. Часть дерева игры в "крестики-нолики"Листья этого дерева соответствуют таким позициям на доске, из которых невозможно сделать ход, — то ли потому, что кто-то из игроков уже одержал победу, то липотому, что все клетки заполнены и игра закончилась вничью. Каждому узлу деревасоответствует определенная цена. Сначала назначается цены листьям.
Допустим, речьидет об игре в "крестики—нолики". В таком случае листу назначается цена —1, 0 или 1в зависимости от того, соответствует ли данной позиции проигрыш, ничья или выигрыш игрока 1 (который ставит "крестики").Эти цены распространяются вверх по дереву в соответствии со следующим правилом. Если какой-либо узел соответствует такой позиции, из которой должен сделатьход игрок 1, тогда соответствующая цена является максимальной среди цен потомковданного узла. При этом предполагаем, что игрок 1 сделает самый выгодный для себяход, т.е. такой, который принесет ему самый ценный результат.
Если же узел соответствует ходу игрока 2, тогда соответствующая цена является минимальной среди ценпотомков данного узла. При этом мы предполагаем, что игрок 2 также сделает самыйвыгодный для себя ход, т.е. такой, который при самом благоприятном исходе приведетк проигрышу игрока 1, а при менее предпочтительном исходе — к ничьей.Пример 10.6. На рис. 10.12 показаны цены позиций в игре "крестики-нолики".Листьям, которые приносят выигрыш для игрока О (который рисует "нолики"), назначается цена -1; листьям, которые приносят ничью, назначается цена О; а листь292ГЛАВА 10. МЕТОДЫ РАЗРАБОТКИ АЛГОРИТМОВям, которые приносят выигрыш для игрока X (который рисует "крестики"), назначается цена +1.
Затем продвигаемся вверх по дереву. На уровне 8, где остается только одна пустая клетка, и предстоит ход игроку X, ценой для неразрешенных позиций является "максимум" из одного потомка на уровне 9.На уровне 7, где предстоит ход игроку О, и имеются два варианта решения, вкачестве цены для внутреннего узла принимаем минимальную из цен его потомков.
Крайняя слева позиция на уровне 7 представляет собой лист и имеет цену 1,поскольку она является выигрышем для X. Вторая позиция на уровне 7 имеет цену min(0, -1) = -1, тогда как третья имеет цену min(0, 1) = 0. Одна позиция, показанная на уровне 6 (на этом уровне предстоит ход игроку X), имеет ценутах(1, -1, 0) = 1. Это означает, что для обеспечения выигрыша игроку X нужносделать определенный выбор и в этом случае выигрыш последует немедленно. ПОбратите внимание: если цена корня равняется 1, то выигрышная стратегия находится в руках игрока 1. Действительно, когда наступает его очередь ходить, он гарантирован, что может выбрать ход, который приведет к позиции, имеющей цену 1.Когда же наступает очередь игрока 2 делать свой ход, ему не остается ничего иного,как выбрать ход, ведущий к все той же позиции с ценой 1, что для него означаетпроигрыш.
Тот факт, что игра считается завершившейся, гарантирует в конечномсчете победу первого игрока. Если же цена корня равняется О, как в случае игры в"крестики-нолики", тогда ни один из игроков не располагает выигрышной стратегией и может гарантировать себе лишь ничью, если будет играть без ошибок. Если жецена корня равняется -1, то выигрышная стратегия находится в руках игрока 2.Функции выигрышаИдею дерева игры, узлы которого имеют цену -1, 0 или 1, можно обобщить на деревья, листьям которых присваиваются любые числа (такое число называется выигрышем),выполняющие роль цены игры. Для оценивания внутренних узлов применяются те жеправила: взять максимум среди потомков на тех уровнях, где предстоит сделать ход игроку 1, и минимум среди потомков на тех уровнях, где предстоит сделать ход игроку 2.В качестве примера, где удобно применить концепцию выигрышей, рассмотримсложную игру (например, шахматы), в которой дерево игры, являясь, в принципе,конечным, столь огромно, что любые попытки оценить его по методу "снизу вверх"обречены на неудачу.
Любые шахматные программы действуют, в сущности, путемпостроения для каждой промежуточной позиции на шахматной доске дерева игры.Корнем этого дерева является текущая позиция; корень распространяется вниз нанесколько уровней. Точное количество уровней зависит от быстродействия конкретного компьютера. Когда большинство листьев дерева проявляют "неоднозначность"(т.е. не ведут ни к выигрышу, ни к ничьей, ни к проигрышу), каждая программа использует определенную функцию позиций на доске, которая пытается оценить вероятность выигрыша компьютера в этой позиции. Например, на такой оценке в значительной мере сказывается наличие у одной из сторон материального перевеса и такиефакторы, как прочность защиты королей.
Используя подобную функцию выигрыша,компьютер может оценить вероятность выигрыша после выполнения им каждого извозможных очередных ходов (в предположении, что игра каждой из сторон будетпроходить по оптимальному сценарию) и выбрать ход с наивысшим выигрышем.11Ниже перечислен ряд других правил, в соответствии с которыми действуют хорошиешахматные программы:1. Использование эвристик, чтобы исключить из рассмотрения определенные ходы, которыевряд ли можно считать хорошими. Это помогает увеличить количество просматриваемыхуровней дерева за фиксированное время.2. Распространение "цепочек взятия", которые представляют собой последовательности ходов,сопровождающиеся взятием фигур противника, за пределы последнего уровня, до которогообычно распространяется дерево. Это помогает более точно оценить относительную материальную силу позиций.3.
Сокращение поиска на дереве методом альфа-бета отсечения (см. дальше в этом разделе).10.4. ПОИСК С ВОЗВРАТОМ293Реализация поиска с возвратомДопустим, что заданы правила некоторой игры,1 т.е. допустимые ходы и правилазавершения игры. Мы хотим построить дерево этой игры и оценить его корень. Этодерево можно построить обычным способом, а затем совершить обход его узлов в обратном порядке.
Такой обход в обратном порядке гарантирует, что мы попадем навнутренний узел п только после обхода всех его потомков, в результате чего можнооценить узел л, найдя максимум или минимум (в зависимости от конкретной ситуации) значений всех его потомков.Объем памяти, который требуется для хранения такого дерева, может оказаться недопустимо большим, но, если соблюдать определенные меры предосторожности, можнообойтись хранением в памяти в любой заданный момент времени лишь одного пути — откорня к тому или иному узлу. В листинге 10.3 показана рекурсивная программа search(поиск), которая выполняет обход дерева с помощью последовательности рекурсивныхвызовов этой процедуры.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
