Евристичний пошук

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

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

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

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

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

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

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

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

Кращими властивостями володіє інша форма евристичного пошуку, що одержала найменування спочатку найкращий (best-first search). Так само, як і у варіанті сходження на гору, у нашому розпорядженні є оцінна функція, за допомогою якої можна порівнювати стану в просторі станів. Основна ж відмінність нового методу від раніше розглянутого полягає в тому, що порівнюються не тільки ті стани, у які можливий перехід з поточного, але і всі, до яких "можна дістати".

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

2.2. Алгоритм A*

Існує добре відомий алгоритм пошуку, який відноситься до групи перший кращий, що одержав назву А * (вимовляється "А з зірочкою"). Основна ідея алгоритму складається у використанні для кожного вузла на графі простору станів оцінної функції виду:

f(n)=g(n)+(n)

Тут g (п) відповідає відстані на графі від вузла n до початкового стану, a h(n) — оцінка відстані від n до вузла, який представляє кінцевий (цільовий) стан. Чим менше значення оцінної функції f(n), тим "краще", тобто вузол п лежить на більш короткому шляху від вихідного стану до цільового. Ідея алгоритму полягає в тому, щоб за допомогою f(n) відшукати найкоротший шлях на графі від вихідного стану до цільового

Звідси випливає що якщо h(n) — нижня оцінка дійсної відстані до цільового стану, тобто якщо h(n) ніколи не дає завищеної оцінки відстані то алгоритм А* завжди відшукає оптимальний шлях до мети за допомогою оцінної функції f(n). Алгоритм, який володіє такою властивістю, називається розв'язним (більш докладне обговорення цього питання читач знайде в спеціальній літературі, зокрема в роботах Нільсона [Nilsson, 1980, Chapter 2] і Перла [Pearl, 1984, Chapter2]).

Позначення:

s-вузол початкового стану,

g-вузол цільового стану,

OPEN — список, що містить обрані, але неопрацьовані вузли;

CLOSED—список, що містить оброблені вузли;

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