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

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

Таким чином, оцінююча функція f складається з двох компонентів:

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

де g(n) — фактична довжина шляху від довільного стану n до початкового, а h(n) — евристична оцінка відстані від стану n до цілі.

Наприклад, в 8-головоломке значенням h(n) можна вважати число фішок, що знаходяться не на своїх місцях. Якщо розглянути стани, зображені на мал. 6, то значення f для кожного з них будуть рівні 6, 4 і 6 відповідно (мал. 9).

На мал. 10 показано значення f для кожного стану графа "жадібного" алгоритму пошуку для 8-головоломки. Поряд з кожним станом вказана його евристична вага f(n) = g(n)+ h(n). Номер у верхній частині стану указує порядок, в якому цей стан був узятий із списку open. Деякі стани (h, g, b, d, n, k і i) не пронумеровані, оскільки вони залишалися в списку open на момент завершення алгоритму. 

Мал. 9. Евристика f для полягань в грі "8-головоломка"

Зміст списків open і closed, які генерують цей граф, приведений нижче.

1. open = [а4]; closed = [].

2. open = [с4, b6, d6]; closed = [а4].

3. open = [е5, f5, b6, d6, g6]; closed = [а4, с4].

4. open = [f5, hб, b6, d6, g6, 17]; closed = [а4, с4, е5].

5. open = [j5, h6, b6, d6, g6, k7, 17]; closed = [а4, с4, е5, f5].

6. open = [l5, h6, b6, d6, g6, k7, 17]; closed = [а4, с4, е5, f5, j5].

7. open = [m5, h6, b6, d6, g6, n7, k7, 17]; closed = [а4, с4, е5, f5, j5, l5].

8. Знайдено рішення т = ціль!.

На 3 кроці стану е і f мають евристичне значення, рівне 5. Стан е був перевірений першим, його нащадками є h і i. Хоча h є нащадком е, для нього число фішок, розташованих не на своїх місцях, відповідає стану f; при цьому даний стан знаходиться на один рівень нижче в просторі станів. Міра глибини, g(n), примушує алгоритм вибирати f як оцінки на кроці 4. Тому алгоритм повертається до стану f, що знаходиться на один рівень вище, і потім продовжує рухатися до мети по іншій вітці. Граф простору перебувань на цій стадії пошуку показаний на мал. 11. Тут закрашені області, в яких знаходяться ті, що складаються із списків open і closed. Звернете увагу на приспособленчеську природу пошуку до першого якнайкращого збігу.

Насправді компонент g(n) функції оцінки додає нашому пошуку властивості пошуку завширшки. Він запобігає можливості помилки із-за помилкової оцінки: якщо евристика безперервно повертає "гарні" оцінки для перебувань на шляху, не ведучому до цілі, то значення g буде рости і домінувати над h, повертаючи

1 2 3 4 5 6 7