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

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

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

Почнемо розробку даного алгоритму і його варіантів з аналізу описаної нижче простої ідеї.

Щоб знайти шлях вирішення Sol від заданого вузла N до деякого цільового вузла, необхідно реалізувати в програмі наступні операції:

• якщо N - цільовий вузол, то Sol = [N];

• інакше, якщо існує вузол-наступник N1 вузла N, такий, що мається шлях Sol від вузла N1 до цільового вузла, то Sol = [N | Sol].

Це формулювання може бути переведена на мову Prolog наступним чином:

Лістинг 12.1 – Знаходження шляху від заданого вузла

solve(N,[N]) :-

goal ( N).

solve(K, [K | Soll]) :-

S < N , N1,

Solve (N, Soll)

По суті, ця програма являє собою реалізацію стратегії пошуку в глибину. Її називають пошуком в глибину з урахуванням того, в якому порядку розглядаються варіанти в просторі станів. Кожен раз, коли програмі пошуку в глибину надається можливість продовжити пошук шляхом переходу до одного з декількох вузлів, вона завжди віддає перевагу вибрати з них самий глибокий. Найглибшим вузлом є той, який розташований далі всіх, від початкового вузла. На рис. 12.4 показано, в якому порядку відвідуються вузли. Цей порядок відповідає трасуванні виконання програми Prolog при пошуку відповіді на наступне питання: ?- solve (a, Sol).

Рисунок 12.3 – Пошук в глибину

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

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

Рисунок 12.4 –Пошук в ширину

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

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

Для здійснення пошуку в ширину по заданому безлічі можливих шляхів необхідно виконати наступні дії:

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

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

3.6 Загальні аспекти інформованого пошуку

У попередньому розділі було показано, що в умовах відсутності інформації задача пошуку може бути вирішена успішно, але при цьому витрати часу і пам'яті можуть бути зовсім неприйнятними. Якщо задачу про ферзів спробувати вирішити на дошці 100 * 100, то кількість станів буде близько 10 ^ 400. Нехай вас не введе в оману компактна експоненціальна форма подання цього числа. Число атомів у видимій частині всесвіту становить близько 10 ^ 80.

У цьому зв'язку представляється доцільним поліпшити сліпий пошук в тих випадках, коли є яка-небудь додаткова інформація. Зрозуміло, ми не розглядаємо випадок, коли точно відомий шлях до мети. В останньому випадку задача вже вирішена. Йдеться про інформацію, яка спостерігається, але не дає прямої відповіді, як рухатися до мети.

Розглянемо наступну задачу. Нехай нам потрібно добратися з Таллінна до Москви повітряним транспортом. Відстані між містами і повітряні траси показані на ріс.12.6.

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

Якби ми не мали ніяких даних про відстані, то мав би місце сліпий (непоінформовані) пошук. Якщо ми знаємо тільки відстань від поточної точки до сусідніх, то ми в змозі виконати пошук за критерієм вартості. Найближчий пункт від Таллінна - Гельсінкі (100км), потім - Петербург (295), Рига (476), Твер (716), Москва (161). Загальна протяжність шляху - 1748 км, і вона суттєво відрізняється від оптимальної - 957 км. Припустимо, що нам відомо відстань від кожного з міст до Москви по прямій.

Ця інформація може використовуватися для вибору наступного пункту маршруту. Так, доступними пунктами з Таллінна є Хельсінкі (897км), С.Петербург (634) і Рига (839). Прагнучі на кожному кроці максимально наблизитися до мети, ми виберемо на першому кроці С.Петербург, на другому кроці - Твер, потім - Москву. Загальна протяжність шляху дорівнює оптимальної.

Даний вид пошуку називається жадібним пошуком по першій найкращій відповідності. Кожен наступний вузол для розгортання вибирається на основі функції оцінки f (n). У зв'язку з тим, що ми не володіємо точними оцінками, використовуються евристичні функції h (n) або евристики. У розглянутому прикладі евристична функція - це відстань до мети по прямій.

Рисунок 12.6 – Відстанні до пункта по прямій

Ця евристика не є свідомо оптимальної. Якщо, наприклад, між Твер'ю і Москвою літаки не літають, то оптимальний маршрут Таллінн - Рига - Москва буде істотно відрізнятися від запропонованого алгоритму жадібного пошуку по першому найкращому збігу: Таллінн - С.Петербург - Твер - Рига - Москва.

Рисунок 12.7 – Жадібний пошук по першій найкращій відповідності

Жадібний пошук по першій найкращій відповідності нагадує пошук в глибину і страждає від тих же недоліків. На останній схемі без запобігання повторюваних станів можливо нескінченне блукання по відрізку С.Петербург - Твер - С.Петербург і т.д. В найгіршому варіанті складність методу становить bm, де b - коефіцієнт розгалуження, m - максимальна глибина простору пошуку. Однак, гарна евристична функція дозволяє істотно знизити таку складність.

3.7 Аналіз загальних методів пошуку.

У даному розділі проводяться аналіз і порівняння основних методів пошуку. Проаналізуємо, які вимоги пред'являються їм до ресурсів часу і простору. Розглянуті програми пошуку в ширину виробляють один за іншим шляхи рішень, впорядковані по довжині, причому спочатку формуються найкоротші рішення. Це важливо, якщо необхідно забезпечити одержання оптимальних рішень (з точки зору довжини). Стратегія пошуку в ширину гарантує першочергову вироблення найкоротших рішень. Це твердження, безумовно, не відноситься до стратегії пошуку в глибину. Але під час пошуку в глибину з ітеративним поглибленням такий пошук виконується з поступово збільшуються межами глибини, і тому спостерігається тенденція до того, що в першу чергу виявляються найкоротші рішення. Таким чином, при ітеративному поглибленні відбувається свого роду моделювання пошуку в ширину.

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

Типовою проблемою, пов'язаною з пошуком, є комбінаторна складність. При наявності нетривіальних проблемних областей кількість варіантів, які розглядатимуться, стає настільки значною, що найбільше значення набуває суттєве збільшення витрат ресурсів на дослідження даних варіантів. Можна легко проаналізувати причини того, чому це відбувається. Для спрощення такого аналізу припустимо, що простір станів являє собою дерево з однаковими гілками. Це означає, що кожен вузол в дереві, за винятком листя, має точно b наступників. Припустимо, що найкоротший шлях вирішення має довжину d, і в дереві на глибині d чи меншою відсутнє листя. Кількість альтернативних шляхів довжини d від початкового вузла одно bd. При пошуку в ширину кількість розглянутих шляхів пропорційне b^d. Це позначається як O (b ^ d). Отже, кількість можливих шляхів дуже швидко зростає при збільшенні їх довжини, що призводить до так званого комбінаторному вибуху.

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

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

<== попередня сторінка	\|	наступна сторінка ==>
Визначення методу пошуку.	\|	Будова атмосфери

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

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