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

?- подсписок( S, [а, b, с] ).

S = [];

S = [a];

S = [а, b];

S = [а, b, с];

S = [b];

...

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

?- перестановка( [а, b, с], P).

P = [а, b, с];

P = [а, с, b];

P = [b, а, с];

...

Рис. 3.5. Один из способов построения перестановки списка [X | L].

Программа для отношения перестановкав свою очередь опять может основываться на рассмотрении двух случаев в зависимости от вида первого списка:

(1) Если первый список пуст, то и второй список должен быть пустым.

(2) Если первый список не пуст, тогда он имеет вид [X | L], и перестановку такого списка можно построить так, как это показано на рис. 3.5: вначале получить список L1 — перестановку L, а затем внести X в произвольную позицию L1.

Два прологовских предложения, соответствующих этим двум случаям, таковы:

перестановка( [], []).

перестановка( [X | L ], P) :-

перестановка( L, L1),

внести( X, L1, P).

Другой вариант этой программы мог бы предусматривать удаление элемента X из первого списка, перестановку оставшейся его части — получение списка P, а затем добавление X в начало списка P. Соответствующая программа такова:

перестановка2( [], []).

перестановка2( L, [X | P] ) :-

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

перестановка2( L1, P).

Поучительно проделать несколько экспериментов с нашей программой перестановки. Ее нормальное использование могло бы быть примерно таким:

?- перестановка( [красный, голубой, зеленый], P).

Как и предполагалось, будут построены все шесть перестановок:

P = [ красный, голубой, зеленый];

P = [ красный, зеленый, голубой];

P = [ голубой, красный, зеленый];

P = [ голубой, зеленый, красный];

P = [ зеленый, красный, голубой];

P = [ зеленый, голубой, красный];

no (нет)

Приведем другой вариант использования процедуры перестановка:

?- перестановка( L, [а, b, с] ).

Наша первая версия, перестановка, произведет успешную конкретизацию L всеми шестью перестановками. Если пользователь потребует новых решений, он никогда не получит ответ "нет", поскольку программа войдет в бесконечный цикл, пытаясь отыскать новые несуществующие перестановки. Вторая версия, перестановка2, в этой ситуации найдет только первую (идентичную) перестановку, а затем сразу зациклится. Следовательно, при использовании этих отношений требуется соблюдать осторожность.

3.3. Определите два предиката

четнаядлина( Список) и нечетнаядлина( Список)

таким образом, чтобы они были истинными, если их аргументом является список четной или нечетной длины соответственно. Например, список [а, b, с, d]имеет четную длину, a [a, b, c] — нечетную.

3.4. Определите отношение

обращение( Список, ОбращенныйСписок),

которое обращает списки. Например,

обращение( [a, b, c, d], [d, c, b, a] ).

3.5. Определите предикат

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

Список называется палиндромом, если он читается одинаково, как слева направо, так и справа налево. Например, [м, а, д, а, м].

3.6. Определите отношение

сдвиг( Список1, Список2)

таким образом, чтобы Список2представлял собой Список1, "циклически сдвинутый" влево на один символ. Например,

?- сдвиг( [1, 2, 3, 4, 5], L1),

сдвиг1( LI, L2)

дает

L1 = [2, 3, 4, 5, 1]

L2 = [3, 4, 5, 1, 2]

3.7. Определите отношение

перевод( Список1, Список2)

для перевода списка чисел от 0 до 9 в список соответствующих слов. Например,

перевод( [3, 5, 1, 3], [три, пять, один, три] )

Используйте в качестве вспомогательных следующие отношения:

означает( 0, нуль).

означает( 1, один).

означает( 2, два).

...

3.8. Определите отношение

подмножество( Множество, Подмножество)

где Множествои Подмножество — два списка представляющие два множества. Желательно иметь возможность использовать это отношение не только для проверки включения одного множества в другое, но и для порождения всех возможных подмножеств заданного множества. Например:

?- подмножество( [а, b, с], S ).

S = [a, b, c];

S = [b, c];

S = [c];

S = [];

S = [a, c];

S = [a];

...

3.9. Определите отношение

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

так, чтобы оно распределяло элементы списка между двумя списками Список1и Список2и чтобы эти списки были примерно одинаковой длины. Например:

разбиениесписка( [а, b, с, d, e], [a, с, e], [b, d]).

3.10. Перепишите программу об обезьяне и бананах из главы 2 таким образом, чтобы отношение

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

давало не только положительный или отрицательный ответ, но и порождало последовательность действий обезьяны, приводящую ее к успеху. Пусть Действиябудет такой последовательностью, представленной в виде списка ходов:

Действия = [ перейти( дверь, окно),

передвинуть( окно, середина),

залезть, схватить ]

3.11. Определите отношение

линеаризация( Список, ЛинейныйСписок)

где Списокможет быть списком списков, а ЛинейныйСписок — это тот же список, но "выровненный" таким образом, что элементы его подсписков составляют один линейный список. Например:

?- линеаризация( [а, d, [с, d], [], [[[e]]], f, L).

L = [a, b, c, d, e, f]

В математике мы привыкли записывать выражения в таком виде:

2*a + b*с

где + и * — это операторы, а 2 , а , b , с — аргументы. В частности, + и * называют инфиксными операторами, поскольку они появляются между своими аргументами. Такие выражения могут быть представлены в виде деревьев, как это сделано на рис. 3.6, и записаны как прологовские термы с + и * в качестве функторов:

+( *( 2, а), *( b, с) )

Рис. 3.6. Представление выражения 2*а+b*с в виде дерева.