Предотвращение перебора с возвратами

Система Prolog автоматически выполняет перебор с возвратами, если это необхо­димо для достижения цели. Автоматический перебор с возвратами представляет со­бой полезный принцип программирования, поскольку он освобождает программиста от необходимости явно обеспечивать в программе перебор с возвратами. С другой стороны, неуправляемый перебор с возвратами может вызвать снижение эффектив­ности программы. Поэтому иногда возникает необходимость управлять перебором с возвратами или даже предотвращать его. Такую задачу в языке Prolog можно вы­полнить с помощью оп&ратора отсечения.

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

Рассмотрим двухступенчатую функцию, показанную на рис. 5.1. Соответствующую зависимость между X и Y можно определить с помощью приведенных ниже правил.

Правило 1. Если X < 3, то Y = 0.

Правило 2. Если 3 =< X и X < б, то Y = 2.

Правило 3. Если б =< X, то Y = 4.

Эти правила можно записать на языке Prolog в виде бинарного отношения f( К,У)следующим образом:

f( X, О) :- X < 3, % Правило 1 f ( X, 2) :- 3 =< X, X < 6. I Правило 2 f( X, 4} :- 6 =< X. % Правило 3

Y

4 • *

г щ-------- &

_.—■—i—-6 i ■—•—■—■—-
з e x

Рис. 5.1. Двухступенчатая функция

В данной программе, безусловно, предполагается, что перед вызовом на выполне­ние отношения f ( X, Y) переменная X уже конкретизирована значением какого-либо числа, поскольку это требуется для операций сравнения.

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

Эксперимент 1

Проанализируем, что произойдет при выполнении следующего вопроса:

?- i ( 1, У) , 2 < Y.

При выполнении первой цели, £( 1, Y), переменная Y конкретизируется значе­нием 0. Поэтому вторая цель принимает следующий вид:

Lt; 0

Данная цель не достигается, поэтому не достигается и весь список целей. Причи­на этого очевидна, но, прежде чем принять, что данный список целей не достижим, система Prolog проверяет с помощью перебора с возвратами еще два бесперспектив­ных варианта. Подробная трассировка этого процесса показана на рис. 5.2.

Рис. 5.2. Трассировка выполнения, при которой в точке, обозначенной как "Оператор отсечения", уже известно, что цели, определенные правилами 2 и 3, на достижимы

Часть I. Язык Prolog

Приведенные выше три правила, касающиеся функциональной зааисимости f, являются взаимоисключающими, поэтому может быть достигнуто не больше одной заданной в них цели. Но система Prolog, в отличие от программиста, не имеет ин­формации о том, что после достижения цели, заданной одним правилом, нет смысла пытаться использовать другие правила, поскольку попытка их достижения неизбеж­но окончится неудачей. Б примере, приведенном на рис. 5.2, известно, что цель пра­вила 1 будет достигнута в точке, обозначенной как "Оператор отсечения". В этот мо­мент необходимо явно сообщить системе Prolog, что не нужно выполнять перебор с возвратами, чтобы предотвратить осуществление бесполезных действий. Эту задачу можно решить с использованием механизма отсечения. Оператор отсечения записы­вается как восклицательный знак (!) и вставляется между целями как своего рода псевдоцель. Рассматриваемая программа, переоформленная с использованием опера­торов отсечения, принимает вид

f ( X_f О) :- X < 3, ! .

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

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

Теперь символ ! предотвращает перебор с возвратами в тех точках, в которых он появляется в программе. Если после этого будет задан следующий вопрос:

?- £( 1, Y;, 2 < у.

система Prolog сформирует такую же левую ветвь трассировки выполнения, как по­казано на рис. 5,2. Выполнение данной ветви окончится неудачей при обработке це­ли 2 < 0. Затем система Prolog предпринимает попытку осуществить перебор с воз­вратами, но не сможет пройти точку в программе, обозначенную символом !, поэто­му альтернативные ветви, которые соответствуют правилам 2 и 3, так и не будут сформированы.

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

На основании этого можно сделать вывод, что введение в рассматриваемую про­грамму операторов отсечения позволило повысить ее эффективность. Но если в дан­ном примере будут удалены операторы отсечения, программа все равно выработает такие же результаты; просто она, возможно, будет затрачивать больше времени. В данном случае введение операторов отсечения привело лишь к изменению проце­дурного значения программы и не повлияло на результаты ее работы. Тем не менее ниже будет показано, что использование операторов отсечения способно также по­влиять и на результаты.