Отсечение применяется для устранения бесконечных циклов, при программировании взаимоисключающих утверждений и при необходимости неудачного завершения доказательства цели. Рассмотрим все три случая на примерах.
Пример 1. Устранение бесконечных циклов. Вновь обратимся к утверждениям, определяющим вычисление факториала (см. тему «Рекурсия»).
'факт'(0,1).
'факт'(K,F): - К1 is К-1, 'факт'(К1,F1), F is F1*К.
Введя запрос:
?- 'факт'(0,X).
получим
X=1 -> ;
Если мы поставим <;>, т.е. запросим еще решения, то Пролог сделает попытку сопоставить 'факт'(0,Х) со вторым утверждением 'факт'(К,F): -.. . Сопоставление успешно, и теперь делается попытка доказать цель 'факт'(-1,F1), что в свою очередь приводит к цели 'факт'(-2,F2) и так далее, т.е. образуется бесконечный цикл.
К счастью, можно устранить такие ситуации, используя отсечение, и тем самым указывая Прологу, что не существует других решений в случае успешного согласования граничного условия.
'факт'(0,1):-!.
'факт'(К,F):-К1 is К-1,'факт'(К1,F1),F is F1*К.
Учитывая данное определение 'факт' и задавая вопрос:
? - 'факт'(0,Х).
получаем единственное решение:
X=1 -> ;
no
Пример 2. Программирование взаимоисключающих утверждений. При оценке роста человека чаще всего пользуются не числовыми данными, а качественными определениями, например "Человек высокого роста" или "Он был ниже среднего роста". Можно связать эти качественные оценки с числовыми данными (Н - высота человека, см), например, следующим образом:
ОЧЕНЬ_ВЫСОКИЙ, если Н>200;
ВЫСОКИЙ, если 170<Н<=200;
РОСТ= ВЫШЕ_СРЕДНЕГО, если 160<Н<=170;
СРЕДНИЙ, если 150<Н<=160;
НИЖЕ_СРЕДНЕГО, если 140<Н<=150;
МАЛЕНЬКИЙ, если Н<140.
Тогда описать классификацию людей по росту можно с помощью следующих утверждений языка Пролог:
/* первый вариант программы */
'рост'(Н,'ОЧЕНЬ ВЫСОКИЙ'):- Н>200.
'рост'(Н,'ВЫСОКИЙ'):- Н>170,Н=<200.
'рост'(Н,'ВЫШЕ СРЕДНЕГО'):- Н>160,Н=<170.
'рост'(Н,'СРЕДНИЙ'):- Н>150,H=<160.
'рост'(Н,'НИЖЕ СРЕДНЕГО'):- Н>140,H=<150.
'рост'(Н,'МАЛЕНЬКИЙ'):- Н<140.
/* второй вариант программы */
'рост1'(Н,'ОЧЕНЬ ВЫСОКИЙ'):- Н>200,!.
'рост1'(Н,'ВЫСОКИЙ'):- Н>170,!.
'рост1'(Н,'ВЫШЕ СРЕДНЕГО'):- Н>160,!.
'рост1'(Н,'СРЕДНИЙ'):- Н>150,!.
'рост1'(Н,'НИЖЕ СРЕДНЕГО'):- Н>140,!.
'рост1'(Н,'МАЛЕНЬКИЙ').
В первом варианте программы тело каждого правила содержит все условия, описывающие человека данной категории, во втором варианте все правила, кроме последнего, содержат знаки отсечения "!".
В первом варианте программы при возврате независимо от уже найденного единственно верного решения вновь будут безуспешно просматриваться все остальные, лежащие ниже решения. На это затрачивается много времени. Во второй программе благодаря отсечению просмотр остальных решений производиться не будет. Рассмотрим, что произойдет, если знаки отсечений удалить из утверждений. Тогда в ответ на запрос типа
? -'рост'(175,Х).
X='ОЧЕНЬ ВЫСОКИЙ' --->;
X='ВЫСОКИЙ' --->;
X='ВЫШЕ СРЕДНЕГО'-->;
X='СРЕДНИЙ'-->;
X='НИЖЕ СРЕДНЕГО'-->;
X='МАЛЕНЬКИЙ'-->;
no
будет получено несколько решений, из которых только первое верно, а остальные ошибочны. Таким образом, в данной программе отсечение несет двойную функцию: благодаря сокращению пространства поиска уменьшает время решения и, главное, отсекает неправильные варианты ответов на запрос, позволяя получить единственно правильное решение.
Чтобы определение роста стало полностью корректным, необходимо рассмотреть и такие случаи, когда значение Н задается либо меньшим 20 см, либо слишком большим(>300 см). И в том и в другом случаях доказательство должно завершаться неудачей (т.к. иметь подобный рост для человека нереально). Для этого во вторую программу введем еще одно утверждение:
'рост3'(Н,_) :- (Н<20;H>300),!,fail.
'рост3'(Н,'ОЧЕНЬ ВЫСОКИЙ'):- Н>200,!.
'рост3'(Н,'ВЫСОКИЙ') :- Н>170,!.
'рост3'(Н,'ВЫШЕ СРЕДНЕГО'):- Н>160,!.
'рост3'(Н,'СРЕДНИЙ') :- Н>150,!.
'рост3'(Н,'НИЖЕ СРЕДНЕГО') :- Н>140,!.
'рост3'(Н,'МАЛЕНЬКИЙ').
и обратимся к системе с запросом:
? - 'рост'(0,Х).
no
Сначала произойдет сопоставление запроса с головой первого утверждения. Цель (H<20; H>300) будет достигнута. Затем будет доказана цель - отсечение. Но когда встретится предикат fail, стоящий перед ним предикат отсечение остановит работу механизма возврата. В результате ответом на запрос будет "нет" (no). Преимущество введения предиката fail заключается в том, что выделяются случаи, когда доказательство утверждений должно закончиться неудачей.
|
Главная
Каталог файлов
