необходимо придерживаться приведенных ниже правил:
(1) Если В - целевая вершина, то задача решается тривиальным образом.
(2) Если вершина В имеет ИЛИ-преемников, то нужно решить одну из соответствующих задач-преемников (пробовать решать их одну за другой, пока не будет найдена задача, имеющая решение).
(3) Если вершина В имеет И-преемников, то нужно решить все соответствующие задачи (пробовать решать их одну за другой, пока они не будут решены все).
Если применение этих правил не приводит к решению, считать, что задача не может быть решена.
Соответствующая программа выглядит так:
решить( Верш) :-
цель( Верш).
решить( Верш) :-
Верш ---> или : Вершины, % Верш - ИЛИ-вершина
принадлежит( Верш1, Вершины),
% Выбор преемника Верш1 вершины Верш
решить( Bepш1).
решить( Верш) :-
Верш ---> и : Вершины, % Верш - И-вершина
решитьвсе( Вершины).
% Решить все задачи-преемники
решитьвсе( [ ]).
решитьвсе( [Верш | Вершины]) :-
решить( Верш),
решитьвсе( Вершины).
Здесь принадлежит - обычное отношение принадлежности к списку.
Эта программа все еще имеет недостатки:
она не порождает решающее дерево, и
она может зацикливаться, если И / ИЛИ-граф имеет соответствующую структуру (циклы).
Программу нетрудно изменить с тем, чтобы она порождала решающее дерево. Необходимо так подправить отношение решить, чтобы оно имело два аргумента:
решить( Верш, РешДер).
Решающее дерево представим следующим образом. Мы имеем три случая:
(1) Если Верш - целевая вершина, то соответствующее решающее дерево и есть сама эта вершина.
(2) Если Верш - ИЛИ-вершина, то решающее дерево имеет вид
Верш ---> Поддерево
где Поддерево - это решающее дерево для одного из преемников вершины Верш.
(3) Если Верш - И-вершина, то решающее дерево имеет вид
Верш ---> и : Поддеревья
где Поддеревья - список решающих
