Page 22 - 4800

2.7 Керування ходом виконання програм з використанням відсікання

Пролог містить засіб, що перешкоджає пошукові з поверненням при визначених
умовах. Ця операція називається відсіканням і виконується предикатом 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,Z) зазнає невдачі при поточних значеннях
змінних X, Y і Z.
– Запобігання переходу до наступної пропозиції процедури.
Нехай процедура опису предиката r складається з трьох правил. Позначимо
через r1, r2 і r3 – записи того самого предиката r у кожній із трьох пропозицій
процедури. Тоді два варіанти запису цієї процедури у вигляді:
а) r1(X,Y) if !, 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,Y).
Таким чином, якщо предикат fail ініціює бектрекінг (повернення до перебору
чергових альтернатив після першої знайденої), то предикат cut його завершує.

2.8 Застосування предикату NOT -- заперечення як неуспіх

Розглянемо фразу “Іван любить усі ігри крім баскетболу.” Спробуємо записати її
на Пролозі. Першу частину цього твердження виразити легко: “Іван любить довільне Х,
якщо Х – гра”, або ж :
like(„Іван”,X):-game(X).
Aлe ж потрібно виключити баскетбол. Це можна зробити, використавши інше
формулювання:
Якщо Х – баскетбол, тоді “Іван любить Х” не буде істиною, інакше, якщо Х –
гра, тоді “Іван любить Х”.

22