Информатика -продвинутый курс



РЕКУРСИЯ - часть 2


Ускорить выход из рекурсии можно, добавив к предикату «факт(1,1)» отсечение !:

факт(1,1):-!.

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

родитель(Х):- родитель(Y),отец(Y,Z).

родитель(коля).

отец(коля,петя).

родитель(петя).

В этом случае в первом предложении голова имеет ту же функцию, что и одна из целей - «родитель». В процессе поиска ответа в этой базе знаний будет применено правило: предложение, стоящее первым, будет применено первым - известное как принцип поиска в глубину.

Это приведет к тому, что система будет обращаться только к первому предложению базы знаний и ответ на вопрос не будет найден никогда (образуется бесконечная петля вывода). Однако небольшое изменение базы знаний - перестановка двух предложений местами - приведет к удачному поиску решения.

Программа 116

родитель(коля).

родитель(X):- родитель(Y), отец(Y,Х).

отец(коля,петя).

? - родитель(петя).

Неограннчено-повторное обращение к предложению может быть и более замаскированным так, как это получается в программе 117.

Программа 117

выше(А,В): - ниже(В,А).

ниже(В,А): - выше(А, В).

выше(коля,петя).

?- ниже(петя,коля).

Однако если третье предложение стоит на первом месте, то повторного обращения не произойдет и ответ будет найден.

В общем виде рекурсия на Прологе выглядит так:

Р(1,...).

P(n,...) -Q1,..., Qn, P(n-l,...), R1,... Rm.

Правило Р обращается само к себе, при этом происходит углубление рекурсии. Предикаты Q1, .... Qn выполняются на прямом ходе рекурсии, а R1,..., Rm - на обратном; n - это некоторый условный параметр, входящий в условие продолжения рекурсии, а Р(1,...)- факт, завершающий процесс рекурсии.

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

Использование repeat в качестве подцели некоторого правила приводит к многократному повторению остальных подцелей этого правила.




Содержание  Назад  Вперед