Назад | Содержание| Вперёд Глава 5 УПРАВЛЕНИЕ ПЕРЕБ...

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

Глава 5

УПРАВЛЕНИЕ ПЕРЕБОРОМ

Мы уже видели, что программист можетуправлять процессом вычислений по программе,располагая ее предложения и цели в том или иномпорядке. В данной главе мы рассмотрим еще односредство управления, получившее название"отсечение" (cut) и предназначенное дляограничения автоматического перебора.

5. 1. Ограничение перебора

В процессе достижения цели пролог-системаосуществляет автоматический перебор вариантов,делая возврат при неуспехе какого-либо из них.Такой перебор - полезный программный механизм,поскольку он освобождает пользователя отнеобходимости программировать его самому. Сдругой стороны, ничем не ограниченный переборможет стать источником

Рис. 5. 2. Вточке, помеченной словом "ОТСЕЧЕНИЕ",уже известно,

что правила 2 и 3 должныпотерпеть неудачу.

При вычислении первой цели f( l, Y) Y конкретизируется нулем. Поэтому вторая цельстановится такой:

2 < 0

Она терпит неудачу, а поэтому и весь списокцелей также терпит неудачу. Это очевидно, однакоперед тем как признать, что такому списку целейудовлетворить нельзя, пролог-система при помощивозвратов попытается проверить еще двебесполезные в данном случае альтернативы.Пошаговое описание процесса вычисленийприводится на рис. 5.2.

Три правила, входящие в отношение f,являются взаимоисключающими, поэтому успехвозможен самое большее в одном из них.Следовательно, мы (но не пролог-система) знаем,что, как только успех наступил в одном из них, нетсмысла проверять остальные, поскольку они всеравно обречены на неудачу. В примере, приведенномна рис. 5.2, о том, что в правиле 1 наступил успех,становится известно в точке, обозначенной словом"ОТСЕЧЕНИЕ". Для предотвращениябессмысленного перебора мы должны явно указатьпролог-системе, что не нужно осуществлять возврат из этой точки. Мы можем сделатьэто при помощи конструкции отсечения. "Отсечение"записывается в виде символа '!',который вставляется между целями и играет рольнекоторой псевдоцели. Вот наша программа,переписанная с использованием отсечения:

f( X, 0) :- X < 3, !.

f( X, 2) :- 3 =< X, X <6, !.

f( X, 4) :- 6 =< X.

Символ '!' предотвращает возврат из техточек программы, в которых он поставлен. Если мытеперь спросим

?- f( 1, Y), 2 < Y.

то пролог-система породит левую ветвь дерева,изображенного на рис. 5.2. Эта ветвь потерпитнеудачу на цели 2 < 0. Система попытается сделать возврат, но вернутьсяона сможет не далее точки, помеченной в программесимволом '!' . Альтернативные ветви,соответствующие правилу 2 и правилу 3, порожденыне будут.

Новая программа, снабженная отсечениями, вовсех случаях более эффективна, чем первая версия,в которой они отсутствуют. Неудачные вариантыновая программа распознает всегда быстрее, чемстарая.

Вывод: добавив отсечения, мы повысилиэффективность. Если их теперь убрать, программапородит тот же результат, только на его получениеона истратит скорее всего больше времени. Можносказать, что в нашем случае после введенияотсечений мы изменили только процедурный смыслпрограммы, оставив при этом ее декларативныйсмысл в неприкосновенности. В дальнейшем мыпокажем, что использование отсечения может такжезатронуть и декларативный смысл программы.

5. 1. 2. Эксперимент 2

Проделаем теперь еще один эксперимент совторой версией нашей программы. Предположим, мызадаем вопрос:

?- f( 7, Y).

Y = 4

Проанализируем, что произошло. Перед тем, какбыл получен ответ, система пробовала применитьвсе три правила. Эти попытки породили следующуюпоследовательность целей:

Попытка применить правило 1:

7 < 3 терпит неудачу,происходит возврат, и попытка применить правило 2(точка отсечения достигнута не была)

Попытка применить правило 2:

3 <= 7 успех, но 7 < 6 терпит неудачу; возврат и попыткаприменить правило 3 (точка отсечения снова недостигнута)

Попытка применить правило 3:

6 <= 7 - успех

Приведенные этапы вычисления обнаруживают ещеодин источник неэффективности. В началевыясняется, что X < 3 неявляется истиной (7 < 3 терпитнеудачу). Следующая цель - 3 =< Х (3 <= 7- успех). Но нам известно, что, еслипервая проверка неуспешна, то вторая обязательнобудет успешной, так как второе целевоеутверждение является отрицанием первого.Следовательно, вторая проверка лишняя исоответствующую цель можно опустить. То же самоеверно и для цели 6 =< Х в правиле 3.Все эти соображения приводят к следующей, болееэкономной формулировке наших трех правил:

если Х < 3, то Y= 0

иначе, если 3 <= X и Х < 6, то Y = 2,

иначе Y = 4.

Теперь мы можем опустить в нашей программе теусловия, которые обязательно выполняются прилюбом вычислении. Получается третья версияпрограммы:

f( X, 0) :- X < 3, !.

f( X, 2) :- X < 6, !.

f( X, 4).

Эта программа дает тот же результат, что иисходная, но более эффективна, чем обепредыдущие. Однако, что будет, если мы теперьудалим отсечения? Программа станет такой:

f( X, 0) :- X < 3.

f( X, 2) :- X < 6.

f( X, 4).

Она может порождать различные решения, часть изкоторых неверны. Например:

?- f( 1, Y).

Y = 0;

Y = 2;

Y = 4;

nо (нет)

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

Более точный смысл механизма отсеченийможно сформулировать следующим образом:

Назовем "целью-родителем" ту цель, котораясопоставилась с головой предложения,содержащего отсечение. Когда в качестве целивстречается отсечение, такая цель сразу жесчитается успешной и при этом заставляет системупринять те альтернативы, которые были выбраны смомента активизации цели-родителя до момента,когда встретилось отсечение. Все оставшиеся вэтом промежутке (от цели-родителя до отсечения)альтернативы не рассматриваются.

Чтобы прояснить смысл этого определения,рассмотрим предложение вида

Н :- В1, В2, ..., Вm, !, ...,Вn.

Будем считать, что это предложениеактивизировалось, когда некоторая цель G сопоставилась с Н. Тогда G являетсяцелью-родителем. В момент, когда встретилосьотсечение, успех уже наступил в целях В1, ..., Вm. При выполнении отсечения это(текущее) решение В1, ..., Вm "замораживается" и все возможные оставшиесяальтернативы больше не рассматриваются. Далее,цель G связывается теперь с этимпредложением: любая попытка сопоставить G с головой какого-либо другого предложенияпресекается.

Применим эти правила к следующему примеру:

С :- Р, Q, R, !, S, Т, U.

С :- V.

А :- В, С, D.

?- А.

Здесь А, В, С, D, Р и т.д. имеютсинтаксис термов. Отсечение повлияет навычисление цели С следующим образом.Перебор будет возможен в списке целей Р, Q, R; однако, как только точкаотсечения будет достигнута, все альтернативныерешения для этого списка изымаются израссмотрения. Альтернативное предложение,входящее в С:

С :- V.

также не будет учитываться. Тем не менее,перебор будет возможен в списке целей S, Т, U. "Цель-родитель" предложения,содержащего отсечения, -это цель С впредложении

А :- В, С, D.

Поэтому отсечение повлияет только на цель С. С другой стороны, оно будет "невидимо" изцели А. Таким образом, автоматическийперебор все равно будет происходить в спискецелей В, С, D, вне зависимости отналичия отсечения в предложении, котороеиспользуется для достижения С.

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

Оглавление