Метод
Вид материала | Лекция |
СодержаниеРассмотрим следующее дерево Возможны 2 случая |
- Темы курсовых работ по курсу «Программирование» для студентов группы биб-11-1 (2011-2012, 85.51kb.
- Практических: 0 Лабораторных:, 21.53kb.
- Урока литературы в 9 классе на тему: «Древнерусская литература и современность. Золотое, 43.48kb.
- Расшифровка : Наука в целом (информационные технологии 004), 79.71kb.
- Программа исследования, 416.21kb.
- Решение. Из анализа схемы следует, что резисторы, 80.22kb.
- 1. Предмет и метод. Основные понятия экономики, 49.49kb.
- Линейных алгебраических уравнений ax=B, где, 66.22kb.
- 1 Встатье рассматриваются вопросы соотношения, 1701.62kb.
- Теоретичні питання з курсу „ Аналітична геометрія та лінійна алгебра, 24.09kb.
Лекция №5
Метод отсечения
Идея метода была предложена Дж. Маккарти в 1961 г.
В основе метода лежит то, что процессы построения и отсечения ДИ происходят одновременно.
Существуют 2 случая отсечения:
- Неглубокое (простое) отсечение.
- Глубокое отсечение.
1. Неглубокое отсечение
Рассмотрим следующее дерево:




A (MAX)





f(a) = …………
B (MIN)
З


c
f(c) = z
Пусть нам известны оценки f(a)= и f(c)=z. Докажем, что если f(c), то остальные ветви, исходящие из вершины b можно отсечь.
Так как игрок B стремится минимизировать оценочную функцию, следовательно, оценка вершины b будет не больше z.
Так как оценка вершины b не больше z ( f(b) f(c) ), следовательно, вершина b неперспективна (т.к. f(a)=, а игрок A стремится максимизировать оценочную функцию).
Все вышесказанное справедливо для -отсечения.
Для -отсечения :
- ход делает игрок B
- f(a) =
- f(c) = w
2. Глубокое отсечение
Рассмотрим следующее дерево:
S



A


f(a) =
B

f(c)
A

B

e …
f(e) = z
Пусть нам известны оценки f(a)= и f(e)= z . Докажем, что если f(e) , то остальные ветви, исходящие из вершины d можно отсечь.
Так как игрок B стремится минимизировать оценочную функцию, следовательно, оценка вершины d будет не больше z (f(d) f(e) = z ).
Так как игрок A стремится максимизировать оценочную функцию, оценка вершины c будет не меньше оценки вершины d (f(с) f(d)).
Возможны 2 случая:
1) f(c) = f(d), тогда f(c) = f(d) f(e) , т.е. имеем неглубокое - отсечение;
2) f(c) f(d), тогда вершина d неперспективна и для получения оценки f(c) не использовалась, а значит все вершины выходящие из d неперспективны.
Ход | Наилучшая оценка | Позиция на глубину | Оценка позиции | Условие отсечения | Действие |
Свой A(MAX) | | Своя | Z | z | -отсечение |
Противник B(MIN) | | Противника | W | w | -отсечение |
возрастает при построении оценки снизу вверх, а убывает при построении оценки снизу вверх.
Пусть оценивается дерево на n уровней. На каждом уровне имеется m вариантов выбора. Тогда сложность вычислений:
- для метода максимина - mn
- для метода отсечений:
(при больших n

Семинар №5
Задача №1:
Условие из примера в лекции №4.
5 S
3 1 4 1=zα=1 6 5 3 5 8 9 7 3=zα 4zα
n = 26
nk = 13


A
4=3





α=5




B











β=4

4=3=zα

A































α=1
5
3
7=w=5
3
4

B
Недостатки методов МАКСИМИНА и отсечений
1) Оба метода не являются стратегиями и базируются на классических переборных алгоритмах, с использованием оценочной функции.
2) Эффект горизонта.