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

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

nonvar( Элемент), !.

удалить( Элемент, [Элемент | Список ], Список).

удалить(Элемент, [А | Список], [А | Список1]) :-

удалить( Элемент, Список, Список1).

Полная программа для решения арифметических ребусов приводится на рис. 7.2. В программу включены также определения двух ребусов. Вопрос к пролог-системе для ребуса про DONALD'a, GERALD'a и ROBERT'a с использованием этой программы выглядит так:

?- ребус1( N1, N2, N), сумма( N1, N2, N).

% Решение числовых ребусов

сумма( N1, N2, N) :-

% Числа представлены в виде списков цифр

сумма1( N1, N2, N,

0, 0,

% Перенос справа и перенос влево равны 0

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], _ ).

% Все цифры доступны

сумма1( [], [], [], 0, 0, Цифры, Цифры).

сумма1( [D1 | N1], [D2 | N2], [D | N], C1, С, Циф1, Циф) :-

сумма1( Nl, N2, N, C1, C2, Циф1, Циф2),

суммацифр( Dl, D2, C2, С, Циф2, Циф).

суммацифр( Dl, D2, C1, D, С, Циф1, Циф) :-

удалить( D1, Циф1, Циф2),

% Выбор доступной цифры для D1

удалить( D2, Циф2, Циф3),

% Выбор доступной цифры для D2

удалить( D, Циф3, Циф),

% Выбор доступной цифры для D

S is D1 + D2 + C1,

D is S mod 10,

С is S div 10.

удалить( A, L, L) :-

nonvar( A), !.

% Переменная А уже конкретизирована

удалить( А, [А | L], L).

удалить( А, [В | L], [В | L1]) :-

удалить( A, L, L1).

% Примеры ребусов

ребус1( [D, O, N, A, L, D],

[G, E, R, A, L, D],

[R, O, B, E, R, T].

ребус2( [0, S, E, N, D],

[0, M, O, R, E],

[M, O, N, E, Y].

Рис. 7.2. Программа для арифметических ребусов.

Иногда этот ребус упрощают, сообщая часть решения в виде дополнительного ограничения, например D равно 5. В такой форме ребус можно передать пролог-системе при помощи сумма1:

?- сумма1( [5, O, N, A, L, 5],

[G, E, R, A, L, 5],

[R, O, B, E, R, T],

0, 0, [0, 1, 2, 3, 4, 6, 7, 8, 9], _ ).

Интересно, что в обоих случаях существует только одно решение, т.е. только один способ заменить буквы цифрами.

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

?- упростить( 1 + 1 + а, E).

E = а + 2

?- упростить( 1 + a + 4 + 2 + b + с, E).

E = а + b + с + 7

?- упростить( 3 + x + x, E).

E = 2*x + 3

7.2. Определите процедуру

добавить( Элемент, Список)

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

Список = [а, b, с | Хвост]

где Хвост — переменная. Цель

добавить( d, Список)

вызовет конкретизацию

Xвoст = [d | НовыйХвост]и

Список = [а, b, с, d | НовыйХвост]

Таким способом структура может наращиваться, включая в себя новые элементы. Определите также соответствующее отношение принадлежности.

Имеются три встроенные предиката для декомпозиции и синтеза термов: functor, argи =... Рассмотрим сначала отношение =.., которое записывается как инфиксный оператор. Цель

Терм =.. L

истинна, если L — список, начинающийся с главного функтора терма Терм, вслед за которым идут его аргументы. Вот примеры:

?- f( а, b) =.. L.

L = [f, а, b]

?- T =.. [прямоугольник, 3, 5].

T = прямоугольник( 3, 5)

?- Z =.. [p, X, f( X,Y) ].

Z = p( X, f( X,Y) )

Зачем может понадобиться разбирать терм на составляющие компоненты — функтор и его аргументы? Зачем создавать новый терм из заданного функтора и аргументов? Следующий пример показывает, что это действительно нужно.

Рассмотрим программу, которая манипулирует геометрическими фигурами. Фигуры — это квадраты, прямоугольники, треугольники, окружности в т.д. В программе их можно представлять в виде термов, функтор которых указывает на тип фигуры, а аргументы задают ее размеры:

квадрат( Сторона)

треугольник( Сторона1, Сторона2, Сторона3)

окружность( R)

Одной из операций над такими фигурами может быть увеличение. Его можно реализовать в виде трехаргументного отношения

увел( Фиг, Коэффициент, Фиг1)

где Фиги Фиг1 — геометрические фигуры одного типа (с одним в тем же функтором), причем параметры Фиг1равны параметрам Фиг, умноженным на Коэффициент. Для простоты будем считать, что все параметры Фиг, а также Коэффициентуже известны, т.е. конкретизированы числами. Один из способов программирования отношения увелтаков:

увел( квадрат( A), F, квадрат( А1) ) :-

A1 is F*A

увел( окружность( R), F, окружность( R1) ) :-

R1 is F*R1

увел( прямоугольник( А, В), F, прямоугольник( А1, В1)) :-

A1 is F*A, B1 is F*B.

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

Ниже приводится программа, в которой делается попытка (неудачная) справиться для начала хотя бы со всеми однопараметрическими фигурами при помощи одного предложения:

увел( Тип( Пар), F, Тип( Пар1) ):-

Пар1 is F*Пар.

Однако в Прологе подобные конструкции, как правило, запрещены, поскольку функтор должен быть атомом, и, следовательно, переменная Типсинтаксически не будет воспринята как функтор. Правильный метод — воспользоваться предикатом ' =..'. Тогда процедура увелбудет иметь обобщенную формулировку, пригодную для фигур любых типов:

увел( Фиг, F, Фиг1):-

Фиг =.. [Тип | Параметры],

умножспис( Параметры, F, Параметры1),

Фиг1 =.. [Тип | Параметры)].

умножспис( [], _, []).

умножспис( [X | L], F, [X1 | L1] ) :-

X1 is F*X, умножспис( L, F, L1).

Наш следующий пример использования предиката ' =..' связан с обработкой символьных выражений (формул), где часто приходится подставлять вместо некоторого подвыражения другое выражение. Мы определим отношение