Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Топ:
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Интересное:
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2017-06-19 | 372 |
5.00
из
|
Заказать работу |
|
|
Отсечение (Cut)
Отсечение (т.е.!) есть предикат, который отсекает (cuts) недетерминизм, то есть отсекает возможность выработки дальнейших решений (сообразно своему имени).
Отсекаемый недетерминизм можно разбить на два группы (хотя в ряде случаев отсечения могут принадлежать обеим):
§ Отсечения, которые отсекают возможность выполнения других (следующих по порядку) клауз текущего предиката.
§ Отсечения, которые ликвидируют возможность генерации новых решений у недетерминированных вызовов предикатов.
Других значимых причин для использования отсечений нет, кроме двух, упомянутых выше. Если эти цели понятны, то очень просто ставить отсечения в правильном месте:
§ либо отсечение ставится в месте, где перебор последовательных клауз больше не требуется и/или
§ оно ставится после вызова недетерминированного (то есть с квалификацией nondeterm или multi) предиката, для которого важно только одно решение.
Первая причина может быть проиллюстрирована следующим примером
clauses
p(17, X):-
X > 13,
!,
q(X),
...
p(A, X):-
...
В этом примере у нас есть отсечение после проверки X > 13. Это типичный случай использования первой причины: "Наши клаузы реагируют на значение входной переменной и сразу (где сразу означает немедленно после проверки X > 13) мы находим правильное решение".
Обычно такого рода отсечения помещаются сразу после головы клаузы или после проверки, ближайшей к голове клаузы.
Вторая причина может быть проиллюстрирована на следующем примере:
clauses
firstMember(X, L):-
X = list::getMember_nd(L),
!.
В этом примере отсечение помещается немедленно после недетерминированного предиката, от которого мы ожидаем единственное решение.
Выше мы выделили слово немедленно дважды, поскольку ключевым словом в размещении отсечения является именно слово немедленно: они должны быть помещены настолько рано в клаузе, насколько это возможно.
|
Вы должны с подозрением относиться к клаузам, содержащим более одного отсечения. Наличие более одного отсечения в одном клаузе часто говорит о наличии ошибки в программе.
Красные и Зеленые отсечения
Вообще говоря, мы не поощряем зеленые отсечения, мы вполне уживаемся с красными отсечениями.
Сообщество традиционного Пролога дало определение красного и зеленого отсечений. Коротко это: зеленое отсечение - это отсечение, которое не меняет семантику предиката, в котором используется, а красное отсечение - меняет семантику.
Ясно, что все отсечения, которые отсекают все последующие решения недетерминированных предикатов являются красными по своей природе. Поэтому различия между красными и зелеными отсечениями имеют смысл только для тех отсечений, которые предотвращают откаты к следующим клаузам.
Рассмтрим клаузы:
clauses
p(X):-
X > 0,
!,
...
p(X):-
X <= 0,
...
В предикате выше отсечение является зеленым (green), поскольку, если мы его удалим, то предикат будет вести себя таким же образом. Когда отсечение имеется в первом клаузе, проверка X <= 0 во втором клаузе в действительности не нужна (второй клауз соответствует всем остальным случаям, кроме X<0 - прим. Переводчика):
clauses
p(X):-
X > 0,
!,
...
p(X):-
...
Но без этой проверки, однако, отсечение становится красным, поскольку теперь предикат будет вести себя по-другому, если мы удалим отсечение (предикат становится недетерминированным, поскольку, даже если X>0, появляется еще одно решение - хорошо, если безвредное - прим. Переводчика).
Зеленые отсечения могут показаться излишними, но в действительности они используются для исключения лишних вариантов отката (главным образом по соображениями скорости работы). В системе Visual Prolog они могут, однако, быть необходимыми для того, чтобы показать компилятору, что некоторые предикаты являются предикатами определенного типа, например, процедурами.
|
Рекурсия в прологе
Рекурсия - это второе средство для организации повторяющихся действий в Prolog'е. Рекурсивная процедура - это процедура, вызывающая сама себя до тех пор, пока не будет соблюдено некоторое условие, которое остановит рекурсию. Такое условие называют граничным. Рекурсия - хороший способ для решения задач, содержащих в себе подзадачу такого же типа.
Пример рекурсии: найти факториал n!.
Задача нахождения значения факториала n! очень хорошо решается с помощью рекурсии, поскольку может быть сведена к решению аналогичной подзадачи, которая, в свою очередь, сводится к решению аналогичной подподзадачи и т.д.
Действительно, чтобы найти значение факториала n!, можно найти значение факториала (n-1)! и умножить найденное значения на n. Для нахождения значения факториала (n-1)! можно пойти по уже известному пути - найти значение факториала (n-2)! и умножить найденное значения на n-1. Так можно действовать до тех пор, пока не доберемся до нахождения значения факториала (n-n)! или другими словами, факториала 0!. Значение факториала 0! известно - это 1. Вот это и будет граничное условие, которое позволит остановить рекурсию. Все, что теперь остается - это умножить полученную 1 на (n-(n-1)), затем на (n-(n-2)) и т.д. столько раз, сколько было рекурсивных вызовов. Результат n! получен.
Вот как выглядит программа, которая проделывает вычисление n! (нужно заметить, что предложения Prolog-программы достаточно точно повторяют формулировку задачи на естественном языке).
PREDICATES
|
|
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!