Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Топ:
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Интересное:
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2017-06-19 | 364 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!