Прийнятна евристика

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

Алгоритми пошуку

Прийнятна евристика використовується для оцінювання ціни досягнення цільового стану в інформованому алгоритмі пошуку. Щоб бути прийнятною, оціночна ціна видана евристикою повинна бути не більшою ніж дійсна ціна досягнення цільового стану. Алгоритм пошуку використовує евристику для того, щоб знайти оцінювано оптимальний шлях до цільового стану з поточного вузла. Наприклад, алгоритм пошуку A* використовує функцію (де $n$ це поточний вузол):

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

де

$f(n)$ = оціночна функція,

$g(n)$ = ціна від початкового вузла до поточного вузла,

$h(n)$ = оціночна ціна від поточного вузла до цілі.

$h(n)$ обчислюється використовуючи евристичну функцію. У разі використання неприйнятної евристики, A* міг би прогледіти оптимальний розв'язок проблеми пошуку через завищену оцінку у $f(n)$.

Визначення

$n$ — вузол,

$h$ — евристика

$h(n)$ — ціна, визначена $h$ для досягнення цілі з $n,$

$h^{*}(n)$ — справжня ціна досягнення цілі з $n.$

$h(n)$ — прийнятна, якщо

$\forall n,h(n)\leq h^{*}(n)$

Отримання

Прийнятну евристику можна вивести з полегшеної версії задачі або з інформації, отриманні з бази даних шаблонів, яка зберігає точні розв'язки для підзадач задачі, або через використання методів індуктивного навчання.

Приклади

Два різні приклади прийнятних евристик застосовуються для гри п'ятнашки:

• Відстань Геммінга
• Манхеттенська відстань

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

Манхеттенська відстань для пазла визначається як сума відстаней між кожним елементом і його правильною позицією.

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

43	61	30	81
72	123	93	144
153	132	14	54
24	101	111

Індекси вказують на Манхеттенську відстань для кожного елемента. Загальна Манхеттенська відстань пазла становить:

$h(n)=3+1+0+1+2+3+3+4+3+2+4+4+4+1+1=36$

Зауваження

Тоді як всі узгоджені евристики є прийнятними, не всі прийнятні евристики є узгодженими.

Див. також

• Евристична функція
• Алгоритм пошуку