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




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


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

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

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


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