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

К сожалению, наш интерпретатор запрограммирован таким образом, что он блокирует механизм автоматических возвратов, так как для манипулирования базой данных он использует процедуры 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

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

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

1.6

Да. (Определение верно)

1.7

(a) возвратов не будет

(b) возвратов не будет

(c) возвратов не будет

(d) возвраты будут

2.1

(a) переменная

(b) атом

(c) атом

(d) переменная

(e) атом

(f) структура

(g) число

(h) синтаксически неправильное выражение

(i) структура

(j) структура

2.3

(a) успех

(b) неуспех

(c) неуспех

(d) D = 2, E = 2

(e) P1 = точка(-1, 0) 

   Р2 = точка( 1, 0)

   Р3 = точка( 0, Y)

Такая конкретизация определяет семейство треугольников, у которых две вершины располагаются на оси x в точках 1 и -1, а третья — в произвольной точке оси у.

2.4

отр( точка( 5, Y1), точка( 5, Y2) )

2.5

регулярный( прямоугольник( точка( X1, Y1),

 точка( Х2, Y1), точкa( X2, Y3),

 точка( X1, Y3) ) ).

Здесь предполагается, что первая точка соответствует нижней левой вершине прямоугольника.

2.6

(a) А = два

(b) no

(c) С = один

(d) D = s(s(1));

   D = s(s(s(s(s(1)))))

2.7

родственники( X, Y) :-

 предок( X, Y);

 предок( Y, X);

 предок( Z, X),

 предок( Z, Y);

 предок( X, Z),

 предок( Y, Z).

2.8

преобразовать( 1, один).

преобразовать( 2, два).

преобразовать( 3, три).

2.9

В случае, изображенном на рис. 2.10, пролог-система выполняет несколько больший объем работы.

2.10

В соответствии с определением сопоставления, приведенном в разд. 2.2, данное сопоставление будет успешным. X приобретает вид циклической структуры, в которой сам X присутствует в качестве одного из аргументов.

3.1

(a) конк( L1, [ _, _, _ ], L)

(b) конк( [ _, _, _ ], L1, L),

     % Удалить 3 первые элемента L

    конк( L2, [ _, _, _ ], L1)

     % Удалить 3 последние элемента L1

Вот более короткий вариант, предложенный I. Tvrdy:

конк( [ _, _, _ | L2], [ _, _, _ ], L)

3.2

(а) последний( Элемент, Список) :- 

   конк( _, [Элемент], Список).

(b) последний( Элемент, [Элемент]).

   последний( Элемент, [Первый | Остальные]):-

    последний( Элемент, Остальные).

3.3

четнаядлина( [] ).

четнаядлина( [Первый | Остальные] ) :-

 нечетнаядлина( Остальные).

нечетнаядлина( [ _ ] ).

нечетнаядлина( [Первый | Остальные] ) :-

 четнаядлина( Остальные).

3.4

обращение( [], []).

обращение( [Первый | Остальные], ОбращСпис): -

 обращение( Остальные, ОбращСписОстальных),

 конк( О6ращСписОстальных, [Первый], ОбращСпис).

3.5

% Такой предикат легко определить при помощи отношения обратить

палиндром( Список) :-

 обратить( Список, Список).

% Вот другое решение, не использующее обратить

палиндром1( [] ).

палиндром1( [ _ ] ).

палиндром1 [Первый | Остальные] ) :-

 конк( Середина, [Первый], Остальные),

 палиндром1( Середина).

3.6

сдвиг( [Первый | Остальные], Сдвинут) :-

 конк( Остальные, [Первый], Сдвинут).

3.7

перевод( [], []).

перевод( [Голова | Хвост], [Голова1 | Хвост1]) :-

 означает( Голова, Голова1),

 перевод( Хвост, Хвост1).

3.8

подмножество( [], [] ).

подмножество( [Первый | Остальные], [Первый | Подмн]):-

  % Оставить первый элемент в подмножестве

 подмножество( Остальные, Подмн).

подмножество( [Первый | Остальные], Подмн) :-

  % Убрать первый элемент из подмножества

 подмножество( Остальные, Подмн).

3.9

разбиениесписка( [], [], []). % Разбивать нечего

разбиениесписка( [X], [X], []).

 % Разбиение одноэлементного списка

разбиениесписка( [X, Y | Список], [X | Список1],

 [Y | Список2]) :-

 разбиениесписка( Список, Список1, Список2).

3.10

можетзавладеть( состояние( _, _, _, имеет), [] ).

  % Ничего не надо делать

можетзавладеть( Состояние, [Действие | Действия]):-

 ход( Состояние, Действие, НовоеСостояние),

  % Первое действие

 можетзавладеть( НовоеСостояние, Действия).

  % Оставшиеся действия

3.11