Иван Братко - Программирование на языке Пролог для искусственного интеллекта
• Мы получаем ответ "да" или "нет", но не получаем решающее дерево. Можно было бы восстановить решающее дерево при помощи трассировки программы, но такой способ неудобен, да его и недостаточно, если мы хотим иметь возможность явно обратиться к решающему дереву как к объекту программы.
• В эту программу трудно вносить добавления, связанные с обработкой стоимостей.
• Если наш И/ИЛИ-граф — это граф общего вида, содержащий циклы, то пролог-система, следуя стратегии в глубину, может войти в бесконечный рекурсивный цикл.
Попробуем постепенно исправить эти недостатки. Сначала определим нашу собственную процедуру поиска в глубину для И/ИЛИ-графов.
Прежде всего мы должны изменить представление И/ИЛИ-графов. С этой целью введём бинарное отношение, изображаемое инфиксным оператором '--->'. Например, вершина а с двумя ИЛИ-преемниками будет представлена предложением
а ---> или : [b, с].
Оба символа '--->' и ':' — инфиксные операторы, которые можно определить как
:- op( 600, xfx, --->).
:- op( 500, xfx, :).
Весь И/ИЛИ-граф рис. 13.4 теперь можно задать при помощи множества предложений
а ---> или : [b, с].
b ---> и : [d, e].
с ---> и : [f, g].
e ---> или : [h].
f ---> или : [h, i].
цель( d). цель( g). цель( h).
Процедуру поиска в глубину в И/ИЛИ-графах можно построить, базируясь на следующих принципах:
Для того, чтобы решить задачу вершины В, необходимо придерживаться приведенных ниже правил:
(1) Если В — целевая вершина, то задача решается тривиальным образом.
(2) Если вершина В имеет ИЛИ-преемников, то нужно решить одну из соответствующих задач-преемников (пробовать решать их одну за другой, пока не будет найдена задача, имеющая решение).
(3) Если вершина В имеет И-преемников, то нужно решить все соответствующие задачи (пробовать решать их одну за другой, пока они не будут решены все).
Если применение этих правил не приводит к решению, считать, что задача не может быть решена.
Соответствующая программа выглядит так:
решить( Верш) :-
цель( Верш).
решить( Верш) :-
Верш ---> или : Вершины, % Верш - ИЛИ-вершина
принадлежит( Верш1, Вершины),
% Выбор преемника Верш1 вершины Верш
решить( Bepш1).
решить( Верш) :-
Верш ---> и : Вершины, % Верш - И-вершина
решитьвсе( Вершины).
% Решить все задачи-преемники
решитьвсе( []).
решитьвсе( [Верш | Вершины]) :-
решить( Верш),
решитьвсе( Вершины).
Здесь принадлежит — обычное отношение принадлежности к списку.
Эта программа все еще имеет недостатки:
• она не порождает решающее дерево, и
• она может зацикливаться, если И/ИЛИ-граф имеет соответствующую структуру (циклы).
Программу нетрудно изменить с тем, чтобы она порождала решающее дерево. Необходимо так подправить отношение решить, чтобы оно имело два аргумента:
решить( Верш, РешДер).
Решающее дерево представим следующим образом. Мы имеем три случая:
(1) Если Верш — целевая вершина, то соответствующее решающее дерево и есть сама эта вершина.
(2) Если Верш — ИЛИ-вершина, то решающее дерево имеет вид
Верш ---> Поддерево
где Поддерево — это решающее дерево для одного из преемников вершины Верш.
(3) Если Верш — И-вершина, то решающее дерево имеет вид
Верш ---> и : Поддеревья
где Поддеревья — список решающих деревьев для всех преемников вершины Верш.
% Поиск в глубину для И/ИЛИ-графов
% Процедура решить( Верш, РешДер) находит решающее дерево для
% некоторой вершины в И / ИЛИ-графе
решить( Верш, Верш) :- % Решающее дерево для целевой
цель( Верш). % вершины - это сама вершина
решить( Верш, Верш ---> Дер) :-
Верш ---> или : Вершины, % Верш - ИЛИ-вершина
принадлежит( Верш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).
% Попытка с новым ограничением
Недостатком имитации поиска в ширину является то, что при каждом увеличении предела по глубине программа повторно просматривает верхнюю область пространства поиска.
