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