Главная Промышленная автоматика.

Реализация поиска с возвратом

Допустим, что заданы правила некоторой игры, т.е. допустимые ходы и правила завершения игры. Мы хотим построить дерево этой игры и оценить его корень. Это дерево можно построить обычным способом, а затем совершить обход его узлов в обратном порядке. Такой обход в обратном порядке гарантирует, что мы попадем на внутренний узел я только после обхода всех его потомков, в результате чего можно оценить узел л, найдя максимум или минимум (в зависимости от конкретной ситуации) значений всех его потомков.

Обьем памяти, который требуется для хранения такого дерева, может оказаться недопустимо большим, но, если соблюдать определенные меры предосторожности, можно обойтись хранением в памяти в любой заданный момент времени лишь одного пути - от корня к тому или иному узлу. В листинге 10.3 показана рекурсивная программа search (поиск), которая выполняет обход дерева с помошью последовательности рекурсивных вызовов этой процедуры. Эта программа предполагает выполнение следующих условий.

1. Выигрыши являются действительными числами из конечного интервала, например от -1 до -i-1.

2. Константа о» больше, чем любой положительный выигрыш, а -о» - меньше, чем любой отрицательный выигрыш.

3. Тип данных modetype (тип режима) определяется следуюшим образом:

type

modetype = <MIN, MAX)

4. Предусмотрен тип данных boardtype (тип игровой доски), который определяется способом, подходящим для представления позиций на игровой доске.

5. Предусмотрена функция payoff (выигрыш), которая вычисляет выигрыш для любой позиции, которая является листом.

Листинг 10.3. Рекурсивная программа поиска с возвратом

function search ( В: boardtype,- mode: modetype) : real;

{ оценивает и возвращает выигрыш для позиции В в предположении, что следующим должен ходить игрок 1 (mode = МАХ) или игрок 2 (mode = MIN) }

С: boardtype; { сын позиции В }

value: real; { для временного хранения минимального или максимального значения }

begin

(1) if В является листом then

(2) return(payoff(В)) else begin

(3) if mode = MAX then

(4) value: = -«« else

(5) value := о»;

(6) for для каждого сына С позиции В do

(7) if mode = MAX then

(8) value:= max(vaiue, search(C, MIN)) else

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



(9) value:= min(vaiue, searchiC, MAX) ) ;

(10) return(value) end

end,- { search }

Можно рассмотреть еще один вариант реализации поиска с возвратом. В этом варианте используется нерекурсивная программа, которая поддерживает стек позиций, соответствующих последовательности вызовов функции search. При создании такой программы можно использовать методы, рассмотренные в разделе 2.6.

Альфа-бета отсечение

Одно простое условие позволяет нам избавиться от рассмотрения значительной части типичного дерева игры. Вернемся к эскизу программы, представленному в листинге 10.3. Цикл for в строке (6) может проигнорировать определенных сыновей - нередко довольно больщое их число. Допустим, мы рассматриваем узел п, показанный на рис. 10.13, и уже определили, что цена Ci первого из сыновей узла я равняется 20. Поскольку узел я находится в режиме МАХ (т.е. ход 1-го игрока), то его значение не меньще 20. Допустим теперь, что, продолжая поиск, мы нащди, что у сына сг есть потомок d с выигрышем 15. Поскольку узел Сг находится в режиме MIN (т.е. ход 2-го игрока), то значение узла Сг не может быть больще 15. Таким образом, какое бы ни было значение узла Сг, оно не может влиять на цену узла я и любого предка узла га.

Режим МАХ


Рис. 10.13. Отсечение потомков узла

Таким образом, в ситуации, показанной на рис. 10.13, можно проигнорировать рассмотрение тех потомков узла Сг, которые мы еще не рассматривали. Общее правило пропуска или "отсечения" узлов связано с понятием конечных и ориентировочных значений для узлов. Конечное значение - это то, что мы просто называем "значением" (выигрышем). Ориентировочное значение - это верхний предел значений узлов в режиме MIN или нижний предел значений узлов в режиме МАХ. Ниже перечислены правила вычисления конечных и ориентировочных значений.

1. Если мы уже рассмотрели или отсекли всех потомков узла га, сделать ориентировочное значение узла га конечным значением.

2. Если ориентировочное значение узла га в режиме МАХ равно Vi, а конечное значение одного из его потомков равняется Vj, тогда установить ориентировочное



значение узла п равным max(oi, 02). Если же узел п находится в режиме MIN, тогда ориентировочное значение узда п установить равным min(ii, 1)2).

Если р является узлом в режиме MIN, имеет родителя q (в режиме МАХ), а ориентировочные значения уздов р я q равняются Vi и Vz соответственно, причем "1 < "г, тогда можно отсечь всех нерассмотренных потомков узда р. Можно также отсечь нерассмотренных потомков узда р, если р является узлом в режиме МАХ, а q является, таким образом, узлом в режиме MIN, и 1)2 < vy.

Пример 10.7. Рассмотрим дерево, показанное на рис. 10.14. Полагая, что значения дистьев соответствуют значениям, указанным на рисунке, мы хотим вычислить значение корня. Начинаем обход дерева в обратном порядке. Достигнув у;?ла D, в соответствии с правилом (2) назначаем узду С ориентировочное значение 2, которое является конечным значение узда D. Просматриваем узел Е и возвращаемся в узел С, а затем переходим в узел В. В соответствии с правилом (1) конечное значение узда С равно 2, а ориентировочное значение узда 5-2. Обход далее продолжается вниз к узду G, а затем обратно в узел Е. Ориентировочное значение узда Е равно 6. В соответствии с правилом (3) можно отсечь узел И, поскольку ориентировочное значение узда Е уменьшиться не может и оно уже больше значения узда В, которое не может увеличиться.

Режим МАХ

Режим MIN

Режим МАХ


Рис. 10.14. Дерево игры

Продолжим пример. Для узда назначаем ориентировочное значение 2 и переходим к узду К. Для узда / назначается ориентировочное значение 8. Значение узда L не влияет на значение узда /. Для узда / назначается ориентировочное значение 8. Переходим в узел N, узду М назначается ориентировочное значение 5. Необходимо выполнить просмотр узда О, поскольку 5 (ориентировочное значение узда М) меньше, чем ориентировочное значение узда /. Далее пересматриваются ориентировочные значения уздов / и А. Переходим к узду R. Выполняется просмотр уздов Л и S, узду Р назначается ориентировочное значение 4. Просмотр узда Т и всех его потомков проводить не нужно, поскольку это может только понизить значение узда Р, которое уже и без того слишком низкое, чтобы повлиять на значение узда А. П

Метод ветвей и границ

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





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 [94] 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0035