Рассмотрим средство управления, предназначенное для ограничения автоматического перебора – отсечение. Отсечение записывается в виде символа «!», который вставляется между целями и играет роль некоторой псевдоцели. Символ «!» предотвращает возврат из тех точек программы, в которых он поставлен.
Назовем целью-родителем ту цель, которая сопоставима с головой предложения, содержащего отсечение. Когда в качестве цели встречается отсечение, такая цель сразу же считается успешной и при этом заставляет систему принять те альтернативы, которые были выбраны с момента активизации цели-родителя до момента, когда встретилось отсечение. Все оставшиеся в этом промежутке (от цели-родителя до отсечения) альтернативы не рассматриваются.
Например H:-B1, B2, …, Bm, !, …, Bn. Будем считать, что предложение активизировалось когда некоторой цели G сопоставилась H. Тогда G является целью-родителем. В момент, когда встретилось отсечение, успех уже наступил в целях B1, B2, …, Bm. При выполнении отсечения текущее решение замораживается и все возможные оставшиеся альтернативы больше не рассматриваются.
Будем считать, что это предложение активизировалось, когда некоторая цепь G сопоставилась с Н. Тогда G является целью-родителем. В момент, когда встретилось отсечение, успех уже наступил в целях Bl, B2,..., Вт. При выполнении отсечения это (текущее) решение Bl, B2,..., Вт «замораживается» и все возможные оставшиеся альтернативы больше, не рассматриваются. Далее, цель G связывается теперь с этим предложением: любая попытка сопоставить G с головой какого-либо другого предложения пресекается.
Применим это правило к следующему примеру:
С :- Р, Q, R, !, S, T, U.
C:-V.
А :- В, С, D.
ЦЕЛЬ: А.
Здесь А, В, С, D, Р и т.д. имеют синтаксис термов. Отсечение повлияет на вычисление цели С следующим образом. Перебор будет возможен в списке целей Р, Q, R; однако, как только точка отсечения будет достигнута, все альтернативные решения для этого списка изымаются из рассмотрения. Альтернативное предложение, входящее в С:
С :- V.
также не будет учитываться. Тем не менее перебор будет возможен в списке целей S, T, U.
«Цель-родитель» предложения, содержащего отсечения, - это цель С в предложении
А :- В, С, D.
Поэтому отсечение повлияет только на цель С. С другой стороны, оно будет «невидимо» из цели А. Таким образом, автоматический перебор все равно будет происходить в списке целей В, С, D, вне зависимости от наличия отсечения в предложении, которое используется для достижения С.
УПРАВЛЕНИЕ ПЕРЕБОРОМ
При программировании на Прологе бывают полезными две особые цели trueи fail, true- всегда успешна, fail - всегда терпит неудачу. Функция fail осуществляет вынужденное неудачное завершение выполнения предиката и таким образом инициирует бектрекинг.
Сказать на Прологе, что что-то не есть истина, можно при помощи специальной цели fail (неуспех), которая всегда терпит неудачу, заставляя потерпеть неудачу и ту цель, которая является ее родителем.
Начнем с рассмотрения отношения различны (X, Y).
Определим отношение различны (X, Y), которое выполняется, если X и Y не совпадают. В данном случае давайте считать, что X и Y различны, если они не сопоставимы. Вот способ выразить это на Прологе:
Если X и Y сопоставимы, то цель различны ( X, Y) терпит неуспех иначе цель различны (X, Y) успешна. Запишем зто на Прологе, используя сочетание отсечения и fail:
различны (X, X):-!, fail, различны (X, Y).
То же самое можно записать и в виде одного предложения: различны (X, Y) :-X = Y, !, fail; true.
Эти примеры показывают, что полезно иметь унарный предикат «not» (не), такой, что (not) Цель истинна, если Цель не истинна. Определим отношение notследующим образом:
Если Цель успешна, то not (Цель) неуспешна, иначе not ( Цель) успешна.
Это определение может быть записано на Прологе так: ; not (Р) :-Р,!, fail;
true. .
Turbo Prolog поддерживает такой предикат. Это полезное средство, и его часто можно с выгодой применять вместо
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
