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

.

procedureвычислить (Прогр, СписокЦелей, Успех)

Входные параметры:

 Прогр: список предложений

 СписокЦелей: список целей

Выходной параметр:

 Успех: истинностное значение; Успех принимает значение

        истина, если список целевых утверждений

        (их конъюнкция) истиннен с точки зрения Прогр

Локальные переменные:

 Цель: цель

 ДругиеЦели: список целей

 Достигнуты: истинностное значение

 Сопоставились: истинностное значение

 Конкрет: конкретизация переменных

          H, Н', B1, B1', …, В_>n, В_>n': цели

Вспомогательные функции:

 пycтой( L): возвращает истину, если L — пустой список

 голoвa( L): возвращает первый элемент списка L

 хвост( L): возвращает остальную часть списка L

 конкат( L1, L2): создает конкатенацию списков — присоединяет

  список L2 к концу списка L1

 сопоставление( T1, T2, Сопоставились, Конкрет): пытается

  сопоставить термы Т1 и T2; если они сопоставимы, то

  Сопоставились — истина, а Конкрет представляет

  собой конкретизацию переменных

 подставить( Конкрет, Цели): производит подстановку переменных

  в Цели согласно Конкрет

begin

 ifпустой( СписокЦелей)thenУспех : = истина

 else

  begin

   Цель : = голова( СписокЦелей);

   ДругиеЦели : = хвост( СписокЦелей);

   Достигнута : = ложь;

   while notДостигнутаand

    "в программе есть еще предложения" do

    begin

     Пусть следующее предложение в Прогр есть

      H :- B1, …, Вn.

     Создать вариант этого предложения

      Н' :- В1', …, Вn'.

     сопоставление( Цель, Н',

      Сопоставились, Конкрет)

     ifСопоставилисьthen

      begin

       НовыеЦели :=

        конкат( [В1', …, Вn' ], Другие Цели);

       НовыеЦели : =

        подставить( Конкрет, НовыеЦели);

       вычислить( Прогр, НовыеЦели, Достигнуты)

      end

    end;

    Успех : = Достигнуты

  end

end;

Рис. 2.11.  Вычисление целевых утверждений Пролога.

Всякий раз, как рекурсивный вызов процедуры >вычислить приводят к неуспеху, процесс вычислений возвращается к >ПРОСМОТРУ и продолжается с того предложения  С,  которое использовалось последним. Поскольку применение предложения  С  не привело к успешному завершению, пролог-система должна для продолжения вычислений попробовать альтернативное предложение. В действительности система аннулирует результаты части вычислений, приведших к неуспеху, и осуществляет возврат в ту точку (предложение  С),  в которой эта неуспешная ветвь начиналась. Когда процедура осуществляет возврат в некоторую точку, все конкретизации переменных, сделанные после этой точки, аннулируются. Такой порядок обеспечивает систематическую проверку пролог-системой всех возможных альтернативных путей вычисления до тех пор, пока не будет найден путь, ведущий к успеху, или же до тех пор, пока не окажется, что все пути приводят к неуспеху.

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

Конечно, в настоящих реализациях Пролога в процедуру >вычислить добавлены и еще некоторые усовершенствования. Одно из них — сокращение работы по просмотрам программы с целью повышения эффективности. Поэтому на практике пролог-система не просматривает все предложения программы, а вместо этого рассматривает только те из них, которые касаются текущего целевого утверждения.

2.9. Рассмотрите программу на рис. 2.10 и по типу того, как это сделано на рис. 2.10, проследите процесс вычисления пролог-системой вопроса

>?- большой( X), темный( X).

Сравните свое описание шагов вычисления с описанием на рис. 2.10, где вычислялся, по существу, тот же вопрос, но с другой последовательностью целей:

>?- темный( X), большой( X).

В каком из этих двух случаев системе приходится производить большую работу для нахождения ответа?

Задача об обезьяне и банане часто используется в качестве простого примера задачи из области искусственного интеллекта. Наша пролог-программа, способная ее решить, показывает, как механизмы сопоставления и автоматических возвратов могут применяться для подобных целей. Мы сначала составим программу, не принимая во внимание процедурную семантику, а затем детально изучим ее процедурное поведение. Программа будет компактной и наглядной.