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

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

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

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

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

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

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

а ---> или : [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).

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

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

 решитьвсе( Вершины).

  % Решить все задачи-преемники

решитьвсе( []).

решитьвсе( [Верш | Вершины]) :-

 решить( Верш),

 решитьвсе( Вершины).

Здесь принадлежит — обычное отношение принадлежности к списку.

Эта программа все еще имеет недостатки:

• она не порождает решающее дерево, и

• она может зацикливаться, если И/ИЛИ-граф имеет соответствующую структуру (циклы).

Программу нетрудно изменить с тем, чтобы она порождала решающее дерево. Необходимо так подправить отношение решить, чтобы оно имело два аргумента:

решить( Верш, РешДер).

Решающее дерево представим следующим образом. Мы имеем три случая:

(1) Если Верш — целевая вершина, то соответствующее решающее дерево и есть сама эта вершина.

(2) Если Верш — ИЛИ-вершина, то решающее дерево имеет вид

Верш ---> Поддерево

где Поддерево — это решающее дерево для одного из преемников вершины Верш.

(3) Если Верш — И-вершина, то решающее дерево имеет вид

Верш ---> и : Поддеревья

где Поддеревья — список решающих деревьев для всех преемников вершины Верш.

% Поиск в глубину для И/ИЛИ-графов

% Процедура решить( Верш, РешДер) находит решающее дерево для

% некоторой вершины в И / ИЛИ-графе

решить( Верш, Верш) :-    % Решающее дерево для целевой

 цель( Верш).             % вершины - это сама вершина

решить( Верш, Верш ---> Дер) :-

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

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

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

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

решить( Верш, Верш ---> и : Деревья) :-

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

 решитьвсе( Вершины, Деревья).

  % Решить все задачи-преемники