§10. Перебор с возвратами. Метод отсечения.

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

Рассмотрим один из методов для организованного поиска решения, исчерпывающего все варианты - перебор с возвратом (бэктрекинг, поиск с отходом назад). Далее будет показано, как применение дополнительных приемов, таких как отсечение позволяет существенно сократить объем операций поиска.

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

Построим дерево игры. Каждый узел представляет определенную позицию в игре. Если узел n представляет позицию x,то все потомки узла n соответствуют совокупности допустимых ходов из позиции x.

Пример 1:

Часть дерева игры в крестики-нолики. Указана цена игры для игрока №1,ставящего крестик:

Выигрыш-1 очко,

Ничья-0 очков,

Проигрыш-1 очко.

Замечание: аналогично можно построить дерево, узлы которого представляют этапы развития некоторой неигровой ситуации (см. §11).

При бэктрекинге совершается обход дерева решений в обратном порядке. Т.е. внутренний узел n рассматривается только после обхода всех его потомков.

Узлу n присваивается некоторое значение, исходя из следующих правил:

1. Если узел n соответствует позиции x, из которой делает ход игрок №1, тогда узлу n присваивается значение, равное максимуму из цен его сыновей. Т.е. из позиции x игрок №1 сделает ход, который принесет ему максимальный выигрыш.

2. Если из узла n (позиции x) делает ход игрок №2, то узлу n присваивается значение, равное минимуму из цен его сыновей. Т.е. из позиции x игрок №2 сделает ход, который принесет минимальный выигрыш игроку №1.

Пример2. Оценим все узлы, части дерева игры из примера 1.

Последовательность обхода дерева в обратном порядке такова:b,I,e,f,c,j,g,k,h,d,a.

B: цена = 1 известна.

I: цена = 0 известна.

E: последует ход игрока №1. Цена Е = максимуму из цен сыновей: I, т.е.max{0}=0.

F: цена = -1 известна.

C: последует ход игрока №2. Цене С = минимуму из цен сыновей E и F, т.е. min{0,-1}=-1.

J: цена = 0 известна.

G: последует ход игрока №1. Цена G = максимуму из цен сыновей: J, т.е. max{0}=0.

K: цена = 0 известна.

H: последует ход игрока №1. Цена H = максимуму из цен сыновей: K, т.е. max{1}=1.

D: последует ход игрока №2. Цена D = минимуму из цен сыновей G, H; min{0,1}=0.

A: последует ход игрока №1. ЦенаA = максимуму из цен сыновей B,C,D, max{1,-1,0}=1.

Таким образом цена узла A перед ходом игрока №1 равна 1, следовательно, на этапе A игрок №1 имеет стратегию, следуя которой, он получит 1 очко (т.е. победит). А именно, стратегию A→B.

Аналогично, если игра дошла до этапа D, цена которого = 0, то игрок №1 имеет стратегию, которая обеспечит ему 0 очков (т.е. ничью). А именно D→G→J.

При этом, считаем, что из любой позиции игрок №2 делает ход, наиболее невыгодный для №1.

Отсечение – приём, позволяющий избежать рассмотрения некоторых частей дерева игры при бэктрекинге.

Пусть, например, рассматривается узел С находящийся в режиме max (ход игрока №1). Известна цена сына C₁ = 20. Оценивается сын C₂.

Допустим, найдена цена одного из сыновей D₁ узла C₂, равная 15. Так как С₂ в режиме min, то цена С₂ не может быть больше 15, т.е. она заведомо меньше цены С_1.

Т.к С в режиме max, а цена С₂ меньше цены С₁, то цена С₂ не повлияет на цену С, рассмотрение С₂ можно не продолжать – отсечь С_2.

Пример 3. Оценить корень А дерева игры, применить бэктрекинг и метод отсечения. Цены узлов K-V заданы по условию.

Решение порядок обхода:

K L E M N F B O P G Q R H C S T I U V J D A.

Рассмотрим отсечение узла J.

Вычислена цена I = 4, значит, цена Р, который находится в режиме min будет .

Дана цена U = 6, тогда цена J, который находится в режиме max будет . Какова бы она не была, она не может стать ценой D, которая . Поэтому далее узел J и его сыновья не рассматриваются (отсекаются).

Таким образом цена D равна цене I и равна 4.

Оценка корня дерева говорит о том, что на этапе А игрок №1 имеет стратегию, при которой он получает 5 очков, а именно: A→C→H→Q.