Prolog

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

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

        пуск( Состояние) :-

                Условие ---> Действие,

                проверить( Условие, Состояние),

                выполнить( Действие, Состояние).

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

Проект

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

Резюме

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

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

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

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

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

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

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

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

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

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

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

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

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

                основе принципа резолюции

Литература

Waterman and Hayes-Roth (1978) - классическая книга по системам, управляемым образцами. В книге Nilsson (1980) можно найти фундаментальные понятия, относящиеся к задаче автоматического доказательства теорем, включая алгоритм преобразования логических формул в конъюнктивную нормальную форму. Прологовская программа для выполнения этого преобразования приведена в Clocksin and Mellish (1981).

Clocksin F. W. and Mellish С S. (1981). Programming in Prolog. Springer- Verlag. [Имеется перевод: Клоксин У., Мелиш К. Программирование на языке Пролог. - М.: Мир, 1987.]

Nilsson N. J. (1980). Principles of Artificial Intelligence. Tioga; Springer-Verlag.

Waterman D. A. and Hayes-Roth F. (1978, eds). Pattern-Directed Inference Systems. Academic Press.

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

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

ОТВЕТЫ К НЕКОТОРЫМ УПРАЖНЕНИЯМ

Глава 1

1. 1

(a)    no

(b)    X = пат

(c)    X = боб

(d)    X = боб,    Y = пат

1. 2

(a)    ?-  родитель( X, пат).

(b)    ?-  родитель( лиз, X).

(c)    ?-  родитель( Y, пат),     родитель( X, Y).

1. 3

(a)    счастлив( X) :-

                родитель( X, Y).

(b)    имеетдвухдетей( X) :-

                родитель( X, Y),

                сестра( Z, Y).

1. 4

внук( X, Z) :-

        родитель( Y, X),

        родитель( Z, Y).

1. 5

тетя( X, Y) :-

        родитель( Z, Y),