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

Братко Иван

Определение отношения

сумма1

можно разбить на два случая:

(1) Все три числа представляются пустыми списками. Тогда

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

(2) Все три числа имеют какую-то самую левую цифру и справа от нее - остальные цифры. То есть, они имеют вид:

[D1 | N1], [D2 | N2], [D | N]

В этом случае должны выполняться два условия:

 (а) Оставшиеся цифры, рассматриваемые как три числа N1, N2 и N, сами должны удовлетворять отношению

сумма1

, выдавая влево некоторый перенос C2 и оставляя некоторое

подмножество неиспользованных цифр

Циф2

.

 (b) Крайние левые цифры D1, D2 и D, а также перенос C2 должны удовлетворять отношению, показанному на рис. 7.1: C2, D1 и D2 складываются, давая в результате D и перенос влево. Это условие в нашей программе формулируется в виде отношения

суммацифр

.

Переводя это на Пролог, получаем:

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

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

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

Осталось только описать на Прологе отношение

суммацифр

. В его определении есть одна тонкая деталь, касающаяся применения металогического предиката

nonvar

. D1, D2 и D должны быть десятичными цифрами. Если хоть одна из этих переменных еще не конкретизирована, ее нужно конкретизировать какой-нибудь цифрой из списка

Циф2

. Как только такая конкретизация произошла, эту цифру нужно удалить из множества доступных цифр. Если D1, D2 и D уже конкретизированы, тогда, конечно, ни одна из доступных цифр "потрачена" не будет. В программе эти действия реализуются при помощи недетерминированного вычеркивания элемента списка. Если этот элемент - не переменная, ничего не вычеркивается (конкретизации не было). Вот эта программа:

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

 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

и

с

, тогда