Неизвестно - Prolog

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

отобр( Дер) :- % Отобразить решающее дерево

отобр( Дер, 0), !. % с отступом 0

отобр( Верш ---> Дер, Н) :-

% Отобразить решающее дерево с отступом Н

write( Верш), write( '--->'),

H1 is H + 7,

отобр( Дер, H1), !.

отобр( и : [Д], Н) :-

% Отобразить И-список решающих деревьев

отобр( Д, Н).

отобр( и : [Д | ДД], Н) :-

% Отобразить И-список решающих деревьев

отобр( Д, Н),

tab( H),

отобр( и : ДД, Н), !.

отобр( Верш, Н) :-

write( Верш), nl.

Рис. 13. 8. Поиск в глубину для И / ИЛИ-графов. Эта программа может

зацикливаться. Процедура решитьнаходит решающее дерево, а

процедура отобрпоказывает его пользователю. В процедуре отобр

предполагается, что на вывод вершины тратится только один символ.

Например, при поиске в И / ИЛИ-графе рис. 13.4 первое найденное решение задачи, соответствующей самой верхней вершине а , будет иметь следующее представление:

а ---> b ---> и : [d, c ---> h]

Три формы представления решающего дерева соответствуют трем предложениям отношения решить. Поэтому все, что нам нужно сделать для изменения нашей исходной программы решить, - это подправить каждое из этих трех предложений, просто добавив в каждое из них решающее дерево в качестве второго аргумента. Измененная программа показана на рис. 13.8. В нее также введена дополнительная процедура отобрдля отображения решающих деревьев в текстовой форме. Например, решающее дерево рис. 13.4 будет отпечатано процедурой отобрв следующем виде:

а ---> b ---> d

е ---> h

Программа рис. 13.8 все еще сохраняет склонность к вхождению в бесконечные циклы. Один из простых способов избежать бесконечных циклов - это следить за текущей глубиной поиска и не давать программе заходить за пределы некоторого ограничения по глубине. Это можно сделать, введя в отношение решитьеще один аргумент:

решить( Верш, РешДер, МаксГлуб)

Как и раньше, вершиной Вершпредставлена решаемая задача, а РешДер- это решение этой задачи, имеющее глубину, не превосходящую МаксГлуб. МаксГлуб-это допустимая глубина поиска в графе. Если МаксГлуб= 0, то двигаться дальше запрещено, если же МаксГлуб> 0, то поиск распространяется на преемников вершины Верш, причем для них устанавливается меньший предел по глубине, равный МаксГлуб-1. Это дополнение легко ввести в программу рис. 13.8. Например, второе предложение процедуры решить примет вид: