Программирование на языке Пролог для искусственного интеллекта




Базовые процедуры поиска в И / ИЛИ-графах


В этом разделе нас будет интересовать какое-нибудь

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

Преимущество такого метода программирования И / ИЛИ-поиска состоит в его простоте. Но есть и недостатки:

  • Мы получаем ответ "да" или "нет", но не получаем решающее дерево.


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