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

правила ("rules of thumb"), які використовує експерт, щоб ефективно вирішити ту або іншу проблему, в значній мірі евристичні за природою. Такі евристики були створені і формалізовані розробниками експертних систем.

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

Розглянемо гру в "хрестики-нулі". Вичерпний пошук (повний перебір варіантів) в цій грі скрутний, але можливий. На кожний з дев'яти перших ходів існує вісім можливих відповідей. На які, у свою чергу, можна відповісти сім'ю різними варіантами і т. д. Простій аналіз дозволяє знайти загальне число можливих станів, які слід розглянути у вичерпному пошуку, — 9х8х7х. . . , або 9!.  

Враховуючи симетрію задачі, можна зменшити простір пошуку. Проблема безлічі можливих конфігурацій насправді зводиться до пошуку можливих симетричних конфігурацій ігрової дошки. Таким чином, існує не дев'ять, а тільки три можливі перші ходи — в кут, на верхню центральну клітку і в центр грат. Редукції на другому рівні і далі скорочують розмірність простору до 12x7!, як показано на мал. 1. Симетрія ігрового простору, подібна розглянутою вище, може бути описана як математичний інваріант, і якщо вона існує в задачі, то може бути успішно використана для значного зменшення простору станів. Проста евристика може звести нанівець необхідність пошуку: ми можемо робити такі ходи на дошці, в яких хрестики мають найбільшу кількість виграшних ліній. (Перші три стани гри "хрестики-нулі" прораховані саме таким чином, мал. 2

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

Опонент після першого ходу може вибрати один з двох можливих у відповідь ходів (як показано на мал. 3). Що б не вибрав опонент, до результуючого стану гри може бути застосована евристика. Евристика використання "найбільшого числа виграшних ліній" вибирає серед можливих ходів якнайкращий. При продовженні пошуку кожен новий хід усуває необхідність обробки нащадків відкинутих вузлів, таким чином, повний перебір не потрібний. На мал. 3 продемонстрований редукційний пошук на перших трьох кроках гри. Кожен стан гри помічений відповідним йому евристичним значенням.  

Хоча точна кількість можливих полягань в грі обчислити важко, верхня межа цієї кількості станів може бути обчислена, якщо допустити, що максимальне число ходів в грі — 9, і кожен хід має по 8 нащадків. Насправді число станів буде значно менше, оскільки дошка заповнюється, і з кожним ходом число можливих відповідей зменшується. Більш того, опонент робить половину всіх ходів. Не дивлячись на це, груба верхня межа — 9x8, або 72 стани, що на 4 порядки менше величини 9!.

Алгоритм евристичного пошуку

1. "Жадібний" алгоритм пошуку

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

1 2 3 4 5 6 7