Назад | Содержание| Вперёд 13. 3. Базовые процедурыпоиска в И / ИЛИ-графах...

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

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.    Рассмотритекакую-нибудь простую детерминированную игрудвух лиц с полной информацией и дайтеопределение ее И / ИЛИ-представления. Используйтепрограмму поиска в И / ИЛИ-графах для построениявыигрывающих стратегий в форме И / ИЛИ-деревьев.

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

Главная | В избранное | Наш E-MAIL | Добавить материал | Нашёл ошибку | Наверх