Prolog

В этом разделе нас будет интересовать какое-нибудь решение задачи независимо от его стоимости, поэтому проигнорируем пока стоимости связей или вершин И / ИЛИ-графа. Простейший способ организовать поиск в И / ИЛИ-графах средствами Пролога - это использовать переборный механизм, заложенный в самой пролог-системе. Оказывается, что это очень просто сделать, потому что процедурный смысл Пролога это и есть не что иное, как поиск в И / ИЛИ-графе. Например, И / ИЛИ-граф рис. 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)        Если Верш - И-вершина, то решающее дерево имеет вид

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

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