Программирование на языке Пролог для искусственного интеллекта

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

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

% Поиск в глубину для И/ИЛИ-графов
% Процедура решить( Верш, РешДер) находит решающее дерево для
% некоторой вершины в И / ИЛИ-графе
решить( Верш, Верш) :-    % Решающее дерево для целевой
 цель( Верш).             % вершины - это сама вершина
решить( Верш, Верш ---> Дер) :-
 Верш ---> или : Вершины, % Верш - ИЛИ-вершина
 принадлежит( Верш1, Вершины),
  % Выбор преемника  Верш1  вершины  Верш
 решить( Bepш1, Дер).
решить( Верш, Верш ---> и : Деревья) :-
 Верш ---> и : Вершины,   % Верш - И-вершина
 решитьвсе( Вершины, Деревья).
  % Решить все задачи-преемники
решитьвсе( [], []).
решитьвсе( [Верш | Вершины], [Дер | Деревья]) :-
 решить( Верш, Дер),
 решитьвсе( Вершины, Деревья).
отобр( Дер) :-            % Отобразить решающее дерево
 отобр( Дер, 0), !.       % с отступом 0
отобр( Верш ---> Дер, H) :-
  % Отобразить решающее дерево с отступом H
 write( Верш), write( '--->'),
 H1 is H + 7,
 отобр( Дер, H1), !.
отобр( и : [Д], H) :-
  % Отобразить И-список решающих деревьев
 отобр( Д, H).
отобр( и : [Д | ДД], H) :-
  % Отобразить И-список решающих деревьев
 отобр( Д, H),
 tab( H),
 отобр( и : ДД, H), !.
отобр( Верш, H) :-
 write( Верш), nl.

Рис. 13.8. Поиск в глубину для И/ИЛИ-графов. Эта программа может зацикливаться. Процедура решить находит решающее дерево, а процедура отобр показывает его пользователю. В процедуре отобр предполагается, что на вывод вершины тратится только один символ.

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

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

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

а ---> b ---> d
              e ---> 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).
  % Попытка с новым ограничением

Недостатком имитации поиска в ширину является то, что при каждом увеличении предела по глубине программа повторно просматривает верхнюю область пространства поиска.

Упражнения

13.1. Закончите составление программы поиска в глубину (с ограничением) для И/ИЛИ-графов, намеченную в настоящем разделе.

13.2. Определите на Прологе И/ИЛИ-пространство для задачи 'ханойская башня'