Назад | Содержание | Вперёд

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)        Если Верш - И-вершина, то решающее дерево имеет вид

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

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

% Поиск в глубину для И / ИЛИ-графов
% Процедура решить( Верш, РешДер) находит решающее дерево для
% некоторой вершины в И / ИЛИ-графе

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

        решить( Верш, Верш ---> Дер) :-
                Верш ---> или : Вершины,
        % Верш - ИЛИ-вершина
                принадлежит( Верш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).
                                                        % Попытка с новым ограничением

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

Упражнения

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

13. 2.    Определите на Прологе И / ИЛИ-пространство для задачи "ханойская башня" и примените к нему процедуры поиска настоящего раздела.

13. 3.    Рассмотрите какую-нибудь простую детерминированную игру двух лиц с полной информацией и дайте определение ее И / ИЛИ-представления. Используйте программу поиска в И / ИЛИ-графах для построения выигрывающих стратегий в форме И / ИЛИ-деревьев.


Назад | Содержание | Вперёд