Базовые процедуры поиска в И / ИЛИграфах
13. 3. Базовые процедуры поиска в И / ИЛИ-графах
В этом разделе нас будет интересовать какое-нибудь решение задачи независимо от его стоимости, поэтому проигнорируем пока стоимости связей или вершин И / ИЛИ-графа. Простейший способ организовать поиск в И / ИЛИ-графах средствами Пролога - это использовать переборный механизм, заложенный в самой пролог-системе. Оказывается, что это очень просто сделать, потому что процедурный смысл Пролога это и есть не что иное, как поиск в И / ИЛИ-графе. Например, И / ИЛИ-граф Рисунок 13.4 (без учета стоимостей дуг) можно описать при помощи следующих предложений:
а :- b.
% а - ИЛИ-вершина с двумя преемниками
а :- с.
% b и с
b :- d, е.
% b - И-вершина с двумя преемниками d и е
с :- h.
с :- f, g.
f :- h, i.
d. g. h.
% d, g и h - целевые вершины
Для того, чтобы узнать, имеет ли эта задача решение, нужно просто спросить:
?- а.
Получив этот вопрос, пролог-система произведет поиск в глубину в дереве Рисунок 13.4 и после того, как пройдет через все вершины подграфа, соответствующего решающему дереву Рисунок 13.4(b), ответит "да".
Преимущество такого метода программирования И / ИЛИ-поиска состоит в его простоте. Но есть и недостатки:
- Мы получаем ответ "да" или "нет", но не получаем решающее дерево. Можно было бы восстановить решающее дерево при помощи трассировки программы, но такой способ неудобен, да его и недостаточно, если мы хотим иметь возможность явно обратиться к решающему дереву как к объекту программы.
- В эту программу трудно вносить добавления, связанные с обработкой стоимостей.
- Если наш И / ИЛИ-граф - это граф общего вида, содержащий циклы, то пролог-система, следуя стратегии в глубину, может войти в бесконечный рекурсивный цикл.
Попробуем постепенно исправить эти недостатки. Сначала определим нашу собственную процедуру поиска в глубину для И / ИЛИ-графов.
Прежде всего мы должны изменить представление И / ИЛИ-графов. С этой целью введём бинарное отношение, изображаемое инфиксным оператором '--->'. Например, вершина а с двумя ИЛИ-преемниками будет представлена предложением
а ---> или : [b, с].
Оба символа '--->' и ':' - инфиксные операторы, которые можно определить как
:- ор( 600, xfx, --->).
:- ор( 500, xfx, :).
Весь И / ИЛИ-граф Рисунок 13.4 теперь можно задать при помощи множества предложений
а ---> или : [b, с].
b ---> и : [d, e].
с ---> и : [f, g].
е ---> или : [h].
f ---> или : [h, i].
цель( d). цель( g). цель( h).
Процедуру поиска в глубину в И / ИЛИ-графах можно построить, базируясь на следующих принципах:
Для того, чтобы решить задачу вершины В, необходимо придерживаться приведенных ниже правил:
(1) Если В - целевая вершина, то задача решается тривиальным образом.
(2) Если вершина В имеет ИЛИ-преемников, то нужно решить одну из соответствующих задач-преемников (пробовать решать их одну за другой, пока не будет найдена задача, имеющая решение).
(3) Если вершина В имеет И-преемников, то нужно решить все соответствующие задачи (пробовать решать их одну за другой, пока они не будут решены все).
Если применение этих правил не приводит к решению, считать, что задача не может быть решена.
Соответствующая программа выглядит так:
решить( Верш) :-
цель( Верш).
решить( Верш) :-
Верш ---> или : Вершины,
% Верш - ИЛИ-вершина
принадлежит( Верш1, Вершины),
% Выбор преемника Верш1 вершины Верш
решить( Bepш1).
решить( Верш) :-
Верш ---> и : Вершины,
% Верш - И-вершина
решитьвсе( Вершины).
% Решить все задачи-преемники
решитьвсе( [ ]).
решитьвсе( [Верш | Вершины]) :-
решить( Верш),
решитьвсе( Вершины).
Здесь принадлежит - обычное отношение принадлежности к списку.
Эта программа все еще имеет недостатки:
- она не порождает решающее дерево, и
- она может зацикливаться, если И / ИЛИ-граф имеет соответствующую структуру (циклы).
Программу нетрудно изменить с тем, чтобы она порождала решающее дерево. Необходимо так подправить отношение решить, чтобы оно имело два аргумента:
решить( Верш, РешДер).
Решающее дерево представим следующим образом. Мы имеем три случая:
(1) Если Верш - целевая вершина, то соответствующее решающее дерево и есть сама эта вершина.
(2) Если Верш - ИЛИ-вершина, то решающее дерево имеет вид
Верш ---> Поддерево
где Поддерево - это решающее дерево для одного из преемников вершины Верш.
(3) Если Верш - И-вершина, то решающее дерево имеет вид
Верш ---> и : Поддеревья
где Поддеревья - список решающих деревьев для всех преемников вершины Верш.
line();% Поиск в глубину для И / ИЛИ-графов
% Процедура решить( Верш, РешДер) находит решающее дерево для
% некоторой вершины в И / ИЛИ-графе
решить( Верш, Верш) :-
% Решающее дерево для целевой
цель( Верш).
% вершины - это сама вершина
решить( Верш, Верш ---> Дер) :-
Верш ---> или : Вершины, % Верш - ИЛИ-вершина
принадлежит( Верш1, Вершины),
% Выбор преемника Верш1 вершины Верш
решить( Bepш1, Дер).
решить( Верш, Верш ---> и : Деревья) :-
Верш ---> и : Вершины,
% Верш - И-вершина
решитьвсе( Вершины, Деревья).
% Решить все задачи-преемники
решитьвсе( [ ], [ ]).
решитьвсе( [Верш | Вершины], [Дер | Деревья]) :-
решить( Верш, Дер),
решитьвсе( Вершины, Деревья).
отобр( Дер) :-
% Отобразить решающее дерево
отобр( Дер, 0), !.
% с отступом 0
отобр( Верш ---> Дер, Н) :-
% Отобразить решающее дерево с отступом Н
write( Верш), write( '--->'),
H1 is H + 7,
отобр( Дер, H1), !.
отобр( и : [Д], Н) :-
% Отобразить И-список решающих деревьев
отобр( Д, Н).
отобр( и : [Д | ДД], Н) :-
% Отобразить И-список решающих деревьев
отобр( Д, Н),
tab( H),
отобр( и : ДД, Н), !.
отобр( Верш, Н) :-
write( Верш), nl.