Переривання пошуку з вертанням: відсікання

 

Vіsual Prolog передбачає можливість переривання пошуку з вертанням, застосовуючи предикат відсікання cut (позначається знаком оклику!). Його дія проста: крізь нього неможливо зробити відкат (бектрекінг).

Відсікання вміщується в програму в такий же спосіб, як і підціль у тілі правила. Коли процес проходить крізь відсікання, негайно задовольняється звернення до cut і виконується звернення до чергової підцілі (якщо така є). Вперше пройшовши крізь відсікання, уже неможливо зробити відкат до підцілей, розташованих у твердженні до відсікання, і так само неможливо повернутись до інших тверджень щодо оброблюваного предикату.

Існують два основних випадки застосування відсікання cut:

1. Коли заздалегідь відомо, що певні посилки ніколи не призведуть до осмислених рішень (пошук таких рішень буде зайвою витратою часу), застосовують відсікання зайвих гілок виводу, - програма стає швидшою й ефективнішою. Такий прийом називають зеленим відсіканням.

2. Коли відсікання вимагає сама логіка програми для виключення з розгляду альтернативних підцілей. Це - червоне відсікання.

Іншими словами, предикат cut обмежує автоматичний перебір. Для багатьох задач виникає проблема або ж  обмеження бектрекінгу, або ж виключення його зовсім.

Розглянемо спочатку програму, процес обчислень в якій містить непотрібний перебір. Нехай потрібно реалізувати функцію y=f(x), яка визначається наступним чином:

 

якщо х < 10, тоді у = 10;

якщо 10 ≤ х < 20, тоді у = 20;

якщо 20 ≤ х, тоді у = 30.

 

На Прологу її можна визначити наступною програмою:  

Predicates

 f(integer,integer).

   clauses

 f(X,10):- X < 10.

f(X,20):- X ≥ 10, X < 20.

f(X,30):- X ≥ 20.

Проаналізуємо, що зробить програма, коли їй задати наступний запит:

goal: f(5,Y), Y > 20.

При обчисленні цілі f(5,Y) першою, Y приймає значення 10, тому друга підціль стане 10 > 20. Вона закінчується невдачею. Але зрозуміло, що й весь список підцілей, який буде перевірятись завдяки бектрекінгу, також буде закінчуватись невдачею.

Всі три правила обчислення функції f є взаємовиключними. Тому відомо, що якщо успіх наступив в одному з них, нема потреби перевіряти інші, бо вони приречені на невдачу. Отже, якщо в якійсь точці програми настав успіх, для відміни непотрібного перебору ми повинні явно вказати системі, що не потрібно робити повернення із цієї точки. Це можна зробити за допомогою предикату cut. Попередня програма прийме вигляд:

   predicates

f(integer,integer).

   clauses

 f(X,10):- X < 10,!.

f(X,20):- X ≥ 10, X < 20,!.

f(X,30):- X ≥ 20.

Предикат cut не дає робити повернення із тих точок програми, в яких він поставлений і програма стала ефективнішою. Але в разі запиту типу:

Goal: f(22,Y)

система зробить три перевірки, перш ніж зв'яже Y із значенням 30. Але ж перевірки взаємовиключні. Тому для підвищення ефективності можна запропонувати такий варіант програми:

   predicates

f(integer,integer).

   clauses

 f(X,10):- X < 10,!.

f(X,20):- X < 20,!.

f(X,30).

В цьому випадку предикат відсікання міняє й декларативну сутність програми.

Предикат cut по-різному діє на складний запит і на множину фраз.

 

Запобігання пошуку з вертанням до попередньої підцілі в правилі.

 

Розглянемо випадок, коли предикат відсікання є однією із підцілей складного запиту:

G oal

  a(X),b(Y),!,c(X,Y,Z)

При виконанні цього запиту система пройде через предикат cut тільки в тому випадку, коли підціль а(X) i підціль b(Y) будуть задоволені. Після того, як підціль cut буде оброблена, система не зможе зробити відкат через відсікання й знайти альтернативні рішення для викликів а та b, якщо підціль с не задовільниться при поточних значеннях Х і Y.

Розглянемо ще один приклад використання cut.

Predіcates

buy_car(symbol,symbol)

Car (symbol,symbol,іnteger)

Colors(symbol,symbol)

Clauses

buy_car(Model,Color):- car(Model,Color,Prіce),

                    colors(Color,sexy),!,Prіce < 25000.

Car(maseratі,green,25000).

Car(corvette,black,24000).

Car(corvette,red,26000).

Car(porsche,red,24000).

Colors(red,sexy).

Colors(black,mean).

Colors(green,preppy).

Goal

buy_car(corvette,Y).

 

У даному прикладі поставлена ціль: знайти corvette (Корвет) приємного кольору, що підходить за вартістю. Відсікання в правилі buy_car означає, що оскільки в базі даних утримується тільки один "Корвет" приємного кольору, хоч і із занадто високою ціною, то нема потреби шукати іншу машину. Одержавши цільове твердження: buy_car(corvette, Y),

програма зробить наступні кроки:

1.звернеться до car, першої підцілі з тіла предиката buy_car;

2.виконає перевірку для першої моделі, maseratі, що буде невдалою;

3.потім перевірить наступне твердження для car і знаходить відповідність, зв'язуючи змінну Color зі значенням black;

4.переходить до наступного виклику й перевіряє, чи має обрана машина приємний колір. Колір black не є приємним у даній програмі, отже перевірка завершується невдало;

5.виконує пошук з вертанням до виклику car і знов шукає corvette, що задовольняє цьому критерію;

6.знаходить відповідність і знову перевіряє колір. Цього разу колір виявляється приємним, і Vіsual Prolog переходить до наступної підцілі в правилі: до відсікання. Відсікання негайно виконується, "заморожуючи" всі змінні, раніше зв'язані в цьому твердженні;

7.переходить до наступної (і останньої) підцілі в правилі, до порівняння Prіce < 25000;

8.перевірка завершується невдало, і Vіsual Prolog намагається зробити пошук з вертанням з метою знайти іншу машину для перевірки. Відсікання запобігає спробі вирішити останню підціль, і наше цільове твердження завершується вдало, але без означень змінних.

Для пояснення дії предикату cut повернемось до процесу керування побудови виведення в Прологу. Нехай програма має наступний вигляд.

Р: - a,b.

P: - c,d.

Цю програму, використовуючи поняття процедури, можна прочитати наступним чином. При виконанні процедури р виконуються процедури a та b. Якщо вони закінчаться успішно, то й процедура р вважається успішно завершеною. Інакше виконуються процедури с та d. Процедура р вважається задоволеною, якщо успішними є процедури с та d. Інакше р закінчується невдало.

Такий алгоритм обробки можна реалізувати на дереві типу “ і ” - “ або ”, де Ù позначає вузол типу “ або ”, а A позначає вузол типу “ і ”:

                        Р

 

 

           а          b c          d

Вершина типу “ і ” успішно розв`язувана лише тоді, коли її вершини сини успішно вирішені. Вершина типу “ або ” успішно розв`язувана, коли хоча б одна з її вершин-синів успішно розв`язувана.

Згідно стратегії пошуку вглиб, яка використовується в Прологу, проводиться послідовний перегляд дерева “ і - або ” зверху - донизу, зліва – направо. Це відповідає виділенню самої лівої підцілі запиту і впорядкуванню зверху - донизу правил програми.

Якщо при перегляді дерева якийсь з синів вершини типу “ або ” вирішується успішно, тоді обробка інших вершин синів (піддерева, яке знаходиться справа) призупиняється і вважається, що ця вершина типу “ або ” вирішилась успішно.

Якщо якась з вершин синів вершини типу “ і ” вирішується невдало, тоді обробка інших її вершин-синів закінчується невдало.

Зауважимо, що обробка вершини “ або ” не закінчується, а лише призупиняється. Це пов`язано з тим, що з часом можливе повернення до цієї вершини, і тоді гілки, які ще не аналізувались, можуть знову привести до успіху в цій вершині (бектрекінг).

Основна перевага такої стратегії - простота реалізації на послідовних машинах, недолік - великий перебір для деяких програм і запитів. До того ж, якщо дерево обчислень містить нескінченну гілку, тоді потрапивши на неї, ми не зможемо з неї вибратись і тому вірні відповіді, які лежать правіше від цієї гілки на дереві обчислень, не будуть знайдені.

Одним із засобів усунення вказаного недоліку є використання предикату cut. Таким чином відтинається (і іноді досить суттєво) дерево розгалуджень. Розглянемо програму:

а (Х): - b (Х),!, c (Х).

A (Х): - d (Х).

B(e).

B(f).

C(e).

C(f).

D(g).

На запит a(Z) програма побудує єдину відповідь Z=e, оскільки вона не буде повертатись до розгалуджень, які виникли до виклику cut (при обробці підцілей a(Z) і b(Z).

Якщо ж ми видалимо предикат cut з першого правила і побудуємо запит a(Z), тоді отримаємо три відповіді Z=e, Z=f, Z=g.

Зазначимо, що використання предикату cut робить програму ефективнішою, але програма позбавляється прозорої логічної семантики, залишається тільки процедурна семантика, яка відповідає обраній стратегії перегляду дерева.

Запобігання пошуку з вертанням до наступного твердження

Відсікання можна використати, як спосіб повідомити Vіsual Prolog, що він обрав вірне твердження для деякого предиката. Розглянемо програму:

r(1):-!, а, b, с.

r(2):-!, d.

r(3):-!, с.

r(_):- wrіte("Thіs іs a catchall clause.").

Використання відсікання робить предикат r детермінованим. У цьому випадку Vіsual Prolog виконує звернення до r з єдиним цілим аргументом. Припустимо, що зроблено виклик r(l). Система переглядає програму в пошуках відповідності для виклику; знаходить її з першим твердженням, що визначає r. Оскільки є більш ніж одне можливе рішення для даного виклику, Vіsual Prolog проставляє точку вертання біля цього твердження.

Тепер Vіsual Prolog починає обробку тіла правила, проходить через відсікання й виключає можливість вертання до іншого твердження r. Це скасовує точки пошуку вертання, підвищуючи ефективність виконання програми, а також гарантує, що помилкове твердження буде виконано лише, коли жодна з умов не буде відповідати зверненню до r.

Зверніть увагу, що така конструкція схожа на конструкцію case в інших мовах програмування; умова перевірки записується в заголовку правил. По можливості, завжди варто поміщати перевірочну умову саме в заголовок правила, - програма стає ефективнішою і простішою для читання.

 

Детермінізм і відсікання

Якби предикат r, визначений у попередній програмі, не містив відсікань, то це був би недетермінований предикат (здатний робити множинні рішення за допомогою пошуку з вертанням). Vіsual Prolog виконує перевірку тверджень на недетермінованість, полегшуючи роботу програмістів.

У Пролозі є директива компілятора check_determ. Якщо вставити її в самий початок програми, то Vіsual Prolog буде видавати попередження у випадку виявлення в процесі компіляції недетермінованих тверджень.

Можна перетворити недетерміновані твердження в детерміновані, вставляючи відсікання в тіло правил, що визначають відповідний предикат.