Последовательность обхода дерева в обратном порядке такова:B,I,E,F,C,J,G,K,H,D,A.

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

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

 

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

 

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

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

Пример 1:

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

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

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

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


 
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Ход игрока №1 (x)
Ход игрока №2 (0)
Ход игрока №1 (x)
Цена = 1
Цена = 1
Цена = 0
Цена = -1
Цена = 0
Цена = -1
Цена = 0
Цена = 1
Цена = 0
Цена = 0
Цена = 1
A
H
G
F
E
D
C
B
K
J
I
* * * * * * * * * * * * * * * * * *

 

 


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


 

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

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

 

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

 

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

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

А
С
F
E
B
I
D
G
J
H
K
Режим min
Режим max
1
1
-1
0
0
0
0
0
1
-1
1
Режим max  
Режим min  

 

 


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). Известна цена сына C1 = 20. Оценивается сын C2.

С
С1
С2
С3
D1
max
min
15
≤15
20

 

 

 

 

 

 

 

 


Допустим, найдена цена одного из сыновей D1 узла C2, равная 15. Так как С2 в режиме min, то цена С2 не может быть больше 15, т.е. она заведомо меньше цены С1.

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

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

5
2
4
5
2
6
8
5
4
2
1
6
1
8
3
5
2
3
4
6
2
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
T
U
V
max
min
S
max
≥6
≤4

 

 


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

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.