Визначення методу пошуку.

Методи пошуку в системі пролог Prolog реалізуються в форму відповіді на запитання. Питання до системи Prolog завжди являє собою послідовність з однієї або декількох цілей. Щоб відповісти на питання, Prolog намагається досягнути всіх цілей. Але що в даному контексті означає вираз "досягти мети"?. Досягти мети - це означає продемонструвати, що мета є істинною, за умови, що відносини в програмі є істинними. Іншими словами, вираз досягти мети означає: продемонструвати, що мета логічно випливає з фактів і правил, заданих в програмі. Якщо питання містить змінні, система Prolog повинна також знайти конкретні об'єкти (замість змінних), при використанні яких цілі досягаються. Для користувача відображаються варіанти конкретизації змінних, отримані при підстановці конкретних об'єктів замість змінних. Якщо система Prolog не може продемонструвати для якогось варіанту конкретизації змінних, що цілі логічно випливають з програми, то ви-дає в якості відповіді на запитання слово "по".

Таким чином, з точки зору математики програму Prolog слід інтерпретувати так: Prolog приймає факти і правила як набір аксіом, а питання користувача - як теорему, що вимагає докази; потім Prolog намагається довести теорему, тобто продемонструвати, що вона є логічним наслідком з аксіом.

Проілюструємо цей підхід до опису роботи системи Prolog на класичному прикладі. Припустимо, що задані наведені нижче аксіоми.

Всі люди здатні помилятися. Сократ - людина.

З цих двох аксіом логічно випливає теорема: Сократ здатний помилятися.

Перша аксіома, наведена вище, може бути переформульована наступним чином:

Для всіх X, якщо У. - людина, то х здатний збивати.

Відповідним чином цей приклад може бути переведений на мову Prolog, як показано нижче на рисунку 12.1.

Рисунок 12.1 – Приклад до задачі пошуку

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

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

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

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

3.2 Загальні принципи пошуку у мові логічного програмування

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

Цю задачу можна розглядати як задачу вивчення можливих варіантів. У первісній проблемної ситуації є тільки один варіант: поставити кубик С на стіл. А після того як кубик В поставлений на стіл, з'являються три наступних варіанти:

• поставити А на стіл;

• поставити А на С;

• поставити С на А.

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

Рисунок 12.2 – Приклад до задачі пошуку із кубиками

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

1. Проблемні ситуації.

2. Допустимі кроки, або дії, які перетворять одні проблемні ситуації в інші.

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

• Простір станів.

• Початковий вузол.

• Цільовий стан (стан, який має бути досягнуто); цільовими вузлами називаються такі вузли, які відповідають цьому стану.

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

3.3 Неінформований пошук

Неінформований (сліпий) пошук - пошук, при якому відсутня інформація про те, чи в правильному напрямі він ведеться. Такий пошук являє собою комбінаторну задачу, розмірність якої визначається коефіцієнтом розгалуження (b) і глибиною (d) за формулою bd +1. У гіршому випадку при пошуку потрібно розгорнути bd +1 вузлів (сам цільової вузол не розгортається), а в середньому – (bd +1) / 2 вузлів.

Розглянемо, які існують варіанти і методи поліпшення неінформованого пошуку.

Пошук в ширину. Спочатку розгортається кореневий вузол, потім всі її наступники, потім - наступники наступників і т.д. На відміну від пошуку в глибину цей метод швидко виявляє рішення, яке знаходиться неглибоко, і не впадає в нескінченні поглиблення. Істотним недоліком даного методу є необхідність запам'ятовувати всі вузли-предки, кількість яких також визначається формулами комбінаторики.

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

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

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

Двонаправлений пошук. Цей різновид пошуку використовується в тих випадках, коли кінцевий стан нам відомо, а треба знайти шлях до мети. Один пошук запускається з початкового вузла, інший - з кінцевого. Завдання завершується, коли обидва пошуку знаходять загальний вузол. Нехай глибина пошуку d = 6, а коефіцієнт розгалуження b = 2. Пошук в одному напрямку зажадає 2^6 = 64 кроку, а двонаправленого пошуку 26/2 = 13 кроків. Недоліком даного методу є необхідність чисельного визнаяення вузла - попередника, що буває не завжди можливим.

Порівняльні характеристики методів неінформованого пошуку зведені в таблицю 12.1 .Тут використовуються такі позначення:

b - коефіцієнт розгалуження; d - глибина самого поверхневого рішення; m - максимальна глибина дерева; e - межа глибини; С - вартість рішення; n - середня вартість одного кроку.

Таблиця 12.1 – Характеристики методів неінформованого пошуку

Метод	Повнота	Часова складність	Затрати пам'яті	Оптимальність
Пошук в ширину	Так	b^(d+1)	b^(d+1)	Так
Пошук по критерію вартості	Так	b^(1+C/n)	b^(1+C/n)	Так
Пошук в глибину	Ні	b^m	bm	Ні
Пошук з обмеженням глибини	Ні	b^e	be	Ні
Пошук в глибину з ітеративним поглибленням	Ні	b^d	bd	Ні
Двонаправлений пошук	Так	b^(d/2)	b^(d/2)	Так

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Предмет і методи метеорологічних досліджень	\|	Пошук в ширину

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.