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

3.4.Директиви комп`ютеру.

Ви можете включити в програму деякі директиви комп`ютеру безпосередньо в програмі або ж вибравши пункт меню Options /Compiler Directives. Наприклад, директиву include.

За допомогою директиви include ви можете підключити до програми написані вами попередньо процедури. Це робиться наступним чином. Додамо стрічку include “my.pro” на початок вашої програми. А в файлі my.pro описуються процедури, які використовуються в вашій програмі.

3.5.Бектрекінг.

Часто при вирішенні конкретних задач вам необхідно переглядати всі можливі шляхи розв'язку задачі. Якщо розглянутий шлях не дає відповіді, ви мусите переглянути альтернативний шлях. Такий підхід до розв'язку задач дістав назву бектрекінг.

Пролог реалізує бектрекінг таким чином. На початку пошуку вирішення поставленої проблеми, він розміщує маркер на місце проглядання і вибирає першу підціль. Якщо її вирішення закінчиться невдачею, тоді Пролог повертається в точку, відмічену маркером і пробує знайти альтернативну підціль. При поверненні в точку бектрекінгу, він звільня всі змінні, зв`язані після входу в дану точку.

Розглянемо наступну програму.

domains

name, thing = symbol

predicates

likes(name, thing)

reads(name)

is_inquisitive(name)

clauses

likes(john, wine).

likes(lance, skiing).

likes(Z,books) :-reads(Z),

is_inquisitive(Z).

likes(lance, books).

likes(lance, films).

reads(john).

is_inquisitive(join).

Задамо системі запитання у вигляді цілі, яка складається з двох підцілей:

likes(X,wine), likes(X,books)

Пролог починає виведення згідно основного принципу бектрекінгу. Підцілі повинні задовільнюватися послідовно зверху вниз.

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

Підціль likes(X, wine) відповідає факту likes(john, wine). Тому Х зв'язується з john. Потім Пролог пробує задовольнити наступну підціль справа. Виклик другої підцілі розпочинає новий пошук з Х = john. Перший пункт likes(john,wine) не відповідає підцілі likes(X,books), тому що wine не є тим же, що й books. Тому Пролог пробує підібрати наступний пункт. Подальший пошук визначається третім правилом бектрекінгу. Коли підціль відповідає голові, тоді наступним повинно задовільнятися тіло даного правила. Тіло правила в свою чергу створює нові підцілі, котрі повинні бути задоволені.

І накінець, четвертий принцип бектрекінгу говорить. Ціль буде задоволена, коли будуть знайдені відповідні факти для кожного рівня дерева цілі.

3.5.1.Бектрекінг з внутрішньою ціллю.

Бектерінг з внутрішньою ціллю ілюструється програмою:

predicates

type(symbol, symbol)

is_a(symbol, symbol)

lives(symbol, symbol)

can_swim(symbol)

goal

can_swim(What) ,

write("A ", What, " can swim.").

clauses

type(ungulate, animal).

type(fish, animal).

is_a(zebra, ungulate).

is_a(herring, fish).

is_a(shark,fish).

lives(zebra, on_land).

lives(frog, on_land).

lives(frog,in_water).

lives(shark, in_water).

can_swim(Y) :-

type(X, animal) ,

is_a(Y, X) , lives(Y,in_water).

Вправи.

3.1.Наберіть останню програму і, використовуючи директиву trace, розгляньте послідовність задоволення вмонтованої цілі.

3.2.Напишіть предикат Прологу, який буде визначати позицію букви в алфавіті:

alphabet-position (Letter, Position).

Наприклад Position=1 якщо Letter=a т.д.

3.3.Напишіть програму Пролога, яка б визначала і друкувала значення n!. Значення n вводиться з клавіатури і є цілим.

3.4.Напишіть програму, яка знаходить найменше спільне кратне двох цілих чисел a i b (значення яких вводяться з клавіатури) НСК(a,b) , скориставшись формулою:

, де НСД(a,b) позначає найбільший спільний дільник. Для знаходження НСД(a,b) використайте окремий предикат, який підключіть до вашої програми за допомогою директиви include.

4.КОНТРОЛЬ ПОШУКУ РІШЕНЬ.

Пролог має два спеціальні предикати, які дозволяють вам контролювать механізм бектрекінгу: предикат fail, котрий примушує запускати механізм бектрекінгу, і cut (позначається !), який використовується для відміни бектрекінгу.

4.1.Використання предикату fail.

Пролог запускає бектрекінг, коли чергове співставлення завершується невдачею. Предикат fail вироблює значення хибність, що позначає невдачу і примушує спрацьовувати бектрекінг. В наступному прикладі показано використання даного предикату для знаходження всіх можливих розв'язків.

domains

name = symbol

predicates

father(name, name)

everybody

clauses

father(leonard, katherine).

father(carl, jason).

father(carl, marilyn).

everybody :-

father(X, Y),

write(X, " is ", Y, "'s father\n"),

fail.

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

4.2.Відміна бектрекінгу.

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

Існує два основних правила використання cut:

1.Коли ви знаєте попередньо, що певні варіанти ніколи не дадуть поштовху в знаходженні розв'язку, тоді використання cut(зелений cut) відкидає перегляд альтернативних шляхів.

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

Іншими словами, предикат 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 є взаємовиключними. Тому ми знаємо, що якщо успіх