Программирование рекурсивных правил

Рекурсия является мощным методом программирования, в котором от­но­ше­ния между объектами можно определить, только пользуясь самими опре­де­ляемыми соотношениями. В Prolog рекурсия приобретает особую важность, так как здесь отсутствуют циклические конструкции. Правила, определяемые этим методом, называются рекурсивными.

В рекурсивном определении выделяют граничное и общее условия. Решить задачу позволяют именно граничные условия, так как в них происходит до­казательство целей и рекурсивный процесс останавливается.

Определим рекурсивно сумму чисел от 0 до N.

Для того чтобы вычислить сумму чисел от 0 до 10, необходимо поставить цель

goal sum(10, F),!.

F=55

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

Можно программу видоизменить, чтобы не ставить отсечение в цели.

predicates

sum(integer, integer)

clauses

sum(0,0) if !.

sum(N,S) if N1=N-1,

sum(N1,S1),

S=S1+N.

goal sum(10, F).

F=55

1 Solution

Рассмотрим программирование рекурсивных правил на нечисловом примере.

domains

name=symbol

predicates

родитель(name,name)

clauses

родитель(pam,bob).

родитель(tom,bob).

…

родитель(pam,jim).

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

Для всех X и Z,

X —  предок Z, если   существует Y, такой, что

(1)    X — родитель Y и

(2)    Y — предок Z.

predicates

predok(name,name)

clauses

predok(X, Z) if родитель(X, Z).

predok(X, Z) if родитель(X, Y) and predok(Y, Z).

Можно задать системе вопрос: «Кто потомки Пам?» То есть: «Кто тот человек, чьим предком является Пам?»

goal predok(pam, Z).

Z=bob

Z=jim

Z=ann

Z=pat

4 Solutions

Решим еще несколько примеров.

Пример 1. Наибольший общий делитель.

Если заданы два целых числа X и Y, то их наибольший общий делитель D можно найти, руководствуясь следующими правилами:

• Если X и Y равны, то D равен X.
• Если X<Y, то D равен наибольшему общему делителю X разности X–Y.
• Если Y<X, то формулировка аналогична правилу (2), если X и Y поменять в нем местами.

predicates

nod(integer, integer, integer)

clauses

nod(X,X,X) if !.

nod(X,Y,D) if X<Y,

Y1=Y-X,

nod(X,Y1,D).

nod(X,Y,D) if Y<X,

nod(Y,X,D).

Пример 2. Нахождение пути между городами.

domains

town = symbol

distance = integer

predicates

road(town, town, distance)

route(town, town, distance)

clauses

road(tampa, houston, 200).

road(gordon, tampa, 300).

road(houston, gordon, 100).

road(houston, kansas_city, 120).

road(gordon, kansas_city, 130).

route(Town1, Town2, Distance) :- % (1)

road(Town1, Town2, Distance).

route(Town1, Town2, Distance) :- % (2)

road(Town1, X, Dist1),

route(X, Town2, Dist2),

Distance=Dist1+Dist2, !.

goal route(tampa, kansas_city, Dist).

Dist=320

1 Solution

Правило (2) является рекурсивным. При каждом обращении к этому пра­ви­лу должно выполняться перемещение на один город ближе к месту назна­че­ния. Отношение, описанное в заголовке правила (2), зависит от более простой версии самого себя, поскольку в правило (2) входит рекурсивная подцель. Пра­ви­ло (1) определяет условие окончания процесса рекурсии, то есть исходный вид процедуры. Если правило (1) станет истиной при выполнении запроса, то про­цесс рекурсии прекращается.

Пример 3. Генерация чисел.

Определим процедуру for (N1, N2, X), которая на бэктрекинге с помощью перебора порождает все целые числа, отвечающие условию
N1 <= X <= N2.

predicates

for(integer, integer, integer)

clauses

for (N1,N2,N1) if N1<=N2.

for (N1,N2,X)  if N1<N2,

N=N1+1,

for (N,N2,X).

goal for(1,4,K), S=K*2, write(K), write(" ", S), nl, fail.

1 2

2 4

3 6

4 8

No Solution

Пример 4. Опишем предикат, генерирующий бесконечное число циклов повторений поиска с возвратом.

predicates

repeat

clauses

repeat.

repeat if repeat.

Использовать repeat можно таким образом:

goal   repeat,

write(" возведение в квадрат числа ="),

readreal(X),

Y=X*X,

write(X," в степени 2 =",Y),nl,

write("продолжать да/нет(y/n)"),

readln(L),

L="n".

Предыдущая - Следующая >>

Tweet

Читайте также:

• Основные понятия представления знаний
• Логическая модель представления знаний
• Продукционная модель представления знаний
• Сетевая модель представления знаний

Добавить комментарий

Имя (обязательное)

E-Mail (обязательное)

Подписаться на уведомления о новых комментариях

Обновить

Отправить

Отменить