Е) Алгоритм рівних цін

Методи «сліпого» пошуку.

Пошук рішення задач у просторі станів.

Методи пошуку: «сліпого» і впорядкованого (евристичного) пошуку.

Ознаки методів «сліпого» пошуку:

· простота алгоритмічної реалізації;

· гарантованість одержання розв'язку, якщо існує;

· в процесі пошуку не враховується інформація про близькість поточної й цільової вершин;

· виконується повний перегляд усього простору станів;

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

Варіанти методів «сліпого» пошуку:

a) випадковий пошук;

b) пошук «вглиб і вшир»;

c) алгоритм рівних цін.

а) Випадковий пошук:

· поінформованість обмежується топологією графа простору станів;

· починаючи з початкового стану, випадково вибирають оператор переходу до наступного стану;

· пошук закінчується досягненням цільового стану.

b) Пошук «вглиб і вшир»:

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

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

с) Пошук «вглиб»:

· на початку пошуку список Closed порожній, а Open містить лише початкову вершину;

· щораз зі списку Open вибирається для розкриття перша вершина;

· розкрита вершина переміщується в список Closed, а її дочірні вершини - у початок списку Open;

· на наступному кроці будуть розкриватись дочірні вершини поточної вершини;

· принцип формування списку Open відповідає стеку LIFO (Last In First Out).

d) Пошук «вшир»:

· дочірні вершини, одержувані при розкритті вершини, розміщуються в кінець списку Open. Отже, принцип формування списку Open відповідає черги FIFO (First In First Out);

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

· кожному операторові, що перетворює стан n_i у стан n_j, ставиться у відповідність деяка функція вартості c(n_i,n_j) з позитивними значеннями;

· у ході пошуку шляху враховуються сумарні витрати для досягнення вершини

g(n_j)= g(n_i)+ c(n_i,n_j)

де g(n_i) – вартість шляху з початкової вершини у вершину n_i;

· у ході пошуку вершини в списку Open сортуються в порядку збільшення вартості. Щораз розкривається вершина з найменшою вартістю;

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

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

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

2. Методи евристичного пошуку:

· основна ідея – у використанні для керування процесом пошуку додаткової інформації, що формується на основі емпіричного досвіду дослідника;

· використання евристик скорочує кількість варіантів пошуку, що веде до прискорення рішення задачі;

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

Варіанти методів евристичного пошуку:

a) алгоритм «підйому на гору»;

b) алгоритм глобального врахування відповідності цілі;

c) А-алгоритм.

а) Алгоритм «підйому на гору»:

· цілеспрямований пошук у напрямку найшвидшого убування евристичної оцінної функції;

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

· чим менше значення оцінної функції, тим перспективніший» шлях, на якому перебуває вершина;

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

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

· хоча даний алгоритм прискорює пошук, він не гарантує досягнення цільової вершини;

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

b) Глобальне врахування відповідності цілі:

· відмінність щодо попереднього методу в тому, що на кожному етапі виконується не локальне порівняння всіх вершин-кандидатів у списку Open;

· для цього список відкритих вершин сортується в порядку зростання значень оцінки;

· найкраща вершина для продовження шляху буде на першому місці в списку Open;

· тому даний алгоритм називають також алгоритмом вибору першої найкращої вершини (Best-First);

· застосовується евристична функція, що враховує тільки майбутні витрати;

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

с) А-алгоритм:

використовує оцінку "перспективності" вершини у вигляді деякої оцінної функції:

,

де - відповідає відстані на графі від вузла до початкового стану;

- оцінка відстані від до вузла, що представляє цільовий стан.

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

Дата добавления: 2014-01-07