Средство управления, предназначенное для ограничения автоматического перебора

Страницы работы

3 страницы (Word-файл)

Фрагмент текста работы

Рассмотрим средство управления, предназначенное для ограничения автоматического перебора – отсечение.  Отсечение записывается в виде символа «!», который вставляется между целями и играет роль некоторой псевдоцели. Символ «!» предотвращает возврат из тех точек программы, в которых он поставлен.

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

Например 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 поддерживает такой предикат. Это полезное средство, и его часто можно с выгодой применять вместо

Похожие материалы

Информация о работе