Узгоджена евристика

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

Формально, для кожного вузла N і кожного його можливого наступника P утвореного будь-якою дією a, оцінена ціна досягнення цілі з N є не більшою ніж ціна кроку діставання до P плюс оцінена ціна досягнення цілі з P. Інакше кажучи:

$h(N)\leq c(N,P)+h(P)$ і

$h(G)=0.\,$

де

• h — узгоджена увристична функція
• N — будь-який вузол у графі
• P — будь-який спадкоємець N
• G — будь-який цільовий вузол
• c(N,P) — ціна діставання від P до N

Узгоджена евристика також прийнятна, тобто вона ніколи не переоцінює ціну досягнення цілі (зворотнє не завжди правильно!). Це доведено за допомогою індукції по $m,$ довжині накращого шляху від вузла до цілі. За припущенням, $h(N_{m})\leq h^{*}(N_{m}),$ де $h^{*}(n)$ позначає ціну найкоротшого шляху з n до цілі. Отже,

$h(N_{m+1})\leq c(N_{m+1},N_{m})+h(N_{m})\leq c(N_{m+1},N_{m})+h^{*}(N_{m})=h^{*}(N_{m+1})$,

роблячи її прийнятною. ($N_{m+1}$ є будь-яким вузлом чий найкращий шлях до цілі має довжину m+1, пролягає через деякий безпосередньо дочірній вузол $N_{m}$ чий найкращий шлях до цілі має довжину m.)

Однак, прийнятну евристику $h,$ майже завжди можна перетворити в узгоджену евристику, $h'$, через таке підлаштування:

$h'(P)\gets \max(h(P),h(N)-c(N,P))$

(Відоме як рівняння pathmax)

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

Наслідки монотонності

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

Узгоджені евристики називають монотонними, тому що оцінена фінальна ціна для часткового розв'язку, $f(N_{j})=g(N_{j})+h(N_{j})$ монотонно не спадає уздовж найкращого шляху до цілі, де $g(N_{j})=\sum _{i=2}^{j}c(N_{i-1},N_{i})$ є ціною оптимального шляху від початкового вузла $N_{1}$ до $N_{j}$. Для евристики необхідно і достатньо коритися нерівності трикутника, щоб бути узгодженою.

В алгоритммі пошуку A*, використання узгодженої евристики означає, що щойно вузол розширили, ціна з якою його досягли є найменшою можливою, якщо виконуються ті самі припущення, що й для алгоритму Дейкстри знаходження найкоротшого шляху (відсутність негативних ребер). Насправді, якщо граф пошуку наділений ціновою функцією $c'(N,P)=c(N,P)+h(P)-h(N)$ із узгодженою $h$, тоді A* тотожний до пошуку за першим найкращим збігом на цьому графі із використанням алгоритму Дейкстри. У рідкісному випадку, коли прийнятна евритсика неузгоджена, вузол потребуватиме повторюваного розширення кожного разу коли нова найкраща (покищо) ціна отримана для неї.

Див. також

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