иков.
Правила вычисления и в процессе поиска рекомендуются следующие:
1. у MAX вершины значение равно наибольшему в данный момент значению среди окончательных возвращенных значений для ее дочерних вершин;
2. у MIN вершины значение равно наименьшему в данный момент значению среди окончательных возвращенных значений для ее дочерних вершин.
Правила прекращения поиска:
3. можно не проводить поиска на поддереве, растущем из всякой MIN вершины, у которой значение не превышает значения всех ее родительских MAX вершин;
4. можно не проводить поиска на поддереве, растущем из всякой MAX вершины, у которой значение не меньше значения всех ее родительских MIN вершин.
На рис. 3. 7 показаны отсечения для конкретного примера. Таким образом, -алгоритм дает тот же результат, что иметод минимакса, но выполняется быстрее.
Рис. 3. 7. a-b отсечение для конкретного примера
Использование алгоритмов эвристического поиска для поиска на графе И, ИЛИ выигрышной стратегии в более сложных задачах и играх (шашки, шахматы) не реален. По некоторым оценкам игровое дерево игры в шашки содержит 1040 вершин, в шахматах 10120 вершин. Если при игре в шашки для одной вершины требуется 1/3 наносекунды, то всего игрового времени потребуется 1021 веков. В таких случаях вводятся искусственные условия остановки, основанные на таких факторах, как наибольшая допустимая глубина вершин в дереве поиска или ограничения на время и объем памяти.
Многие из рассмотренных выше идей были использованы А. Ньюэллом, Дж. Шоу и Г. Саймоном в их программе GPS. Процесс работы GPS в общем воспроизводит методы решения задач, применяемые человеком: выдвигаются подцели, приближающие к решению; применяетсяэвристический метод (один, другой и т. д. ), пока не будет получено решение
Страницы: << < 5 | 6 | 7 | 8 | 9 > >>