Неизвестно - Prolog

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

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

1. 3. Рекурсивное определение правил

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

Рис. 1. 5. Пример отношения предок:

(а) X- ближайший предок Z; (b) X- отдаленный предок Z.

между собой отношением родитель-ребенок, как показано на рис.1.5. В нашем примере на рис. 1.1 Том - ближайший предок Лиз и отдаленный предок Пат.

Первое правило простое и его можно сформулировать так:

Для всех X и Z,

X - предок Z, если

X - родитель Z.

Это непосредственно переводится на Пролог как

предок( X, Z) :-

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

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

предок( X, Z) :-

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

предок( X, Z) :-

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

родитель( Y, Z).

предок( X, Z) :-

родитель( X, Y1),

родитель( Yl, Y2),

родитель( Y2, Z).

предок( X, Z) :-

родитель( X, Y1),

родитель( Y1, Y2),

родитель( Y2, Y3),

родитель( Y3, Z).

. . .

Рис. 1. 6. Пары предок-потомок, разделенных разным числом поколений.

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

Существует, однако, корректная и элегантная формулировка отношения предок- корректная в том смысле, что будет работать для предков произвольной отдаленности. Ключевая идея здесь - определить отношение предокчерез него самого. Рис 1.7 иллюстрирует эту идею:

Для всех X и Z,

X - предок Z, если

существует Y, такой, что

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

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

Предложение Пролога, имеющее тот же смысл, записывается так:

предок( X, Z) :-

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

предок( Y, Z).

Теперь мы построили полную программу для отношения предок, содержащую два правила: одно для ближайших предков и другое для отдаленных предков. Здесь приводятся они оба вместе:

предок( X, Z) :-

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

предок( X, Z) :-

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

предок( Y, Z).

Рис 1. 7. Рекурсивная формулировка отношения предок.

Ключевым моментом в данной формулировке было использование самого отношения предокв его определении. Такое определение может озадачить - допустимо ли при определении какого-либо понятия использовать его же, ведь оно определено еще не полностью. Такие определения называются рекурсивными . Логически они совершенно корректны и понятны; интуитивно это ясно, если посмотреть на рис. 1.7. Но будет ли в состоянии пролог-система использовать рекурсивные правила? Оказывается, что пролог-система очень легко может обрабатывать рекурсивные определения. На самом деле, рекурсия - один из фундаментальных приемов программирования на Прологе. Без рекурсии с его помощью невозможно решать задачи сколько-нибудь ощутимой сложности.

Возвращаясь к нашей программе, можно теперь задать системе вопрос: "Кто потомки Пам?" То есть: "Кто тот человек, чьим предком является Пам ?"

?- предок( пам, X).

X = боб;

X = энн;

X = пат;

X = джим

Ответы системы, конечно, правильны, и они логически вытекают из наших определений отношений предоки родитель. Возникает, однако, довольно важный вопрос: " Как в действительности система использует программу для отыскания этих ответов?"