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

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

на обложку

Братко Иван

Шрифт:

Рис. 13.7. Формулировка игровой задачи для игры двух лиц в форме И/ИЛИ-дерева; участники игры: "игрок" и "противник".

13.3. Базовые процедуры поиска в И/ИЛИ-графах

В этом разделе нас будет интересовать какое-нибудь решение задачи независимо от его стоимости, поэтому проигнорируем пока стоимости связей или вершин И/ИЛИ-графа. Простейший способ

организовать поиск в И/ИЛИ-графах средствами Пролога — это использовать переборный механизм, заложенный в самой пролог-системе. Оказывается, что это очень просто сделать, потому что процедурный смысл Пролога это и есть не что иное, как поиск в И/ИЛИ-графе. Например, И/ИЛИ-граф рис. 13.4 (без учета стоимостей дуг) можно описать при помощи следующих предложений:

а :- b. % а - ИЛИ-вершина с двумя преемниками

а :- с. % b и с

b :- d, e. % b - И-вершина с двумя преемниками d и e

с :- h.

с :- f, g.

f :- h, i.

d. g. h. % d, g и h - целевые вершины

Для того, чтобы узнать, имеет ли эта задача решение, нужно просто спросить:

?- а.

Получив этот вопрос, пролог-система произведет поиск в глубину в дереве рис. 13.4 и после того, как пройдет через все вершины подграфа, соответствующего решающему дереву рис. 13.4(b), ответит "да".

Преимущество такого метода программирования И/ИЛИ-поиска состоит в его простоте. Но есть и недостатки:

• Мы получаем ответ "да" или "нет", но не получаем решающее дерево. Можно было бы восстановить решающее дерево при помощи трассировки программы, но такой способ неудобен, да его и недостаточно, если мы хотим иметь возможность явно обратиться к решающему дереву как к объекту программы.

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

• Если наш И/ИЛИ-граф — это граф общего вида, содержащий циклы, то пролог-система, следуя стратегии в глубину, может войти в бесконечный рекурсивный цикл.

Попробуем постепенно исправить эти недостатки. Сначала определим нашу собственную процедуру поиска в глубину для И/ИЛИ-графов.

Прежде всего мы должны изменить представление И/ИЛИ-графов. С этой целью введём бинарное отношение, изображаемое инфиксным оператором '

– -->

'. Например, вершина а с двумя ИЛИ-преемниками будет представлена предложением

а ---> или : [b, с].

Оба символа '

– -->

' и '

' — инфиксные операторы, которые можно определить как

:- op( 600, xfx, --->).

:- op( 500, xfx, :).

Весь И/ИЛИ-граф рис. 13.4 теперь можно задать при помощи множества предложений

а ---> или : [b, с].

b ---> и : [d, e].

с ---> и : [f, g].

e ---> или : [h].

f ---> или : [h, i].

цель( d). цель( g). цель( h).

Процедуру

поиска в глубину в И/ИЛИ-графах можно построить, базируясь на следующих принципах:

Для того, чтобы решить задачу вершины В, необходимо придерживаться приведенных ниже правил:

(1) Если В — целевая вершина, то задача решается тривиальным образом.

(2) Если вершина В имеет ИЛИ-преемников, то нужно решить одну из соответствующих задач-преемников (пробовать решать их одну за другой, пока не будет найдена задача, имеющая решение).

(3) Если вершина В имеет И-преемников, то нужно решить все соответствующие задачи (пробовать решать их одну за другой, пока они не будут решены все).

Если применение этих правил не приводит к решению, считать, что задача не может быть решена.

Соответствующая программа выглядит так:

решить( Верш) :-

цель( Верш).

решить( Верш) :-

Верш ---> или : Вершины, % Верш - ИЛИ-вершина

принадлежит( Верш1, Вершины),

% Выбор преемника Верш1 вершины Верш

решить( Bepш1).

решить( Верш) :-

Верш ---> и : Вершины, % Верш - И-вершина