Повна версія

Головна arrow Інформатика arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

МЕТОДИ СПУСКУ ПО ДЕРЕВУ РІШЕНЬ

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

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

Розмірність навіть не дуже складних комбінаторних задач вражає уяву. Наприклад, для оцінки алгоритмів пошуку часто використовують згадану вище завдання про восьми ферзів, які треба так розставити на шахівниці, щоб жоден з них не бив іншого. Простір станів для такого завдання становить приблизно 3 • 10 14 вузлів. При розгортанні 10000 вузлів в секунду на обхід всього дерева потрібно приблизно 1000 років! У той же час людина в стані вирішити це завдання за лічені хвилини. Розглянемо, які існують варіанти і методи поліпшення неінформованого пошуку.

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

Пошук в ширину. Спочатку розгортається кореневої вузол, потім все його наступники, потім - наступники наступників і т.д. На відміну від пошуку в глибину цей метод швидко виявляє рішення, яке знаходиться неглибоко, і не впадає в нескінченні поглиблення. Істотним недоліком даного методу є необхідність запам'ятовувати всі вузли-предки, кількість яких також визначається формулами комбінаторики. Для згаданої задачі про восьми ферзів при витраті пам'яті 1000 байт на вершину обсяг необхідної пам'яті вимірюється сотнями петабайт (1 терабайт = = 1024 гігабайти, 1 петабайт = 1024 терабайта). Очевидно, що цей недолік істотно обмежує можливість застосування методу.

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

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

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

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

d = 6, а коефіцієнт розгалуження b = 2. Пошук в одному напрямку

6

зажадає 2 6 = 64 кроку, а двонаправлений пошук - 22 = 8 кроків. Недоліком даного методу є необхідність обчислюваності вузла-попередника, що буває не завжди можливим.

Запобігання формуванню повторюваних станів. У прикладі завдання про фермера ми вже використовували цю модифікацію методу пошуку, правда, там запам'ятовувалися лише вузли поточного шляху. У разі помилкового шляху в цій програмі виконується відкат, і Prolog «забуває» вже пройдені вузли. Правильна модифікація алгоритму пошуку повинна включати в список все пройдені вершини. Слід, однак, зауважити, що в деяких завданнях повторювані стану є неминучими. Однією з різновидів методу запобігання повторюваних станів є використання властивостей симетричності. Наприклад, складність завдання про восьми ферзів або гра в хрестики-нулики скорочується в чотири рази, оскільки ігрове поле квадратне.

Порівняльні характеристики методів неінформованого пошуку зведені в табл. 2.1.

Таблиця 2.1

Характеристики методів неінформованого пошуку

метод

повнота

тимчасова

складність

витрати

пам'яті

оптимальність

Пошук в ширину

Так

? + '

Так

Пошук але критерієм вартості

Так

b 1 + С / п

b 1 + С / п

Так

Пошук в глибину

Пет

Комерсант т

немає

Пошук з обмеженням глибини

немає

6 е

be

немає

Пошук з ітеративним поглибленням

Так

?

bd

Так

двохнаправлений пошук

Так

/ У '/ 2

Ь

Так

Примітка. У таблиці використовуються наступні позначення: b - коефіцієнт розгалуження; d - глибина самого поверхневого рішення; т - максимальна глибина дерева; е - межа глибини; З - вартість рішення; п - середня вартість одного кроку.

Таким чином, неінформірованнимі пошук є дуже простим, за що отримав також назву «наївний пошук», оскільки здійснює простий перебір варіантів, і це робить його надзвичайно неефективним, непридатним для будь-якого завдання реального світу. У всіх різновидах неінформованого пошуку має місце (в різних варіаціях) експоненціальна складність пошуку И.

 
<<   ЗМІСТ   >>