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

         

Программа поиска с предпочтением в и / или-графе.



  Программа поиска с предпочтением в И / ИЛИ-графе.

Еще одна процедура

        собрать( ОстДер, НовДер, ЕстьРеш1, НовДеревья, ЕстьРеш)

связывает между собой несколько объектов, с которыми работает расширспис. НовДер - это расширенное дерево, взятое из списка деревьев процедуры расширспис, ОстДер - остальные, не измененные деревья из этого списка, а ЕстьРеш1 указывает на "решающий статус" дерева НовДер. Процедура собрать имеет дело с несколькими случаями в зависимости от значения ЕстьРеш1, а также от того, является ли список деревьев И-списком или ИЛИ-списком. Например, предложение

        собрать( или : _, Дер, да, Дер, да).

означает: в случае, когда список деревьев - это ИЛИ-список и при только что проведенном расширении получено решающее дерево, считать, что задача, соответствующая всему списку деревьев, также решена, а ее решающее дерево и есть само дерево Дер. Остальные случаи легко понять из текста процедуры собрать.

Для отображения решающего дерева можно определить процедуру, аналогичную процедуре отобр (рис. 13.8). Оставляем это читателю в качестве упражнения.

    Пример отношений, определяющих конкретную задачу: поиск маршрута
3.    Пример отношений, определяющих конкретную задачу: поиск маршрута

Давайте теперь сформулируем задачу нахождения маршрута как задачу поиска в И / ИЛИ-графе, причем сделаем это таким образом, чтобы наша формулировка могла бы быть непосредственно использована процедурой и_или рис. 13.12. Мы условимся, что карта дорог будет представлена при помощи отношения

        связь( Гор1, Гор2, Р)

означающего, что между городами Гор1 и Гор2



существует непосредственная связь, а соответствующее расстояние равно Р.   Далее, мы допустим, что существует отношение

        клпункт( Гор1-Гор2, Гор3)

имеющее следующий смысл: для того, чтобы найти маршрут из Гор1 в Гор2, следует рассмотреть пути, проходящие через Гор3 ( Гор3 - это "ключевой пункт" между Гор1 и Гор2). Например, на карте рис. 13.1  f   и  g  - это ключевые пункты между  а   и  z:

        клпункт( a-z, f).                 клпункт( a-z, g).

Мы реализуем следующий принцип построения маршрута:

Для того, чтобы найти маршрут между городами   X  и  Z,  необходимо:

    (1)        если между   X  и  Z  имеются ключевые пункты  Y1,   Y2,  ...,  то найти один из путей:

  • путь из  X  в  Z  через  Y1,  или
  • путь из  X  в  Z  через  Y2,  или
    ...

    (2)        если между   X  и  Z  нет ключевых пунктов, то найти такой соседний с  X   город  Y,  что существует маршрут из  Y  в  Z.

Таким образом, мы имеем два вида задач, которые мы будем представлять как

    (1)        X-Z                             найти маршрут из  X  в  Z

    (2)        X-Z через Y               найти маршрут из  X  в  Z,  проходящий через   Y

Здесь 'через' - это инфиксный оператор более высокого приоритета, чем '-', и более низкого, чем '--->'. Теперь можно определить соответствующий И / ИЛИ-граф явным образом при помощи следующего фрагмента программы:

        :- ор( 560, xfx, через)

        % Правила задачи X-Z, когда между  X  и  Z
        % имеются ключевые пункты,
        % стоимости всех дуг равны 0

        X-Z ---> или : СписокЗадач

        :- bagof( ( X-Z через Y)/0, клпункт( X-Z, Y),
                        СписокЗадач),   !.

        % Правила для задачи X-Z без ключевых пунктов

        X-Z ---> или : СписокЗадач

        :- bagof( ( Y-Z)/P, связь( X, Y, Р), СписокЗадач).

        % Сведение задачи типа ''через" к подзадачам,
           % связанным отношением И

        X-Z через Y---> и : [( X-Y)/0, ( Y-Z)/0].

        цель( Х-Х)         % Тривиальная задача: попасть из X в X

Функцию  h  можно определить, например, как расстояние, которое нужно преодолеть при воздушном сообщении между городами.



Содержание раздела








Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий