Конспект установочных лекций по комплексному курсу Информатика, Теория информации


Альфа»бета»поиск - часть 6


Имеет место

setopt(s, {р}, -¥, +¥) == opt(s, p).

С помощью этого инициирующего вызова мы получаем желаемый результат для игрока s в начальной позиции р.

Если вместо cint

возьмем тип bool

и заменим начальное значение gr == -¥ на gr == false, а начальное значение min = ¥ на значение true, то для решения проблемы выигрышной позиции в булевской постановке получим классический бэктрекинг с а-р-отсечением.

С помощью оценок maxopt(s, р) можно отсекать определенные ветви вычислений. В случае сложных игр эти оценки можно заменить более или менее грубыми приближениями. Мы получим «эвристики», -при применении которых результаты не будут уже корректными, а только приближенными.

На эффективность алгоритма влияет и порядок последовательных просмотров вариантов. Если можно сначала просмотреть многообещающие в смысле максимизации или минимизации ветви, то [gr, min]-интервал быстро сужается и излишние ветви раньше распознаются и обрезаются.




- Начало -  - Назад -  - Вперед -



Книжный магазин