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




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


Можно было бы восстановить решающее дерево при помощи трассировки программы, но такой способ неудобен, да его и недостаточно, если мы хотим иметь возможность явно обратиться к решающему дереву как к объекту программы.

  • В эту программу трудно вносить добавления, связанные с обработкой стоимостей.
  • Если наш И / ИЛИ-граф - это граф общего вида, содержащий циклы, то пролог-система, следуя стратегии в глубину, может войти в бесконечный рекурсивный цикл.
  • Попробуем постепенно исправить эти недостатки. Сначала определим нашу собственную процедуру поиска в глубину для И / ИЛИ-графов.

    Прежде всего мы должны изменить представление И / ИЛИ-графов. С этой целью введём бинарное отношение, изображаемое инфиксным оператором '--->'. Например, вершина  а  с двумя ИЛИ-преемниками будет представлена предложением

            а ---> или : [b, с].

    Оба символа  '--->'  и  ':'  - инфиксные операторы, которые можно определить как

            :- ор( 600, xfx, --->).

            :- ор( 500, xfx, :).

    Весь И / ИЛИ-граф рис. 13.4 теперь можно задать при помощи множества предложений

            а ---> или : [b, с].

            b ---> и : [d, e].

            с ---> и : [f, g].

            е ---> или : [h].

            f ---> или : [h, i].

            цель( d).     цель( g).    цель( h).

    Процедуру поиска в глубину в И / ИЛИ-графах можно построить, базируясь на следующих принципах:

    Для того, чтобы решить задачу вершины  В,   необходимо придерживаться приведенных ниже правил:

        (1)        Если  В   -  целевая вершина, то задача решается тривиальным образом.




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