Пошук з вертанням

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"

1 Solutіon.

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

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

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

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

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

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

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

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

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

predіcates

Дата добавления: 2014-01-04