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

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

Шлях, по якому функція best_first_search знаходить цільовий стан, показаний на малюнку жирними стрілками. Припустимо, що P — цільовий стан (див. мал. 4). Оскільки P — ціль, стани на шляху до P мають низькі евристичні значення. Евристика схильна до помилок: стан О має нижче евристичне значення, ніж цільове, і тому було досліджено раніше. На відміну від пошуку екстремуму, який не зберігає пріоритетну чергу для відбору "наступних" станів, даний алгоритм відновлюється після помилки і знаходить цільовий стан.

1.         open = [А-5]; closed = [].

2.         Обчислюваний А-5;ореп=[В-4, С-4, D-6];closed= [A-5].

3.         Обчислюваний Б-4; ореn = [С-4,E-5, F-5, D-6];closed= [В-4, А-5].

4.         Обчислюваний С-4; open = [Н-3, G-4, E-5, F-5, D-6]; closed= [С-4, В-4, А-5].

5.         Обчислюваний Н-3; open = [О-2, Р-3, G-4, E-5, F-5, D-6]; closed = [Н-3, С-4, В-4, А-5]

6.         Обчислюваний О-2; open = [Р-3, G-4, E-5, F-5, D-6]; closed = [О-2, Н-3, С-4, B-4, A-5].

7.         Обчислюваний Р-3; рішення знайдено 

Мал. 5. Евристичний пошук в гіпотетичному просторі станів. Ті, що складаються із списків open і closed виділені 

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

"Жадібний" алгоритм пошуку завжди вибирає найбільш перспективне полягання в open для продовження. Проте, оскільки при виборі стану використовується евристика, яка може виявитися помилковою, алгоритм не відмовляється від решти станів, і зберігає їх в списку open. В даному випадку евристика забезпечує пошук вниз; цей шлях виявляється помилковим, але алгоритм у результаті повертається до деякого "кращого" полягання, що раніше згенерувало, в open і потім продовжує пошук в іншій частині простору. У прикладі на мал. 4 після знаходження нащадків полягання В здавалося, що вони мають погані евристичні оцінки, і тому пошук змістився до стану С. При цьому нащадки полягання В були збережені в open на випадок, якщо алгоритму необхідно буде повернутися до них пізніше. У функції best_first_search, як і в алгоритмах з розділу 3, список open дозволяє повертатися назад по помилковому шляху.

 

2. Функції евристичної оцінки станів

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

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

1 2 3 4 5 6 7