Методы сокращения перебора

       - универсальные методы (не зависят от проблемной области).

       - эвристические методы (учитывают специфику задачи).

 

Универсальные методы

       Метод максимина.

Метод заключается в максимизации выигрыша, при минимизации проигрыша.

(при отсутствии дополнительной информации). Этот метод позволяет отсекать неперспективные направления.

           

       Игрок А: (MAX)

       Игрок В: (MIN)

           

       Идея алгоритма:

1. Строится полное поисковое дерево на ту глубину, которую возможно позволить по затратам памяти, времени и т.д.. Число ходов должно быть чётно.

2. Концевые вершины дерева оцениваются оценочной функцией.

3. Совершается обратное движение по дереву от концевой к начальной вершине. Выбирается лучший ход игрока А.

 

Отрицательной чертой алгоритма является то, что сначала строится всё (возможное) дерево, а затем оно оценивается. Лучшим решением было бы отсеивание неперспективных ветвей во время построения.

 

Пример:

 

Метод a-b отсечения

Идея метода была предложена Дж. Маккарти в 1961 г.

В основе метода лежит то, что процессы построения и отсечения дерева происходят одновременно.

 

Существуют 2 случая a-b отсечения:

 

1. Неглубокое(простое) a-b отсечение.
2. Глубокое  a-b отсечение.

 

Неглубокое a-b отсечение

Рассмотрим следующее дерево:

                         

                      S                                                                                                                                                                                                                          

         A                    A  

A                B                

          f(A)=a     …………

                     B                                                                                                                                                                                                     

                       C                               

                          f(C)=z£a

Пусть на известны оценки f(A)=a  и f(C)=z£a. Докажем, что если f(C)£a, то ветви, исходящие из вершины B (на рисунке обозначенные синим цветом) можно отсечь.

 

Т.к. игрок B стремится минимизировать оценочную функцию, следовательно оценка вершины B будет не больше z.

 

Т.к. оценка вершины B - f(B) £ f(C) £a, следовательно вершина B  не перспективна (потому что f(A)=a, а игрок   A  стремится максимизировать оценочную функцию).

 

Все вышесказанное справедливо для a-отсечения.

Для b-отсечения:

- ход делает игрок B

- f(A)= b

- f(C)= w³b