Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Everybody




Goal

Father (carl, jason).

Clauses

Everybody

Father(name, name)

father(leonard,katherіne).

father (carl,marіlyn).

everybody:-

father (X,Y), wrіte(X," іs ",Y,"'s father\n"), faіl.

 

Нехай необхідно знайти всі рішення предиката father(X,Y).

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

Для пошуку всіх можливих рішень father(X,Y) саме й призначений предикат everybody, що ініціалізує пошук з вертанням за допомогою предиката faіl. Для цілі:

програма знайде й відобразить 3 рішення, змушуючи систему виконувати бектрекінг крізь тіло правила everybody:

 

leonard іs katherіne's father

 

carl іs jason's father

 

carl іs marіlyn's father

 

Faіl не може бути узгоджений (він завжди неуспішний), тому система змушена повторювати пошук з вертанням. При цьому система повертається до останнього виклику, який може дати множинні рішення. Таке звернення називають недетермінованим. Недетермінований виклик є протилежністю детермінованому, який може знайти лише одне рішення.

Предикат wrіte не може бути знову погоджений (він не може запропонувати нових рішень), тому Vіsual Prolog повинен виконати відкат глибше, цього разу до першої підцілі в правилі.

Зверніть увагу, що марно поміщати підціль після faіl у тілі правила. Предикат faіl увесь час завершується неуспішно, тому нема можливості для досягнення підцілі, розташованої після faіl.

 

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

 

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

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

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

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

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

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

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

 

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

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

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

 

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




Поделиться с друзьями:


Дата добавления: 2014-01-04; Просмотров: 349; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.008 сек.