- •Лабораторная работа № 7 Программирование интеллектуальных систем на языке Пролог Управление ходом выполнения программ в системе Турбо-Пролог (2 часть)
- •Организация повторяющихся процессов
- •Управление поиском с возвратом
- •Управление ходом выполнения программ с использованием отсечения
- •Использование метода отката и отсечения
- •Откат и отсечение при реализации отношений вида "один-ко-многим"
- •Ступенчатые функции и отсечение
- •Порядок выполнения лабораторной работы
Управление поиском с возвратом
Один из вариантов управления поиском с возвратом можно иллюстрировать на примере предиката do_answer, записанного в несколько другой форме.
do_answer(X) :-colleague(Z.Y),X==Z,write(" ",X," -> ",Y),nl,fail.
Альтернативная форма записи не изменяет сути данного правила, но дает возможность показать, что введением новых подцелей в правило можно управлять поиском с возвратом. Из этого примера видно, что вторая подцель может оказаться неуспешной из-за несоответствия служащего, унифицированного по первой подцели, со служащим, унифицированным через заголовок правила, т.е. введенного с клавиатуры. Неуспех унификации второй подцели приведет к тому, что откат возникнет до выдачи информации на экран и предикат fail не потребуется. Включен предикат fail в правило, чтобы вызвать откат, если условия правила будут выполнены и все правило окажется успешным.
show_menu:-makcwindow(l,7,15," Меню ",1,50,10,20), repeat, clearwindow, write(" 1 - процесс 1"), nl, write(" 2 - процесс 2"), nl, write(" 0 - выход "), nl, nl, write(" Ваш выбор -> "), readint( Menu ), Menu < 3, process( Menu ), stop_menu( Menu). stop_menu( 0 ) . stop_menu( _ ) :- fail.
Еще одним примером по управлению поиском с возвратом является процедура построения меню show_menu.
В ней repeat используется так, что после выхода из любого модуля, вызываемого предикатом process(), идет возврат в меню.
Исключением является выбор нуля, что вызывает окончание программы.
В данном правиле управление откатом используется дважды: в виде предикатов Menu
Подцель Menu
Если процедура process() завершится успехом, то система делает попытку выполнить процедуру stop_menu(), которая при любых, кроме 0, значениях выбора завершается неудачей, что вызывает откат к предикату repeat. При значении выбора равном 0 - она является истинным фактом, и программа завершается.
Задание 5.
Сохраните на диске Ваш рабочий файл с именем lab4.рго. Он нам скоро понадобится. Создайте новый файл lab4menu.pro, в котором, используя приведенные выше предикаты, напишите программу организации выполнения двух произвольных процессов с выбором их через меню. Процессы должны быть описаны соответствующими предикатами и иметь простейший вид. Например, открытие окна и выдача сообщения.
Запустите программу на выполнение. Затем, используя трассировку, внимательно изучите ход решения задачи, откаты и повторы, выполняемые программой.
Управление ходом выполнения программ с использованием отсечения
Турбо-Пролог содержит средство, препятствующее поиску с возвратом в определенных условиях. Эта операция называется отсечением и выполняется предикатом cut, который в программах обозначается восклицательным знаком (!). Воздействие этого средства просто сводится к прекращению поиска. Отсечение используется в двух случаях:
1. Для ограничения пространства поиска в случаях, когда заранее известно, что некоторые возможные пути не приведут к интересующим вас решениям, т.е. обработка их приведет к ненужной потере времени. С использованием отсечения программа решается быстрее и требует меньшего объема памяти.
2. Когда отсечение требуется по логике программы для:
- Недопущения возврата к предыдущей подпели правила при откате. Пусть какое-либо правило имеет вид:
r1(X,Y,Z) if a(X) , b(Y) , ! , c(X,Y,Z).
Правило, записанное в такой форме, указывает на то, что система пройдет через предикат cut только в том случае, если и подцель а(Х), и подцель b(Y) будут успешными. После того, как предикат cut будет обработан, система не сможет вернуться назад для повторного рассмотрения подцелей а(Х) и b(Y). если подцель c(X,Y^) потерпит неудачу при текущих значениях переменных X,Y и Z.
- Предотвращения перехода к следующему предложению процедуры.
Пусть процедура описания предиката г состоит из трех правил. Обозначим через r1. r2 и r3 - записи одного и того же предиката r в каждом из трех предложений процедуры. Тогда два варианта записи этой процедуры в виде:
a) r1(X,Y) if I, a(X),b(Y), c(X.Y). 6) r1(X,Y) if a(X), b(Y), c(X,Y), !.
r2(X,Y) if !,d(X,Y) r2(X,Y) if d(X,Y), !.
r3(X,Y) if e(X,Y) r3(X,Y) if e(X,Y)
соответствуют тому, что, в первом случае, при обработке предиката r будет использовано лишь одно из правил r1, r2, r3, а, во втором случае, истинность какого-либо одного из правил приводит к окончанию процедуры и исключению из рассмотрения всех записанных ниже.
Пример.
Процедуру поиска максимального из двух чисел можно записать в виде двух правил для предиката max. Но эти правила взаимно исключающие. Если неудачу терпит первое, то второе будет выполняться. Поэтому с использованием отсечения возможна значительно более короткая формулировка процедуры.
max(X,Y,X):-X> =Y max(X,Y,Y):-X< Y
max(X,Y,X):-X> =Y,! max(X,Y,X)
Таким образом, если предикат fail инициирует бектрекинг (возврат к перебору очередных альтернатив после первой найденной), то предикат cut его завершает.
Рассмотрим на простых примерах использование различных вариантов отсечения для управления ходом выполнения Пролог-программ.