Цель работы: изучить встроенный механизм поиска с возвратом и инструментальные средства управления поиском решений.
Управление поиском. Использование предиката fail
Visual Prolog начинает поиск с возвратом, когда вызов завершается неудачно. В определенных ситуациях бывает необходимо инициализировать выполнение поиска с возвратом, чтобы найти другие решения. Visual Prolog поддерживает специальный предикат fail, вызывающий неуспешное завершение, и, следовательно, инициализирует возврат. Действие предиката fail равносильно эффекту от сравнения 2=3 или другой невозможной подцели.
fail не может быть согласован (он всегда неуспешен), поэтому VisualProlog вынужден повторять поиск с возвратом. При поиске с возвратом он возвращается к последнему обращению, которое может произвести множественные решения. Такое обращение называют недетерминированным. Недетерминированное обращение является противоположностью детерминированному обращению, которое может производить только одно решение.
Прерывание поиска с возвратом: отсечение
VisualProlog предусматривает возможность отсечения, которая используется для прерывания поиска с возвратом; отсечение обозначается восклицательным знаком (!). Действует отсечение просто: через него невозможно совершить откат (поиск с возвратом).
Существуют два основных случая применения отсечения:
– Если вы заранее знаете, что определенные посылки никогда не приведут к осмысленным решениям (поиск решений в этом случае будет лишней тратой времени), – примените отсечение и программа станет быстрее и экономичнее. Такой прием называют зеленым отсечением.
– Если отсечения требует сама логика программы для исключения из рассмотрения альтернативных подцелей. Это – красное отсечение.
Использование отсечений
Предотвращение поиска с возвратом к предыдущей подцели в правиле:
rl :- а, b,
!, c.
Такая запись является способом сообщить VisualProlog о том, что вас удовлетворит первое решение, найденное им для подцелей а и b. Имея возможность найти множественные решения при обращении к с путем поиска с возвратом, Пролог при этом не может произвести откат (поиск с возвратом) через отсечение и найти альтернативное решение для обращений а и b. Он также не может возвратиться к другому предложению, определяющему предикат rl.
Предотвращение поиска с возвратом к следующему предложению
Отсечение может быть использовано, как способ сообщить VisualProlog, что он выбрал верное предложение для определенного предиката. Например, рассмотрим следующий фрагмент:
r(1):-
!,
а, b, с.
r(2):-
!,
d.
r(3):-
!,
с.
r(_):- write(«This is a catchall clause.»).
Использование отсечения делает предикат r детерминированным. В данном случае, VisualProlog выполняет обращение к r с единственным целым аргументом. Предположим, что произведено обращение r(l). VisualProlog просматривает программу в поисках соответствия для обращения; он находит его с первым предложением, определяющим r. Поскольку имеется более чем одно возможное решение для данного обращения, VisualProlog проставляет точку возврата около этого предложения. Теперь VisualProlog начинает обработку тела правила, проходит через отсечение и исключает возможность возвращения к другому предложению r. Это отменяет точки поиска с возвратом, повышая эффективность выполнения программы, а также гарантирует, что отлавливающее ошибки предложение будет выполнено лишь в том случае, если ни одно из условий не будет соответствовать обращению к r.
Обратите внимание, что конструкция такого типа весьма похожа на конструкцию case в других языках программирования; условие проверки записывается в заголовке правил.
Однако следует, по возможности, помещать проверочное условие именно в заголовок правила – это повышает эффективность программы и упрощает ее чтение.
Порядок выполнения работы
1. Какие ответы даст программа, содержащая следующие факты и правила:
р(1).
р(2) : — !.
р(3).
Цели: р(Х); р(Х), р(У); р(Х), !, р(У).
Дать пояснения.
2. Составить программу решения двухступенчатой функции, используя бинарное отношение f(X,Y) , без применения отсечений; применив зеленые отсечения в двух первых правилах; используя красные отсечения.
Правило 1: если X<3, то Y=0.
Правило 2: если X>3 и X<6, то Y=2.
Правило 3: если X>=6, то Y=4.
3. Составить программу определения наименьшего (наибольшего) из двух чисел (X,Y) без применения отсечений и с применением зеленых и красных отсечений.
4. Выполнить задания согласно вариантам, используя предикаты fail, cut (!).
Варианты заданий
1. Составить все возможные варианты выплаты заданной суммы денег денежными знаками номиналом 1, 2, 5, 10, 50 и 100 рублей.
2. Составить все возможные варианты кода для кодового замка с 4-мя кнопка (цифрами и/или буквами). Длина кода – 2 знака.
3. Составить все возможные варианты влюбленных пар в компании из 3 мальчиков и 5 девочек.
4. Написать программу, которая выводит на экран все двоичные числа от 0 до 15.
5. Составить расписание всех игр (дома и в гостях) для группы из 4-х футбольных команд.
6. Найти все трехзначные числа, сумма цифр которого равна 14.
7. Найти все двухзначные числа, произведение цифр которого равно 18.
8. Подобрать все возможные числа от 0 до 9 при которых выражение
(A+B)C=A(B-C) верно.
9. Найти все трехзначные числа, сумма цифр которого равна произведению этих же цифр.
10. Подобрать все возможные числа от 0 до 9 при которых выражение (А+В)С=А(В+С)
Загрузка...
