ІНФОРМОВАНЕ ПОШУК

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

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

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

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

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

Приклад повітряних трас до задачі пошуку

Мал. 2.4. Приклад повітряних трас до задачі пошуку

Відстані до пункту призначення по прямій

Мал. 2.5. Відстані до пункту призначення по прямій

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

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

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

Мал. 2.6. Жадібний пошук по першому найкращому відповідності

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

У найгіршому варіанті складність методу складає ред т , де b - коефіцієнт розгалуження, т - максимальна глибина простору пошуку. Однак гарна евристична функція дозволяє істотно знизити таку складність.

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

де g (n) - вартість досягнення п-го вузла; h (n) - евристична функція вартості досягнення мети з п -го вузла.

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

Алгоритм А *. Перший крок пошуку

Мал. 2.7. Алгоритм А *. Перший крок пошуку

Отже, для розгортання вузла буде обраний Санкт-Петербург як має мінімальне значення функції оцінки.

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

Наступним пунктом маршруту буде обрана Тверь (рис. 2.9).

З Твері є шлях тільки в Ригу, але функція оцінки набагато вище, ніж при русі по маршруту «Таллінн - Рига». Отже, ця гілка ( «Таллінн - Санкт-Петербург - Твер - Рига -...») свідомо не дає оптимального рішення, і для розгортання потрібно замість Санкт-Петербурга обрати інше місто. Наступний вузол після Санкт-Петербурга по зростанню функції оцінки - Гельсінкі (рис. 2.10).

Алгоритм А *. Другий крок пошуку

Мал. 2.8. Алгоритм А *. Другий крок пошуку

Алгоритм А *. Третій крок пошуку

Мал. 2.9. Алгоритм А *. Третій крок пошуку

Тут також функції оцінки для Риги і Санкт-Петербурга вище, ніж в раніше розгорнутих вузлах. Отже, необхідно розгорнути вузол «Рига». З Риги ми прямо потрапляємо в Москву (рис. 2.11).

Алгоритм А *. Четвертий крок пошуку

Мал. 2.10. Алгоритм А *. Четвертий крок пошуку

Алгоритм А *. П'ятий і шостий кроки пошуку

Мал. 2.11. Алгоритм А *. П'ятий і шостий кроки пошуку

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

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

Розглянемо приклад ще однієї логічної задачі. У нас вона відома як гра «15» ( «П'ятнашки»). Ми ж розглянемо спрощений варіант на дев'яти клітинах з вісьмома фішками (гра «8»). Початковий і кінцевий стани можуть бути, наприклад, такими (рис. 2.12).

Фішки можна рухати по горизонталі і вертикалі на вільну клітину. Середня складність вирішення становить 22 ходу. Коефіцієнт розгалуження - 3 (4, якщо вільна клітина в центрі;

Гра «8»

Мал. 2.12. Гра «8»:

а - початковий стан; б - кінцевий стан

  • 2 - якщо в кутку). Число станів приблизно З 22 або 3,1 • 10 10 . Усуваючи повторювані стану, можна скоротити їх кількість приблизно в 170 000 разів. Цей стан вже піддається контролю, але відповідну кількість станів для гри в 15 дорівнює 10 13 , тому потрібно знайти хорошу евристичну функцію. В якості таких можуть використовуватися такі функції:
    • h - кількість фішок, що стоять не на своєму місці. На рис. 2.12 а всі фішки стоять не на своєму місці, тобто h x - 8. Дана евристична функція є допустимою, оскільки кожну фішку, що стоїть не на своєму місці, потрібно перемістити щонайменше один раз;
    • h 2 - сума відстаней всіх фішок від їх цільових позицій. Функція також є допустимою, оскільки переміщення будь-якої фішки на одну позицію змінює функцію на одиницю. Ця функція більш точно відображає ступінь розбіжності поточної і цільової позицій. Відстань вимірюється в горизонтальних і вертикальних переміщеннях. На рис. 2.12 a h 2 = 18.

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

Евристики в завданню про восьми ферзів

Мал. 2.13. Евристики в завданню про восьми ферзів

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

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

Локальний максимум і плато

Мал. 2.14. Локальний максимум і плато:

1 - локальний максимум, подолати який локальний пошук не в змозі; 2 - плато, тобто область, в якій евристика не змінюється від ходу до ходу

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

  • 1. Вибираються позиції з кращими значеннями евристик (відбір).
  • 2. Дошка «розрізається» по вертикалі або по горизонталі, і частини дошки від різних позицій з'єднуються разом (схрещування).
  • 3. У отримані нові комбінації вносяться випадкові зміни (мутації).
  • 4. Якщо отримана позиція гірше попередніх, вона відкидається, якщо краще - запам'ятовується (відбір).
  • 5. З наявних кращих позицій все повторюється з і. 2.

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

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

 
Переглянути оригінал
< Попер   ЗМІСТ   ОРИГІНАЛ   Наст >