Последовательность обхода дерева в обратном порядке такова: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). Известна цена сына C₁ = 20. Оценивается сын C₂.

С

С₁

С₂

С₃

D₁

max

min

15

≤15

20

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

Т.к С в режиме max, а цена С₂ меньше цены С₁, то цена С₂ не повлияет на цену С, рассмотрение С₂ можно не продолжать – отсечь С_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.

Дата добавления: 2014-01-04