Программирование на языке Пролог для искусственного интеллекта




Поиск с предпочтением - часть 11


с учетом ограничения Предел.

            Дер1

= неконкретизировано.

(2)        ЕстьРеш = нет

            Дер1

= дерево Дер, расширенное до тех пор, пока его f-оценка не превзойдет Предел

(см. рис. 12.4).

            Решение

= неконкретизировано.

(3)        ЕстьРеш = никогда.

            Дер1

и Решение = неконкретизированы.

В последнем случае Дер является "тупиковой" альтернативой, и соответствующий процесс никогда не будет реактивирован для продолжения просмотра этого дерева. Случай этот возникает тогда, когда f-оценка дерева Дер не превосходит ограничения Предел, однако дерево не может "расти" потому, что ни один его лист не имеет преемников, или же любой преемник порождает цикл.

Некоторые предложения процедуры расширить

требуют пояснений. Предложение, относящееся к наиболее сложному случаю, когда Дер

имеет поддеревья, т.е.

        Дер = д( В, F/G, [Д | ДД ] )

означает следующее. Во-первых, расширению подвергается наиболее перспективное дерево Д. В качестве ограничения этому дереву выдается не Предел, а не-

fig12_4.gif (3426 bytes)

Рис. 12. 4.  Отношение расширить: расширение дерева Дер до тех

пор, пока   f-оценка не превзойдет Предел, приводит к дереву Дер1.

которое, возможно, меньшее значение Предел1, зависящее от f-оценок других конкурирующих поддеревьев ДД. Тем самым гарантируется, что "растущее" дерево - это всегда наиболее перспективное дерево, а переключение активности между поддеревьями происходит в соответствии с их  f-оценками. После того, как самый перспективный кандидат расширен, вспомогательная процедура продолжить

решает, что делать дальше, а это зависит от типа результата, полученного после расширения.


Содержание  Назад  Вперед