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


         

В нашем случае мы уже


В нашем случае мы уже не можем использовать этот прием, поэтому программа несколько усложняется. Ключевую роль в нашей программе будет играть отношение

        расширить( Путь, Дер, Дер1, ЕстьРеш, Решение)

На рис. 11.12 показано, как связаны между собой аргументы отношения расширить. При каждом обращении к расширить

переменные Путь и Дер будут уже конкретизированы. Дер - поддерево всего дерева поиска, одновременно оно служит для представления множества путей-кандидатов внутри этого поддерева. Путь - это путь, ведущий из стартовой вершины в корень поддерева Дер. Самая общая идея алгоритма -



Рис. 11. 12.  Отношение paсширить( Путь, Дер, Дер1, ЕстьРеш, Решение):

s -   стартовая вершина,  g

-  целевая вершина. Решение - это Путь,

продолженный вплоть до  gДер1

- результат расширения дерева

Дер на один уровень вниз.

получить поддерево Дер1 как результат расширения Дер на один уровень. Но в случае, когда в процессе расширения поддерева Дер

встретится целевая вершина, процедура расширить

должна сформировать соответствующий решающий путь.

Итак, процедура расширить будет порождать два типа результатов. На конкретный вид результата будет указывать значение переменной ЕстьРеш:

(1)        ЕстьРеш = да

            Решение

= решающий путь, т. е. Путь, продолженный до целевой вершины.

            Дер1

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

Разумеется, такой тип результата получится только в том случае, когда Дер будет содержать целевую вершину. Добавим также, что эта целевая вершина обязана быть листом поддерева Дер.

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

            Дер1

= результат расширения поддерева Дер на один уровень вниз от своего "подножья". Дер1

не содержит ни одной "тупиковой" ветви из Дер, т.

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