Практическое занятие 3. Управление процессом решения задачи. Поиск с возвратом. Рекурсия
Для управления поиском решений существует два стандартных предиката:
предикат fail (ложь), использующийся для поддержания поиска с возвратом;
предикат ! (cut, отсечение), использующийся для предотвращения поиска с возвратом.
Использование предиката fail
В Прологе реализован механизм поиска с возвратом (backtracking), при котором система пытается отыскать все возможные решения задачи. Механизм вывода программы запоминает те точки процесса унификации, в которых не были использованы все альтернативные решения, а затем возвращается в эти точки и ищет решение по иному пути.
При наличии нескольких фактов, поиск заканчивается после нахождения первого решения задачи. Например [Error: Reference source not found], в программе на рис. 3.1 находит только первое решение и заканчивает работу.
Рис.3.1. Пример нахождения одного решения
Если же нужно найти все решения, то в этом случае используется предикат fail. Предикат fail всегда дает неудачу в доказательстве, он вызывает искусственное неуспешное завершение поиска, что позволяет получить все возможные решения задачи и, таким образом, поддерживает поиск с возвратом.
Обратите внимание, что помещать подцель после fail в теле правила бесполезно. Предикат fail все время завершается неудачно, нет возможности для достижения подцели, расположенной после fail.
Рис 3.2. Пример программы с использованием предиката fail
После запуска программы, представленной на рис 3.2, будут напечатаны все названия городов.
Практикум 3-1
|
В Практикуме 2-1 Вы создавали базу знаний (БЗ), хранящую сведения о студентах (не менее 10) и их средних баллах.
Для решения задач воспользуйтесь встроенным предикатом fail. Какой результат выводится, если убрать предикат fail из правил? |
Использование предиката cut
Предикат отсечения1 «cut» обозначается с помощью символа !. Он позволяет получить доступ только к части данных, устраняя дальнейшие поисковые действия. В общем виде можно записать, например:
R : – A,B, !, C.
Это означает, что если для целей А и В найдено хотя бы одно решение, то дальнейший перебор возможных вариантов значений А и В не нужен.
Когда процесс проходит через отсечение, выполняется обращение к очередной подцели (если таковая имеется). Пройдя через отсечение, уже невозможно произвести откат к подцелям, расположенным в обрабатываемом предложении перед отсечением, и также невозможно возвратиться к другим предложениям, определяющим обрабатывающий предикат (предикат, содержащий отсечение).
Существуют два основных случая применения отсечения.
Если заранее известно, что определенные посылки никогда не приведут к осмысленным решениям (поиск решений в этом случае будет лишней тратой времени), Отсечение позволяет сделать программу быстрее и экономичнее. Такой прием называют зеленым отсечением.
Если отсечения требует сама логика программы для исключения из рассмотрения альтернативных подцелей. Это - красное отсечение.
Таким образом, зеленое отсечение не меняет семантики предиката, в котором оно используется. Красное отсечение, наоборот, меняет семантику. Для того чтобы определить цвет отсечения, необходимо удалить его из программы и посмотреть, как программа отвечает на поставленные вопросы, также, как программа без отсечения или по-другому. Как правило, различия проявляются, если в запросах использовать переменные.
На рис. 3.3 приведена программа, составляющая все возможные пары мальчик+девочка.
Рис 3.3. Пример программы без отсечения