Иван Братко - Программирование на языке Пролог для искусственного интеллекта
Резюме
Примеры, рассмотренные в данном разделе, иллюстрируют некоторые достоинства и характерные черты программирования на Прологе:
• Базу данных можно естественным образом представить в виде множества прологовских фактов.
• Такие механизмы Пролога, как вопросы и сопоставление, можно гибко использовать для получения информации из базы данных. Кроме этого можно использовать вспомогательные процедуры-утилиты, еще больше облегчающие взаимодействие с конкретной базой данных.
• Абстракцию данных можно рассматривать как метод программирования, который облегчает работу со сложными структурами данных и вносит большую ясность и наглядность в программы. В Прологе легко соблюдать основные принципы абстракции данных.
• Часто легко можно осуществить перевод абстрактных математических конструкций, таких как автоматы, на язык определений Пролога, готовых к выполнению.
• Как это было в случае восьми ферзей, многие задачи допускают различные подходы, связанные с разными представлениями этих задач. Часто внесение избыточности в представление экономит вычисления. Происходит как бы проигрыш в рабочем пространстве, но выигрыш во времени.
• Часто основным шагом на пути к решению оказывается обобщение задачи. Парадоксально, но рассмотрение более общей задачи позволяет облегчить формулировку решения.
Глава 5
Управление перебором
Мы уже видели, что программист может управлять процессом вычислений по программе, располагая ее предложения и цели в том или ином порядке. В данной главе мы рассмотрим еще одно средство управления, получившее название "отсечение" (cut) и предназначенное для ограничения автоматического перебора.
5.1. Ограничение перебора
В процессе достижения цели пролог-система осуществляет автоматический перебор вариантов, делая возврат при неуспехе какого-либо из них. Такой перебор — полезный программный механизм, поскольку он освобождает пользователя от необходимости программировать его самому. С другой стороны, ничем не ограниченный перебор может стать источником неэффективности программы. Поэтому иногда требуется его ограничить или исключить вовсе. Для этого в Прологе предусмотрена конструкция "отсечение".
Рис. 5.1. Двухступенчатая функция
Давайте сначала рассмотрим простую программу, процесс вычислений, по которой содержит ненужный перебор. Мы выделим те точки этого процесса, где перебор бесполезен и ведет к неэффективности.
Рассмотрим двухступенчатую функцию, изображенную на рис. 5.1. Связь между X и Y можно определить с помощью следующих трех правил:
Правило 1: если X < 3, то Y = 0
Правило 2: если 3 ≤ X и X < 6, то Y = 2
Правило 3: если 6 ≤ X, то Y = 4
На Прологе это можно выразите с помощью бинарного отношения
f( X, Y)
так:
f( X, 0) :- X < 3. % Правило 1
f( X, 2) :- 3 =< X, X < 6. % Правило 2
f( X, 4) :- 6 =< X. % Правило 3
В этой программе предполагается, конечно, что к моменту начала вычисления f( X, Y) X уже конкретизирован каким-либо числом; это необходимо для выполнения операторов сравнения.
Мы проделаем с этой программой два эксперимента. Каждый из них обнаружит в ней свой источник неэффективности, и мы устраним оба этих источника по очереди, применив оператор отсечения.
5.1.1. Эксперимент 1
Проанализируем, что произойдет, если задать следующий вопрос:
?- f( 1, Y), 2 < Y.
Рис. 5.2. В точке, помеченной словом "ОТСЕЧЕНИЕ", уже известно, что правила 2 и 3 должны потерпеть неудачу.
При вычислении первой цели f( 1, 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 =< X (3 ≤ 7 — успех). Но нам известно, что, если первая проверка неуспешна, то вторая обязательно будет успешной, так как второе целевое утверждение является отрицанием первого. Следовательно, вторая проверка лишняя и соответствующую цель можно опустить. То же самое верно и для цели 6 =< X в правиле 3. Все эти соображения приводят к следующей, более экономной формулировке наших трех правил:
если X < 3, то Y = 0
иначе, если 3 ≤ X и 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о (нет)
Важно заметить, что в последней версии, в отличие от предыдущей, отсечения затрагивают не только процедурное поведение, но изменяют также и декларативный смысл программы.
Более точный смысл механизма отсечений можно сформулировать следующим образом:
