Prolog

Неизвестно

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

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

.

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

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

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

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

Оба символа '--->' и ':' - инфиксные операторы, которые можно определить как

:- ор( 600, xfx, --->).

:- ор( 500, xfx, :).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

цель( Верш).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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