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

:- op( 110, xfy, &).          % Конъюнкция
:- op( 120, xfy, v).          % Дизъюнкция
:- op( 130, xfy, =>).         % Импликация
транс( F & G) :- !,     % Транслировать конъюнктивную формулу
 транс( F),
 транс( G).
транс( Формула) :-
 тр( Формула, НовФ), !, % Шаг трансформации
 транс( НовФ).
транс( Формула) :-      % Дальнейшая трансформация невозможна
 assert( дизъюнкт( Формула) ).
% Правила трансформаций для пропозициональных формул
тр( ~( ~X), X) :- !.          % Двойное отрицание
тр( X => Y, ~X v Y) :- !.     % Устранение импликации
тр( ~( X & Y), ~X v ~Y) :- !. % Закон де Моргана
тр( ~( X v Y), ~X & ~Y) :- !. % Закон де Моргана
тр( X & Y v Z, (X v Z) & (Y v Z) ) :- !.
  % Распределительный закон
тр( X v Y & Z, (X v Y) & (X v Z) ) :- !.
  % Распределительный закон
тр( X v Y, X1 v Y) :-         % Трансформация подвыражения
 тр( X, X1), !.
тр( X v Y, X v Y1) :-         % Трансформация подвыражения
 тр( Y, Y1), !.
тр( ~X, ~Х1) :-               % Трансформация подвыражения
 тр( X, X1).

Рис. 16.8. Преобразование пропозициональных формул в множество дизъюнктов с записью их в базу данных при помощи assert.

16.4. Заключительные замечания

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

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

Когда база данных велика, а программа содержит большое количество модулей, процесс сопоставления с образцами становится крайне неэффективным. Неэффективность можно уменьшить, усложнив организацию базы данных. В частности, можно ввести индексирование информации, записанной в базе данных, или разбить эту информацию на отдельные 'подбазы данных', или же разбить все множество модулей на отдельные подмножества. Идея разбиения — в каждый момент дать доступ только к некоторому подмножеству базы данных или набора модулей, ограничив тем самым сопоставление образцов только этим подмножеством. Разумеется, в этом случае механизм управления должен усложниться, поскольку он должен будет обеспечить переход от одних подмножеств к другим с целью их активизации либо деактивизации. Для этого можно применить специальные метаправила.

К сожалению, наш интерпретатор запрограммирован таким образом, что он блокирует механизм автоматических возвратов, так как для манипулирования базой данных он использует процедуры assert и retract. Это положение можно исправить, применив другой способ реализации базы данных, не требующий обращения к этим встроенным процедурам. Например, все состоять базы данных можно представить одним прологовским термом, передаваемым в процедуру пуск в качестве аргумента. Простейший способ реализации этой идеи — организовать этот терм в виде списка объектов базы данных. Тогда верхний уровень базы данных примет вид:

пуск( Состояние) :-
 Условие ---> Действие,
 проверить( Условие, Состояние),
 выполнить( Действие, Состояние).

Задача процедуры выполнить — получить новое состояние базы данных и обратиться к процедуре пуск, подав на ее вход это новое состояние.

Проект

Запрограммируйте интерпретатор, который, в соответствии с приведенным выше замечанием, реализует базу данных как аргумент пусковой процедуры и не использует для этого внутренней базы данных пролог-системы (т.е. обходится без assert и retract). Эта новая версия интерпретатора будет допускать автоматические возвраты. Попытайтесь разработать такое представление базы данных, которое облегчало бы сопоставление с образцами.

Резюме

• Архитектура, ориентированная на типовые конфигурации (образцы), хорошо приспособлена для решения многих задач искусственного интеллекта.

• Программа, управляемая образцами, состоит из модулей, запускаемых при возникновении в базе данных тех или иных конфигураций.

• Прологовские программы можно рассматривать как частный случай систем, управляемых образцами.

• Параллельная реализация — наиболее естественный способ реализации систем, управляемых образцами. Реализация на последовательной машине требует разрешения конфликтов между модулями, содержащимися в конфликтном множестве.

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

• Были рассмотрены следующие понятия:

   системы, управляемые образцами

   архитектуры, ориентированные на образцы

   программирование в терминах образцов

   модули, управляемые образцами

   конфликтное множество, разрешение конфликтов

   принцип резолюции

   автоматическое доказательство теорем на основе принципа резолюции

Литература

Waterman and Hayes-Roth (1978) — классическая книга по системам, управляемым образцами. В