Масленникова О.Е., Попова И.В. Основы искусственного интеллекта
Подождите немного. Документ загружается.
- 171 -
Для преобразования рекурсии в хвостовую для предикатов
badcount2 и badcount3 достаточно воспользоваться отсечением, которое
уберѐт все точки возврата перед рекурсивным вызовом.
badcount2 (N):- N>=0, !, write (N), nl, NewN=N-1, badcount2 (NewN).
badcount2 (N):- write (―N – отрицательное число‖).
badcount3 (N):- write (N), nl, NewN=N+1, check(NewN), !, badcount3
(NewN).
check (M):- M>=0.
check (M):- M<0.
Пример итерационного программирования
Предложение Пролога называют итерационным, если:
− в теле предложения содержится один рекурсивный вызов;
− она содержит лишь единичные и итерационные предложения.
В Прологе итерационные конструкции как таковые отсутствуют, более
общее понятие рекурсия используется как в рекурсивных, так и
итерационных алгоритмах.
Главное преимущество итерации перед рекурсией состоит в
эффективности использования памяти. При выполнении рекурсии, каждый
рекурсивный вызов не завершенный к некоторому моменту времени требует
определенной структуры данных называемой фрагментом стека.
Итерационное программы обычно используют фиксированный объѐм памяти
независящий от числа итераций.
Пример: Вычисление факториала
1. Рекурсивное решение
Факт(0, 1).
Факт(N, F):-M=N-1, Факт(M, K), F=F*N.
2. Итерационное решение.
2.1 Паскаль
i:=0; F:=1;
while i<n do
begin
inc(i);
F:=F*i
end;
2.2 Пролог
Факт(N, F):- Факт(0, N, 1, F).
Факт(I, N, T, F):- I<N, I1=I+1, I1=T*I1, Факт(I1, N, T1, F).
Факт(N, N, F, F).
- 172 -
В Прологе отсутствуют локальные переменные для удержания
промежуточных результатов и их изменения в процессе вычисления.
Поэтому для реализации итерационных алгоритмов, требующих сохранение
промежуточных результатов, процедуры Пролога дополняются аргументами
называемыми накопителями. Обычно промежуточные значения
соответствуют результату вычисления при завершении итерации. Это
значение сопоставляется результирующей переменной с помощью
единичного предложения процедуры.
2.22 Пролог
Факт2(N, F):- Факт2(N1, F).
Факт2(N, T, F):- N>0, T1=T*N, N1=N-1, Факт2(N1, T1, F).
Факт2(0, F, F).
Подводя итог рассмотренным понятиям данного пункта, отметим, что
любая рекурсивная процедура должна включать в себя базис и шаг
рекурсии.
Базис рекурсии – это предложение, определяющее некую начальную
ситуацию или ситуацию в момент прекращения. Как правило, в этом
предложении записывается некий простейший случай, при котором ответ
получается сразу даже без использования рекурсии. Это предложение часто
содержит условие, при выполнении которого происходит выход из рекурсии
или отсечение.
Шаг рекурсии – это правило, в теле которого обязательно содержится,
в качестве подцели, вызов определяемого предиката. Если мы хотим
избежать зацикливания, определяемый предикат должен вызываться не от
тех же параметров, которые указаны в заголовке правила. Параметры
должны изменяться на каждом шаге так, чтобы в итоге либо сработал базис
рекурсии, либо условие выхода из рекурсии, размещенное в самом правиле.
В общем виде правило, реализующее шаг рекурсии, будет выглядеть так:
<имя определяемого предиката>:-
[<подцели>],
[<условие выхода из рекурсии>],
[<подцели>],
<имя определяемого предиката>,
[<подцели>].
Рекурсивные структуры данных в Прологе
Пролог позволяет определить рекурсивные типы данных. Примерами
рекурсивных типов данных служат списки и деревья.
Списки
Список – это объект данных, содержащий конечное число других
объектов (элементов списка). Список задается перечнем его элементов,
заключенным в квадратные скобки, элементы списка могут быть
- 173 -
структурированными. Порядок следования элементов является
существенным. Все элементы списка должны принадлежать одному и тому
же домену (исключая списки структур).
Список, содержащий числа 1, 2 и 3, записывается следующим образом:
[1, 2, 3]. Пустой список обозначается [].
Для объявления списка используется следующее описание домена:
<имя_домена>=<тип_элемента>*
Пример
DOMAINS
list_num=integer*
Затем в секции predicates должен быть описан работающий со списком
предика.
predicates
num(list_num
Собственно, список вводится в разделах goal или clauses.
Список является рекурсивным составным объектом, он состоит из двух
частей:
головы списка – первого элемента списка;
хвоста списка – списка, включающего все последующие элементы.
Пример
[1| [2, 3]]
голова списка 1
хвост списка [2, 3].
Операция деления списка на голову и хвост обозначается |. Запись
[Н|T] можно рассматривать и как новый список, в котором элемент Н
добавлен в голову списка Т. Имена для частей списка могут выбираться
произвольно.
Типовыми задачами обработки списков являются:
− проверка принадлежности к списку,
− выбор элемента списка,
− деление списка,
− состыковка списков
− выбор максимума (минимума),
− сортировка.
Так как список имеет рекурсивную составную структуру, для работы
со списками используется рекурсия.
Пример. Печать элементов списка
- 174 -
DOMAINS
integerlist=integer*
PREDICATES
printlist (integerlist)
CLAUSES
printlist ([]):- !. %для пустого списка ничего не
делать
printlist ([H|T]):- write (H), nl, printlist (T). %для непустого списка
%отделить голову, напечатать ее,
%продолжить печать для хвоста
%списка
Пример. Присоединение списка L2 к концу списка L1
domains
lint=integer *
int =integer
predicates
append(lint,lint,lint)
clauses
append([],L,L).
append( [N I LI], L2,[NIL3] ): - append(Ll,L2,L3).
goal
append([l,2,3],[4,5],X),write(X).
Пусть на вход поступили списки Ll= [1,2,3] , L2=[4,5] . Вначале
предикат имеет вид append( [1,2,3] , [4,5] , [] ). Пролог, действуя по второму
правилу, будет выталкивать очередной элемент первого списка в стек – до
исчерпания этого списка. Затем вступает в действие первое правило.
Третий список инициализируется вторым и получается append([] , [4,5] ,
[4,5]). Далее снова по второму правилу к первому и третьему спискам
приписывается вершина стека. Процесс заканчивается достижением
ситуации append([1,2,3], [4,5], [1,2,3,4,5]).
Составные списки
Составные списки – это списки, в которых используется более чем
один тип элементов.
Для работы со списками из разнотипных элементов нужны
специальные декларации, потому что Visual Prolog требует, чтобы все
элементы списка принадлежали одному типу.
Для создания списка, который мог бы хранить различные типы
элементов, в Прологе необходимо использовать функторы, потому что домен
- 175 -
может содержать более одного типа данных в качестве аргументов для
функторов.
Пример объявления доменов для списка, который может содержать
символы, целые строки или списки представлены ниже.
Domains % функторы 1, i, с и s
llist = l(list); i (integer); с (char); s (string)
list = llist*
Список
[ 2, 9, ["food", "goo"], "new" ]
должен быть представлен в Visual Prolog как:
[i(2), i(9), 1( [s("food") , s("goo")]), s("new")] % Корректно.
Пример
domains
llist = l(list); i(integer); c(char); s(string)
list = llist*
predicates
append(list,list,list) - procedure (i,i,o)
clauses
append([],L,L).
append([X|L1],L2,[X|L3]):-
append(L1,L2,L3).
goal
append([s("likes"), l([s("bill"), s("mary")])],[s("bill"), s("sue")],Ans),
append([l([s("This"),s("is"),s("a"),s("list")]),s("bee")], [c('c')],Ans2).
Некоторые часто используемые предикаты работы со списками
представлены в прил. 3.
Деревья
Для введения понятия «дерева» необходимо восстановить несколько
терминов из теории графов.
Обычно графом называют пару множеств: множество вершин и
множество дуг (множество пар из множества вершин). Различают
ориентированные и неориентированные графы. В ориентированном графе
каждая дуга имеет направление (рассматриваются упорядоченные пары
вершин). Графически обычно принято изображать вершины графа точками, а
связи между ними – линиями, соединяющими точки-вершины.
Путѐм называется последовательность вершин, соединенных дугами.
Для ориентированного графа направление пути должно совпадать с
направлением каждой дуги, принадлежащей пути. Циклом называется путь,
у которого совпадают начало и конец.
- 176 -
Две вершины ориентированного графа, соединенные дугой,
называются отцом и сыном (или главной и подчиненной вершинами).
Известно, что если граф не имеет циклов, то обязательно найдѐтся хотя бы
одна вершина, которая не является ничьим сыном. Такую вершину называют
корневой. Если из одной вершины достижима другая, то первая называется
предком, вторая – потомком.
Деревом называется граф, у которого одна вершина корневая,
остальные вершины имеют только одного отца и все вершины являются
потомками корневой вершины.
Листом дерева называется его вершина, не имеющая сыновей. Кроной
дерева называется совокупность всех листьев. Высотой дерева называется
наибольшая длина пути от корня к листу.
Рекурсивное определение бинарного дерева: дерево либо пусто, либо
состоит из корня, а также левого и правого поддеревьев, которые в свою
очередь также являются деревьями.
Другим словами, бинарное дерево определяется рекурсивно как
имеющее левое поддерево Л, корень К и правое поддерево П. Такие деревья
можно представить термами bintree(n,K,n). Отсутствующие поддеревья
обозначаются стандартным термином nil. Тогда дерево на рис. 74 можно
представить конструкцией:
bin-tree(bintree(bintree(nil,d,nil),b,bintree(nil,e.nil)), a, bintree(nil,с,f)).
В вершинах дерева может храниться информация любого типа. Каждой
вершине дерева можно поставить в соответствие список еѐ
непосредственных преемников.
Рис. 74. Примеры бинарных деревьев
В вершинах дерева может храниться информация любого типа. Для
простоты в этой лекции будем считать, что в вершинах дерева располагаются
целые числа. Тогда соответствующее этому определению описание
альтернативного домена будет выглядеть следующим образом:
- 177 -
DOMAINS
tree=empty;tr(i,tree,tree)
/* дерево либо пусто, либо
состоит из корня (целого числа),
левого и правого поддеревьев,
также являющихся деревьями */
Такое определение позволяет записать следующую структуру данных:
tree(5,
tree(3,
tree(6, empty, empty),
tree(4, empty, empty)),
tree(10,
tree(2, empty, empty),
tree(8, empty, empty)))
Заметим, что идентификатор empty не является зарезервированным
словом Пролога. Вместо него вполне можно употреблять какое-нибудь
другое обозначение для пустого дерева . Например, можно использовать для
обозначения дерева , не имеющего вершин, идентификатор nil, как в Лиспе,
или void, как в Си. То же самое относится и к имени домена (и имени
функтора): вместо tree (tr) можно использовать любой другой
идентификатор.
Представление упорядоченного множества бинарным деревом
позволяет ускорить выборку его элементов. Дерево должно быть
упорядочено так, чтобы любой элемент в левом поддереве был меньше
корня, а в правом поддереве – больше.
Пример. Предикат, который будет проверять принадлежность
значения дереву.
Предикат будет иметь два аргумента. Первым аргументом будет
исходное значение, вторым - дерево, в котором мы ищем данное значение.
Следуя рекурсивному определению дерева , заметим, что некоторое
значение принадлежит данному дереву , если оно либо содержится в корне
дерева , либо принадлежит левому поддереву, либо принадлежит правому
поддереву. Других вариантов нет.
Запишем это рассуждение на Прологе.
tree_member(X,tr(X,_,_)):-!. /* X - является корнем
дерева */
tree_member(X,tr(_,L,_)):-
tree_member(X,L),!. /* X принадлежит
левому поддереву */
- 178 -
tree_member(X,tr(_,_,R)):-
tree_member(X,R). /* X принадлежит
правому поддереву */
Для работы с бинарными деревьями необходимы дополнительные
процедуры упорядочения линейного списка, преобразования списка в
бинарное дерево и обратно, добавления элемента к древовидному списку.
Одной из наиболее частых операций с деревом является обход узлов
дерева и выполнение некоторых действий с ними.
Пример. Вывод значений всех узлов дерева
DOMAINS
treetype =tree(integer, treetype, treetype); empty()
PREDICATES
print_tree(treetype)
CLAUSES
print_tree(empty): -!.
print_tree(tree(Root, Left, Right)):- write(Root), nl, print_tree(Left),
print_tree(Right).
GOAL
print_tree(tree(5,tree(3,tree(6, empty, empty),tree(4, empty,
empty)),tree(10,tree(2, empty, empty),tree(8, empty, empty)))).
Пример. Предикат замены в дереве всех вхождений одного значения
на другое. У предиката будет четыре аргумента: три входных (значение,
которое нужно заменять; значение, которым нужно заменять; исходное
дерево ), четвертым - выходным - аргументом будет дерево , полученное в
результате замены всех вхождений первого значения на второе.
Базис рекурсивного решения будет следующий. Из пустого дерева
можно получить только пустое дерево. При этом абсолютно неважно, что
на что мы заменяем. Шаг рекурсии зависит от того, находится ли
заменяемое значение в корне дерева . Если находится, то нужно заменить
корневое значение вторым значением, после чего перейти к замене первого
значения на второе в левом и правом поддереве. Если же в корне
содержится значение, отличное от заменяемого, то оно должно остаться.
Замену нужно произвести в левом и правом поддеревьях.
tree_replace(_,_,empty,empty). /* пустое дерево
остается пустым деревом*/
tree_replace(X,Y,tr(X,L,R),tr(Y,L1,R1)):-
/* корень содержит заменяемое
значение X*/
!,tree_replace(X,Y,L,L1),
/* L1 - результат замены
- 179 -
в дереве L всех вхождений X
на Y */
tree_replace(X,Y,R,R1).
/* R1 - результат замены
в дереве R всех вхождений X
на Y */
tree_replace(X,Y,tr(K,L,R),tr(K,L1,R1)):-
/* корень не содержит
заменяемое значение X */
tree_replace(X,Y,L,L1),
/* L1 - результат замены
в дереве L всех вхождений X
на Y */
tree_replace(X,Y,R,R1).
/* R1 - результат замены
в дереве R всех вхождений X
на Y */
Пример. Предикат, подсчитывающий общее количество вершин
дерева.
У него будет два параметра. Первый (входной) параметр - дерево,
второй (выходной) - количество вершин в дереве.
Базис: в пустом дереве количество вершин равно нулю. Шаг
рекурсии: чтобы посчитать количество вершин дерева , нужно посчитать
количество вершин в левом и правом поддереве, сложить полученные
числа и добавить к результату единицу (посчитать корень дерева ).
tree_length (empty,0). /* В пустом дереве
нет вершин */
tree_length(tr(_,L,R),N):-
tree_length (L,N1),
/* N1 - число вершин
левого поддерева */
tree_length (R,N2),
/* N2 - число вершин
правого поддерева */
N=N1+N2+1. /* число вершин
исходного дерева
получается сложением
N1, N2 и единицы */
Пример. Разработать предикат, подсчитывающий не общее
количество вершин дерева, а только количество листьев , т.е. вершин, не
имеющих сыновей. Предикат будет иметь два параметра. Входной -
- 180 -
исходное дерево , выходной - количество листьев дерева , находящегося в
первом параметре.
tree_leaves(empty,0). /* в пустом дереве
листьев нет */
tree_leaves(tr(_,empty,empty),1):-!.
/* в дереве с одним корнем -
один лист */
tree_leaves(tr(_,L,R),N):-
tree_leaves(L,N1),
/* N1 - количество листьев
в левом поддереве */
tree_leaves(R,N2),
/* N2 - количество листьев
в правом поддереве */
N=N1+N2.
Пример. Предикат, находящий сумму чисел, расположенных в
вершинах дерева. Он будет иметь два аргумента. Первый - исходный
список, второй - сумма чисел, находящихся в вершинах дерева ,
расположенного в первом аргументе.
Идея реализации немного похожа на подсчет количества вершин.
Базис рекурсии: сумма элементов пустого дерева равна нулю, потому что в
пустом дереве нет элементов. Чтобы подсчитать сумму значений,
находящихся в вершинах непустого дерева , нужно сложить сумму
элементов, хранящихся в левом и правом поддереве, и не забыть добавить
корневое значение.
tree_sum (empty,0). /* В пустом дереве
вершин нет */
tree_sum(tr(X,L,R),N):-
tree_sum (L,N1),
/* N1 - сумма элементов
левого поддерева */
tree_sum (R,N2),
/* N2 - сумма элементов
правого поддерева */
N=N1+N2+X. /* складываем N1, N2
и корневое значение */
Пример. Предикат, позволяющий вычислить высоту дерева
tree_height(empty,0). /* Высота пустого
дерева равна нулю */
tree_height(tr(_,L,R),D) :-