Эвристический поиск

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

Основна проблема стратегій пошуку екстремуму — це їх тенденція зупинятися в локальному максимумі. Іншими словами, як тільки вони досягають стану, що має кращу оцінку, чим його нащадки, алгоритм завершується. Якщо цей стан є не рішенням задачі, а тільки локальним максимумом, то такий алгоритм неприйнятний для даної задачі. Це означає, що рішення може бути оптимальним на обмеженій множині, але із-за форми всього простору, можливо, ніколи не буде вибрано якнайкраще рішення. Приклад такого локального екстремуму з'являється в грі в "квачі". Часто для того, щоб пересунути фішку в потрібну позицію, необхідно зрушити фішку, що знаходиться в якнайкращій позиції. Без цього неможливо вирішити головоломку, але в той же час на даному етапі це погіршує стан системи. Річ у тому, що "кращий" не означає "ідеальний". Методи пошуку без механізмів повернення або інших прийомів відновлення не можуть відрізнити локальний максимум від глобального. Існують методи наближеного рішення цієї проблеми, наприклад, випадкове збурення оцінки. Проте гарантовано вирішувати задачі з використанням техніки пошуку екстремуму не можна.

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

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

Подібно до алгоритмів пошуку в глибину і алгоритмів пошуку завширшки "жадібний" алгоритм пошуку використовує списки збережених станів: список open відстежує поточний стан пошуку, а в closed записуються вже перевірені стани. На кожному кроці алгоритм записує в список open стан з урахуванням деякої евристичної оцінки його "близькості до цілі". Таким чином, на кожній ітерації розглядаються ті, що найбільш перспективні складаються із списку open. Псевдокод для функції, що реалізовує "жадібний" алгоритм пошуку приведений нижче.  

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

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

Потім функція best_first_search обчислює евристичну оцінку полягань в списку open і сортує список відповідно до цих евристичним значенням. При цьому "кращі" стани ставляться в початок списку. Відмітимо, що із-за евристичної природи оцінювання наступний стан повинен перевірятися на будь-якому рівні простору станів. Відсортований список open часто називають пріоритетною чергою (priority queue).  

На мал. 4

1 2 3 4 5 6 7

Похожие работы