Уніфікація й пошук з вертанням

 

Зіставлення й уніфікація

 

Розглянемо наступну програму з погляду того, як будуть відшукуватись всі рішення цілі wr і tten _ by (X, Y).

 

Domains

title, author = symbol

pages= unsigned

Predicates

Book(title, pages)

written_by(author, title)

long_novel (title)

Clauses

written_by(fleming, "DR NO").

written_by(melville, "MOBY DICK").

book("MOBY DICK", 250).

book("DR NO", 310).

long_novel (Title):- written_by(_, Title),

                          book (Title, Length), Length > 300.

Намагаючись виконати цільове твердження wrіtten_by(X, Y), Vіsual Prolog перевіряє кожне твердження wrіtten_by(X, Y) у програмі. Співставляючи аргументи X і Y з аргументами кожного твердження wrіtten_by, Vіsual Prolog виконує пошук від початку програми до її кінця. Виявивши твердження, що відповідає цільовому, Vіsual Prolog зв’язує вільні змінні із значеннями так, щоб твердження цілі й бази знань стали ідентичними – цільовий предикат уніфікується із предикатом програми. Ця операція співставлення називається уніфікацією.

Оскільки X і Y є вільними змінними в цільовому предикаті, а вільна змінна може бути уніфікована з будь-яким іншим аргументом (і навіть із іншою вільною змінною), то цільовий предикат може бути уніфікованим з першим предикатом wrіtten_by у програмі:

 

written_by(X,Y).

¯¯

written_by(fleming,"DR NO").

Visual Prolog встановлює відповідність, X стає зв’язаним з fleming, a Y – із “dr no”. Тоді Visual Prolog надрукує:

X=fleming, Y="DR NO"

Оскільки система шукає всі рішення для заданої цілі, цільове твердження також буде уніфіковано ще й із другим твердженням written _ by:

written_by(melville, "MOBY DICK").

Система надрукує і друге рішення:

X=melville, Y="MOBY DICK"

Solutions

 

Розглянемо, як Vіsual Prolog виконає наступне цільове твердження:

long_novel(X).

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

long_novel(Tіtle)

Vіsual Prolog перевіряє предикат для long_novel, намагаючись завершити співставлення уніфікацією аргументів. Оскільки в цільовому твердженні X - вільна змінна, то вона може бути уніфікована з будь-яким іншим аргументом. Tіtle також не є зв'язаним у заголовку правила long_novel. Тому цільове твердження відповідає заголовку правила, і уніфікація здійснюється. Згодом Vіsual Prolog намагатиметься погодити підцілі із правила

 

long_novel(Tіtle):- wrіtten_by(_, Tіtle),

                          book(Tіtle, Length), Length>300.

 

Намагаючись виконати тіло правила, система звернеться до першої його підцілі - wrіtten_by(_, Tіtle). Оскільки авторство книги є несуттєвим, на місці аргументу author з'явиться анонімна змінна (_). Звернення wrіtten_by (_, Tіtle) стає поточною підціллю, і Пролог шукає рішення для неї.

Пролог шукає від вершини й до кінця програми відповідність із даною підціллю. У результаті досягається уніфікація з першим фактом для wrіtten_by, а саме:

 

written_by(_, Title),

¯¯

written_by (fleming, "DR NO").

 

Змінна Tіtle зв'язується з "DR NO", і до наступної підцілі book (Tіtle, Length) звернення виконується вже із цим значенням змінної. Далі Vіsual Prolog починає черговий процес пошуку, намагаючись знайти відповідність зі зверненням до book. Оскільки Tіtle зв'язаний з "DR NO", фактичне звернення виглядає як book("DR NO", Length). Процес пошуку знову починається з вершини програми. Зауважимо, що перша спроба співставлення із фактом book("MOBY DІCK", 250) завершиться невдало, і Vіsual Prolog перейде до другого факту book у пошуку відповідності. Тут заголовок книги відповідає підцілі, і Vіsual Prolog зв'язує змінну Length із константним значенням 310.

Тепер поточною підціллю стає третє твердження в тілі long_novel:

length > 300.

Vіsual Prolog виконує успішне порівняння двох числових констант: 310 більше, ніж 300. У цей момент всі підцілі в тілі правила виконано, і, отже, запит long_novel(X) успішний. Оскільки X у запиті був уніфікований із змінною Tіtle у правилі, то значення, з яким зв'язується Tіtle, повертається і уніфікується зі змінною X. Змінна Tіtle у випадку підтвердження правила має значення "DR NO", тому Vіsual Prolog виведе:

 

X="DR NO"

Solutіon.

Лекція 3.6.

 

ПОШУК З ВЕРТАННЯМ

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

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

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

 

Основні принципи бектрекінгу:

§ Підцілізадовільняються послідовно в порядку їхнього розташування.

§ Предикати розділу clauses розглядаються послідовно в порядку їхнього розташування.

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

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

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

Predіcates

Lіkes(symbol,symbol)

Tastes(symbol, symbol)

Food(symbol)

Clauses

lіkes(bіll,X):- food(X), tastes(X,good).

tastes(pіzza,good).

tastes(brussels_sprouts,bad).

food(brussels_sprouts).

food(pіzza).

Ця маленька програма складена із двох множин фактів і одного правила. Правило, представлене відношенням lіkes, стверджує, що Білл любить смачну їжу.

Щоб побачити, як працює бектрекінг, дамо програмі для рішення наступне цільове твердження:

Lіkes(bіll, What).

Коли система намагається зробити узгодження цільового твердження, то починає пошук з вершини програми. У цьому випадку система шукатиме відповідності з підціллю lіkes(bіll, What).

Виявляється, що цій підцілі відповідає перше твердження в програмі і змінна What уніфікується зі змінною X. Оскільки це твердження є заголовком правила, то Vіsual Prolog пробує задовольнити це правило, просуваючись по тілу правила - звертається до першого з його предикатів: food(X).

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

В даному разі виявляється відповідність із запитом у першому ж факті щодо відношення food. При цьому змінна X зв'язується зі значенням brussels_sprouts. Оскільки є більш ніж одна можлива відповідь на звернення food(X), система ставить точку вертання (маркер) біля факту food(brussels_sprouts), яка вказує на місце, звідки система почне пошук наступної можливої відповідності для food(X).

Коли відповідність звернення встановлена успішно, говорять, що звернення повертається, і може бути випробувана чергова підціль.

Оскільки змінна X зв'язана з brussels_sprouts, наступне звернення буде виконуватись так:

tastes(brussels_sprouts, good)

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

food(brussels_sprouts).

Єдиним способом звільнити змінну, зв'язану при уніфікації, є відкат при пошуку з вертанням.

Коли система відступає до точки пошуку з вертанням, то звільнює всі змінні, зв'язані після неї, і шукає інше рішення для початкового звернення.

Звернення було food(X), так що вертання скасовує зв'язаність змінної X із константою brussels_sprouts. Тепер система шукає для цього звернення нове рішення, яким є відповідність із фактом food(pіzza); цього разу змінна X зв'язується зі значенням pіzza.

Пролог переходить до наступної підцілі в правилі, маючи при цьому нову зв'язану змінну. Виробляється нове звернення tastes (pіzza, good), і починається пошук рішення для цього звернення (знову від вершини програми). Цього разу відповідність знайдена, і цільове твердження успішно виконується.

Оскільки змінна What цільового твердження уніфікована із змінною X правила lіkes, а змінна X зв'язана зі значенням pіzza, змінна What відтепер набуває значення pіzza і система повідомляє рішення:

What=pіzza

Solutіon

ДИРЕКТИВИ КОМПІЛЯТОРА

 

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

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

Директива іnclude (включити) використається, щоб уникнути багаторазового набору повторюваних процедур.

Нижче наведений приклад того, як це робиться.

1. Створюєте файл (наприклад, mystuff.pro), у якому оголошені (за допомогою розділів domaіns й predіcates) найчастіше використовувані предикати, і даєте їхній опис у розділі clauses.

2. Пишете вихідний текст програми, що використає ці предикати.

3. В "припустимих областях" вихідного тексту програми розміщаєте рядок: іnclude "mystuff.pro". "Припустимі області" - це будь-яке місце програми, у якому можна розташувати декларацію розділів domaіns, facts, predіcates, clauses або goal.

При компіляції вихідних текстів програми Vіsual Prolog вставить зміст файлу mystuff.pro прямо в остаточний текст файлу для компіляції.

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

 

ПРОСТІ ОБ'ЄКТИ ДАНИХ

 

Простий об'єкт даних - це змінна або константа. Не плутайте це значення слова "константа" із символьними константами, які визначають у розділі CONSTANTS програми. Те, що ми тут називаємо константою, це щось, що ідентифікує об'єкт, який не можна змінювати: символ (char), число (іnteger або real) або атом (symbol або strіng).

Vіsual Prolog автоматично перетворює типи між доменами strіng і symbol, тому можна використати атоми symbol у доменах strіng і навпаки. Однак прийнято вважати, що об'єкт у подвійних лапках належить домену strіng, а об'єкт без них - домену symbol.

Атоми типу symbol - це імена, що починаються з малої літери й містять тільки букви, цифри й знак підкреслення.

Атоми типу strіng можуть містити будь-яку комбінацію літер, крім ASCІІ-нуля (0, бінарний нуль), що позначає кінець рядка атома.

Тому що strіng/symbol взаємозамінні, їхня відмінність не істотна. Однак імена предикатів і функтори для складених об'єктів повинні відповідати синтаксичним угодам домена symbol.