5 1 Ограничение перебора
5. 1. Ограничение перебора
В процессе достижения цели пролог-система осуществляет автоматический перебор вариантов, делая возврат при неуспехе какого-либо из них. Такой перебор -...
Рисунок 5 1 Двухступенчатая функция
Рисунок 5. 1. Двухступенчатая функция
неэффективности программы. Поэтому иногда требуется его ограничить или исключить вовсе. Для этого в Прологе предусмотрена конструкция "отсечение&q...
5 1 1 Эксперимент 1
5. 1. 1. Эксперимент 1
Проанализируем, что произойдет, если задать следующий вопрос:
?- f( 1, Y), 2 < Y....
Рисунок 5 2 В точке помеченной
Рисунок 5. 2. В точке, помеченной словом "ОТСЕЧЕНИЕ", уже известно,что правила 2 и 3 должны потерпеть неудачу.
При вычислении первой цели f( l, Y)&nbs...
5 1 2 Эксперимент 2
5. 1. 2. Эксперимент 2
Проделаем теперь еще один эксперимент со второй версией нашей программы. Предположим, мы задаем вопрос:
?- ...
5 2 Примеры использующие отсечение
5. 2. Примеры, использующие отсечение...
5 2 1 Вычисление максимума
5. 2. 1. Вычисление максимума
Процедуру нахождения наибольшего из двух чисел можно запрограммировать в виде отношения
mах( X, Y, Мах)
г...
5 2 2 Процедура проверки принадлежности списку дающая единственное решение
5. 2. 2. Процедура проверки принадлежности списку, дающая единственное решение
Для того, чтобы узнать, принадлежит ли Х списку L, мы пользовались отношением
&nb...
5 2 3 Добавление элемента к списку если он в нем отсутствует (добавление без дублирования)
5. 2. 3. Добавление элемента к списку, если он в нем отсутствует (добавление без дублирования)
Часто требуется добавлять элемент Х в список L только в том случае, когда в списке...
5 2 4 Задача классификации объектов
5. 2. 4. Задача классификации объектов
Предположим, что у нас есть база данных, содержащая результаты теннисных партий, сыгранных членами некоторого клуба. Подбор пар противников...
Упражнения
Упражнения
5. 1. Пусть есть программа:
р( 1). р( 2) :- !. ...
5 3 Отрицание как неуспех
5. 3. Отрицание как неуспех
"Мэри любит всех животных, кроме змей". Как выразить это на Прологе? Одну часть этого утверждения выразить легко: "Мэри любит всякого X...
Упражнения
Упражнения
5. 4. Даны два списка Кандидатыи Исключенные, напишите последовательность целей (используя принадлежити not), которая, при помощи перебора, найдет все элементы списка Кандидаты, не вход...
Рисунок 5 3 Еще одна программа для решения задачи о восьми ферзях
Рисунок 5. 3. Еще одна программа для решения задачи о восьми ферзях.
разность( Множ1, Множ2, Разность)
где все три множества представлены в виде сп...
5 4 Трудности с отсечением и отрицанием
5. 4. Трудности с отсечением и отрицанием
Используя отсечение, мы кое-что выиграли, но не совсем даром. Преимущества и недостатки применения отсечения были показаны на примерах и...
Резюме
Резюме
Отсечение подавляет перебор. Его применяют как для повышения эффективности программ, так и для повышения выразительности языка. Эффективность повышается путем прямого указания (при...
Литература
Литература
Различать "зеленые и "красные" отсечения предложил ван Эмден (1982).
van Emden M. (1982). Red and green cuts. Logic Programming Newsletter: 2....
