Структуры данных и алгоритмы (1021739), страница 77
Текст из файла (страница 77)
Эта программа предполагает выполнение следующих условий.1.Выигрыши являются действительными числами из конечного интервала, например от -1 до +1.2.Константа <*> больше, чем любой положительный выигрыш, а —ее — меньше, чемлюбой отрицательный выигрыш.3. Тип данных modetype (тип режима) определяется следующим образом:typemodetype = (MIN, MAX)4. Предусмотрен тип данных board type (тип игровой доски), который определяетсяспособом, подходящим для представления позиций на игровой доске.5. Предусмотрена функция payoff (выигрыш), которая вычисляет выигрыш длялюбой позиции, которая является листом.Листинг 10.3. Рекурсивная программа поиска с возвратом(1)(2)(3)(4)(5)(6)(7)(8)function search ( В: boardtype; mode: modetype): real;{ оценивает и возвращает выигрыш для позиции В в предположении,что следующим должен ходить игрок 1 (mode = МАХ)или игрок 2 (mode = MIN) }varС: boardtype; { сын позиции В }value: real; { для временного хранения минимального илимаксимального значения }beginif В является листом thenreturn(payoff(В))else beginif mode = MAX thenvalue: = -»°elsevalue := <*>;for для каждого сына С позиции В doif mode = MAX thenvalue:= max(value, search(C, MIN))else1He следует считать, что таким способом отыскиваются решения только для игр.
Как будет показано в последующих примерах, "игра" может на самом деле представлять решение тойили иной практической задачи.294ГЛАВА 10. МЕТОДЫ РАЗРАБОТКИ АЛГОРИТМОВ(9)(10)value:= min(value, search(C, M A X ) ) ;return(value)endend; { search }Можно рассмотреть еще один вариант реализации поиска с возвратом. В этом варианте используется нерекурсивная программа, которая поддерживает стек позиций,соответствующих последовательности вызовов функции search. При создании такойпрограммы можно использовать методы, рассмотренные в разделе 2.6.Альфа-бета отсечениеОдно простое условие позволяет нам избавиться от рассмотрения значительной части типичного дерева игры. Вернемся к эскизу программы, представленному в листинге 10.3.
Цикл for в строке (6) может проигнорировать определенных сыновей — нередко довольно большое их число. Допустим, мы рассматриваем узел п, показанный нарис. 10.13, и уже определили, что цена ct первого из сыновей узла п равняется 20. Поскольку узел п находится в режиме МАХ (т.е. ход 1-го игрока), то его значение неменьше 20.
Допустим теперь, что, продолжая поиск, мы нашли, что у сына с2 есть потомок d с выигрышем 15. Поскольку узел с2 находится в режиме MIN (т.е. ход 2-го игрока), то значение узла с2 не может быть больше 15. Таким образом, какое бы ни былозначение узла с2, оно не может влиять на цену узла п и любого предка узла га.Режим МАХРис. 10.13. Отсечение потомков узлаТаким образом, в ситуации, показанной на рис. 10.13, можно проигнорироватьрассмотрение тех потомков узла с2, которые мы еще не рассматривали. Общее правило пропуска или "отсечения" узлов связано с понятием конечных и ориентировочныхзначений для узлов.
Конечное значение — это то, что мы просто называем"значением" (выигрышем). Ориентировочное значение — это верхний предел значений узлов в режиме MIN или нижний предел значений узлов в режиме МАХ. Нижеперечислены правила вычисления конечных и ориентировочных значений.1.2.Если мы уже рассмотрели или отсекли всех потомков узла га, сделать ориентировочное значение узла га конечным значением.Если ориентировочное значение узла га в режиме МАХ равно v\, а конечное значение одного из его потомков равняется v2, тогда установить ориентировочное10.4. ПОИСК С ВОЗВРАТОМ295значение узла п равным max(t>1( v2).
Если же узел п находится в режиме MIN,тогда ориентировочное значение узла п установить равным min(u1( i>2).3. Если р является узлом в режиме MIN, имеет родителя q (в режиме МАХ), а ориентировочные значения узлов р и q равняются и г и v2 соответственно, причемУ! < и2, тогда можно отсечь всех нерассмотренных потомков узла р. Можно такжеотсечь нерассмотренных потомков узла р, если р является узлом в режиме МАХ,a q является, таким образом, узлом в режиме MIN, и и2 < иг.Пример 10.7. Рассмотрим дерево, показанное на рис.
10.14. Полагая, что значения листьев соответствуют значениям, указанным на рисунке, мы хотим вычислитьзначение корня. Начинаем обход дерева в обратном порядке. Достигнув у^ла D, в соответствии с правилом (2) назначаем узлу С ориентировочное значение 2, которое является конечным значение узла D.
Просматриваем узел Е и возвращаемся в узел С, азатем переходим в узел В. В соответствии с правилом (1) конечное значение узла Сравно 2, а ориентировочное значение узла В — 2. Обход далее продолжается вниз кузлу G, а затем обратно в узел F. Ориентировочное значение узла F равно 6. В соответствии с правилом (3) можно отсечь узел Н, поскольку ориентировочное значениеузла F уменьшиться не может и оно уже больше значения узла В, которое не можетувеличиться.Режим МАХРежим MINотсечьТРежим МАХ ( 2Рис.
10.14. Дерево игрыПродолжим пример. Для узла А назначаем ориентировочное значение 2 и переходим к узлу К. Для узла J назначается ориентировочное значение 8. Значение узла Lне влияет на значение узла J. Для узла / назначается ориентировочное значение 8.Переходим в узел N, узлу М назначается ориентировочное значение 5. Необходимовыполнить просмотр узла О, поскольку 5 (ориентировочное значение узла М) меньше, чем ориентировочное значение узла /. Далее пересматриваются ориентировочныезначения узлов / и А. Переходим к узлу R. Выполняется просмотр узлов R и S, узлуР назначается ориентировочное значение 4. Просмотр узла Т и всех его потомковпроводить не нужно, поскольку это может только понизить значение узла Р, котороеуже и без того слишком низкое, чтобы повлиять на значение узла А.
ПМетод ветвей и границИгры — не единственная категория задач, которые можно решать полным перебором всего дерева возможностей. Широкий спектр задач, в которых требуется найтиминимальную или максимальную конфигурацию того или иного типа, поддаютсярешению путем поиска с возвратом, применяемого к дереву возможностей. Узлы такого дерева можно рассматривать как совокупности конфигураций, а каждый пото296ГЛАВА 10. МЕТОДЫ РАЗРАБОТКИ АЛГОРИТМОВмок узла и представляет некоторое подмножество конфигураций. Наконец, каждыйлист представляет отдельную конфигурацию или решение соответствующей задачи;каждую такую конфигурацию можно оценить и попытаться выяснить, не являетсяли она наилучшей среди уже найденных решений.Если просмотр организован достаточно рационально, каждый из потомков некоторого узла будет представлять намного меньше конфигураций, чем соответствующий узел, поэтому, чтобы достичь листьев, не придется забираться слишком глубоко.
Чтобы такая организация поиска не показалась читателю чересчур запутанной,рассмотрим конкретный пример.Пример 10.8. Вспомните задачу коммивояжера, которую мы рассмотрели в одномиз предыдущих разделов. В связи с этой задачей мы описали так называемый"жадный алгоритм", позволяющий найти хороший, хотя и необязательно оптимальный, маршрут. Посмотрим, как можно было бы найти оптимальный маршрут путемсистематического просмотра всех маршрутов. Это можно было бы сделать, рассмотрев все перестановки узлов и определив маршрут, который проходит через узлы в соответствующей последовательности, учитывая наилучший из найденных до сих пормаршрутов.
Время, которое потребуется на реализацию такого подхода на графе с пузлами, равняется О(п\), поскольку необходимо рассмотреть (п - 1)! различных пере1становок, а оценка каждой перестановки занимает время О(п).Маршрутыбез (а, Ь)Маршруты без(а, Ь) и (а, с)Маршруты без(а, Ь), (а, с)или (а, d)Маршруты с(а, с) и (a, d)но без (а, Ь)Маршруты с(a, d) и без(а, Ь) или (а, с)Рис.
10.15. Начало дерева решений для задачи коммивояжераМы рассмотрим несколько иной подход, который в наихудшем случае оказывается ничуть не лучше описанного выше, однако в среднем — в сочетании с методомветвей и границ, который мы далее кратко рассмотрим, — позволяет получить ответ1Обратите внимание: нам не нужно рассматривать все п! перестановок, поскольку исходный пункт маршрута не имеет значения. Следовательно, мы можем рассматривать только теперестановки, которые начинаются с 1.10.4. ПОИСК С ВОЗВРАТОМ297намного быстрее, чем метод "перебора всех перестановок". Построение дерева начинается с корня, который представляет все маршруты. Маршруты соответствуют ужеупоминавшимся выше "конфигурациям".
Каждый узел имеет двух сыновей, и маршруты, которые представляет узел, делятся этими сыновьями на две группы: которые содержат определенное ребро и у которых такого ребра нет. Например, нарис. 10.15 показаны фрагменты дерева для задачи коммивояжера из рис. 10.11.Будем проходить ребра дерева решений из рис.
10.15 в лексикографическом порядке: (а, Ь), (а, с), ... , (a, f), (Ь, с), ... , (b, f), (с, d) и т.д. Можно, разумеется, выбрать любой другой порядок. Учтите, что не у каждого узла в этом дереве есть двасына. Некоторых сыновей можно удалить, поскольку выбранные ребра не образуютчасть маршрута. Таким образом, не существует узлов для маршрутов, содержащихребра (а, Ь), (а, с) и (а, d), так как вершина а имела бы степень 3 и полученный результат не был бы маршрутом. Точно так же, спускаясь вниз по дереву, можно удалить некоторые узлы, поскольку какой-то город будет иметь степень меньше 2.
Например, нет ни одного узла для маршрутов без (а, 6), (а, с), (a, d) или (а, е). ПОграничения эвристических алгоритмовВоспользовавшись идеями, подобными тем, на которых основывается метод альфа-бета отсечения, можно избавиться от просмотра намного большего количества узлов дерева поиска, чем предполагается в примере 10.8. Для определенности представим, что перед нами поставлена задача минимизации некоторой функции, напримерстоимости маршрута в задаче коммивояжера. Допустим также, что мы располагаемметодом определения нижней границы стоимости любого решения из тех, которыевходят в совокупность решений, представленных некоторым узлом га. Если наилучшее из найденных до сих пор решений стоит меньше, чем нижняя граница для узлал, то не нужно анализировать любой из узлов ниже п.Пример 10.9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
