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),