Соответствующие процедуры, названные >пред1, >пред2, >пред3 и >пред4, показаны на рис. 2.16.
Есть существенная разница в поведении этих четырех декларативно эквивалентных процедур. Чтобы это продемонстрировать, будем считать, отношение >родитель определенным так, как показано на рис. 1.1 гл. 1. и посмотрим, что произойдет, если мы спросим, является ли Том предком Пат, используя все четыре варианта отношения >предок:
>?- пред1( том, пат).
>да
>?- пред2( том, пат).
>да
>?- пред3( том, пат).
>да
>?- пред4( том, пат).
>% Четыре версии программы предок
>% Исходная версия
>пред1( X, Z) :-
> родитель( X, Z).
>пред1( X, Z) :-
> родитель( X, Y),
> пред1( Y, Z).
>% Вариант а: изменение порядка предложений в исходной версии
>пред2( X, Z) :-
> родитель( X, Y),
> пред2( Y, Z).
>пред2( X, Z) :-
> родитель( X, Z).
>% Вариант b: изменение порядка целей во втором предложении
>% исходной версии
>пред3( X, Z) :-
> родитель( X, Z).
>пред3( X, Z) :-
> пред3( X, Y),
> родитель( Y, Z).
>% Вариант с: изменение порядка предложений и целей в исходной
>% версии
>пред4( X, Z) :-
> пред4( X, Y),
> родитель( Y, Z).
>пред4( X, Z):-
> родитель( X, Z).
Рис. 2.16. Четыре версии программы >предок.
В последнем случае пролог-система не сможет найти ответа. И выведет на терминал сообщение: "Не хватает памяти".
На рис. 1.11 гл. 1 были показаны все шаги вычислений по >пред1 (в главе 1 она называлась >предок), предпринятые для ответа на этот вопрос. На рис 2.17 показаны соответствующие вычисления по >пред2, >пред3 и >пред4. На рис. 2.17 (с) ясно видно, что работа >пред4 — бесперспективна, а рис. 2.17(а) показывает, что >пред2 довольно неэффективна по сравнению с >пред1: >пред2 производит значительно больший перебор и делает больше возвратов по фамильному дереву.
Такое сравнение должно напомнить нам об общем практическом правиле при решении задач: обычно бывает полезным прежде всего попробовать самое простое соображение. В нашем случае все версии отношения >предок основаны на двух соображениях:
• более простое — нужно проверить, не удовлетворяют ли два аргумента отношения >предок отношению >родитель;
• более сложное — найти кого-либо "между" этими двумя людьми (кого-либо, кто связан с ними отношениями >родитель и >предок).
Из всех четырех вариантов отношения >предок, >пред1 использует наиболее простое соображение в первую очередь. В противоположность этому >пред4 всегда сначала пробует использовать самое сложное. >Пред2 и >пред3 находятся между этими двумя крайностями. Даже без детального изучения процессов вычислений ясно, что
