Prolog

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

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

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

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

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

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

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

                принадлежит( Верш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. Например, второе предложение процедуры решить примет вид:

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

                МаксГлуб > 0,

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

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

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

                Глуб1 is МаксГлуб - 1,                      % Новый предел по глубине

                решить( Bepш1, Дер, Глуб1).

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

Нашу процедуру

поиска в глубину с ограничением

можно также использовать для имитации

поиска в ширину

.

Идея состоит в следующем

: многократно повторять поиск в глубину каждый раз все с большим значением ограничения до тех пор, пока решение не будет найдено, То есть попробовать решить задачу с ограничением по глубине, равным 0, затем - с ограничением 1, затем - 2 и т.д. Получаем следующую программу:

        имитация_в_ширину( Верш, РешДер) :-

                проба_в_глубину( Верш, РешДер, 0).

% Проба поиска с возрастающим ограничением, начиная с 0

        проба_в_глубину( Верш, РешДер, Глуб) :-

                решить( Верш, РешДер, Глуб);

                Глуб1 is Глуб + 1,                             % Новый предел по глубине

                проба_в_глубину( Верш, РешДер, Глуб1).