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

обычная прологовская нотация, поскольку в ней непосредственно выражается то, что программист имел в виду. С другой стороны, некоторые типы выражений также можно трактовать как своего рода списки. Например, для конъюнктов в исчислении высказываний подошло бы следующее спископодобное представление:

• истина соответствует пустому списку,

• & — оператор для соединения головы с хвостом, определяемый, например, как

:- op( 300, xfy, &)

Конъюнкция членов а, b, и с выглядела бы тогда как

а & b & с & истина

Все приведенные примеры базируются, по существу, на одной и той же структуре, представляющей список. Однако в гл. 8 мы рассмотрели существенно другой способ, влияющий на эффективность вычислений. Уловка состояла в том, что список представлялся в виде пары списков, являясь их 'разностью'. Было показано, что такое представление приводит к очень эффективной реализации отношения конкатенации.

Материал настоящего раздела проливает свет и на то различие, которое существует между применением операторов в математике и применением их в Прологе. В математике с каждым оператором всегда связано некоторое действие, в то время как в Прологе операторы используются просто для представления структур.

Упражнения

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

список( Объект)

для распознавания случаев, когда Объект является стандартным прологовским списком.

9.2. Определите отношение принадлежности к списку, используя систему обозначений, введенную в этой разделе: 'затем — ничего_не_делать'.

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

преобр( СтандСпис, Спис)

для преобразования списков из стандартного представления в систему 'затем — ничего_не_делать'. Например:

преобр( [а, b], а затем b затем ничего_не_делать)

ответ

9.4. Обобщите отношение преобр на случай произвольного альтернативного представления списков. Конкретное представление задается символом, обозначающим пустой список, и функтором для соединения головы с хвостом. В отношении преобр придется добавить два новых аргумента:

преобр( СтандСпис, Спис, Функтор, ПустСпис)

Примеры применения этого отношения:

?- пpeoбp( [а, b], L, затем, ничего_не_делать).
L = а затем b затем ничего_не_делать
?-  преобр( [а, b, с], L, +, 0).
L = а+(b+(с+0) )

9.1.2. Сортировка списков

Сортировка применяется очень часто. Список можно отсортировать (упорядочить), если между его элементами определено отношение порядка. Для удобства изложения мы будем использовать отношение порядка

больше( X, Y)

означающее, что X больше, чем Y, независимо от того, что мы в действительности понимаем под 'больше, чем'. Если элементами списка являются числа, то отношение больше будет, вероятно, определено как

больше( X, Y) :- X > Y.

Если же элементы списка — атомы, то отношение больше может соответствовать алфавитному порядку между ними.

Пусть

сорт( Спис, УпорСпис)

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

Для того, чтобы упорядочить список Спис, необходимо:

• Найти в Спис два смежных элемента X и Y, таких, что больше( X, Y) , и поменять X и Y местами, получив тем самым новый список Спис1; затем отсортировать Спис1.

• Если в Спис нет ни одной пары смежных элементов X и Y, таких, что больше( X, Y), то считать, что Спис уже отсортирован.

Мы переставили местами 2 элемента X и Y, расположенные в списке 'не в том порядке', с целью приблизить список к своему упорядоченному состоянию. Имеется в виду, что после достаточно большого числа перестановок все элементы списка будут расположены в правильном порядке. Описанный принцип сортировки принято называть методом пузырька, поэтому соответствующая прологовская процедура будет называться пузырек.

пузырек( Спис, УпорСпис) :-
 перест( Спис, Спис1), !, % Полезная перестановка?
 пузырек( Спис1, УпорСпис).
пузырек( УпорСпис, УпорСпис).
  % Если нет, то список уже упорядочен
перест( [X, Y | Остаток], [Y, X ) Остаток] ):-
 % Перестановка первых двух элементов
 больше( X, Y).
перест( [Z | Остаток], [Z | Остаток1] ):-
 перест( Остаток, Остаток1). % Перестановка в хвосте

Еще один простой алгоритм сортировки называется сортировкой со вставками. Он основан на следующей идее:

Для того, чтобы упорядочить непустой список L = [X | Хв], необходимо:

(1) Упорядочить хвост Хв списка  L.

(2) Вставить голову X списка L в упорядоченный хвост, поместив ее в такое место, чтобы получившийся список остался упорядоченным. Список отсортирован.

Этот алгоритм транслируется в следующую процедуру вставсорт на Прологе:

вставсорт([], []).