|
НАЗАД
Соответствующие процедуры, названные пред1, пред2, пред3 и пред4, показаны ниже.
% Четыре версии программы предок
% Исходная версия
пред1( X, Z) :-родитель( X, Z). %пр1
пред1( X, Z) :-родитель( X, Y), пред1( Y, Z). %пр2
% Вариант а: изменение порядка предложений в исходной версии
пред2( X, Z) :-родитель( X, Y), пред2( Y, Z). %пр1
пред2( X, Z) :-родитель( X, Z). %пр2
% Вариант b: изменение порядка целей во втором предложении исходной версии
предЗ( X Z) :-родитель( X, Z). %пр1
предЗ( X, Z) :-предЗ( X, Y), родитель( Y, Z). %пр2
% Вариант с: изменение порядка предложений и целей в исходной версии
пред4( X, Z) :-пред4( X, Y), родитель( Y, Z). %пр1
пред4( X, Z) :-родитель( X, Z). %пр2
Есть существенная разница в поведении этих четырех декларативно эквивалентных процедур. Чтобы это продемонстрировать, будем считать отношение родитель определенным так, как показано на рис.2 гл.I, и посмотрим, что произойдет, если мы спросим, является ли Том предком Пат, используя все четыре варианта отношения предок:
?- пред1( том, пат). да
?- пред2( том, пат), да
?- предЗ( том, пат), да
?- пред4( том, пат).
В последнем случае пролог-система не сможет найти ответа. И выведет на терминал сообщение: «Не хвастает памяти».
Работа пред4 - бесперспективна, а рис. 30(а) показывает, что пред2 довольно неэффективна по сравнению с пред1: пред2 производит значительно больший перебор и делает больше возвратов по фамильному дереву.
Такое сравнение должно напомнить нам об общем практическом правиле при решении задач: обычно бывает полезным прежде всего попробовать самое простое соображение. В нашем случае все версии отношения предок основаны на двух соображениях:
- более простое - нужно проверить, не удовлетворяют ли два аргумента отношения предок отношению родитель;
- более сложное - найти кого-либо «между» этими двумя людьми (кого-либо, кто связан с ними отношениями родитель и предок).
Из всех четырех вариантов отношения предок, пред1 использует наиболее простое соображение в первую очередь. В противоположность этому пред4 всегда сначала пробует использовать самое сложное. Пред2 и предЗ находятся между этими двумя крайностями. Даже без детального изучения процессов вычислений ясно, что пред1 следует предпочесть просто на основании правила «самое простое пробуй в первую очередь».
Наши четыре варианта процедуры предок можно далее сравнить, рассмотрев вопрос: «На какие типы вопросов может отвечать тот или иной конкретный вариант и на какие не может?» Оказывается, пред1 и пред2 оба способны найти ответ на любой вид вопроса относительно предков; пред4 никогда не находит ответа, а предЗ иногда может найти, иногда нет. Вот пример вопроса, на который пред3 ответить не может:
?- предЗ( лиз, джим).
Такой вопрос тоже вводит систему в бесконечную рекурсию. Следовательно, и предЗ нельзя признать верным с точки зрения процедурного смысла.
НАЗАД
|
