Euristică consecventă - Consistent heuristic

În studiul problemelor de găsire a căilor în inteligența artificială , se spune că o funcție euristică este consecventă sau monotonă , dacă estimarea sa este întotdeauna mai mică sau egală cu distanța estimată de la orice vârf vecin până la obiectiv, plus costul de atingere acel vecin.

Formal, pentru fiecare nod N și fiecare succesor P al N , costul estimat al atingerii obiectivului de la N nu este mai mare decât costul pas de a ajunge la P plus costul estimat al atingerii obiectivului de la P . Acesta este:

${\ displaystyle h (N) \ leq c (N, P) + h (P)}$ și

${\ displaystyle h (G) = 0. \,}$

Unde

• h este funcția euristică consistentă
• N este orice nod din grafic
• P este orice descendent al lui N
• G este orice nod obiectiv
• c (N, P) este costul atingerii nodului P de la N

În mod informal, fiecare nod i va da o estimare care, luând în considerare costul pentru a ajunge la următorul nod, este întotdeauna mai mică decât estimarea la nodul i + 1 .

O euristică consecventă este, de asemenea , admisibilă , adică nu supraestimează niciodată costul atingerii obiectivului ( invers , totuși, nu este întotdeauna adevărat). Acest lucru este dovedit prin inducție .

Fie costul estimat pentru nodul obiectivului. Aceasta implică faptul că condiția de bază este trivial adevărată ca 0 ≤ 0. Deoarece euristica este consecventă ,. Termenii dați sunt egali cu costul adevărat , deci orice euristică consistentă este, de asemenea, admisibilă, deoarece este limitată de costul adevărat. ${\ displaystyle h (N_ {0}) = 0}$${\ displaystyle h (N_ {i + 1}) \ leq c (N_ {i + 1}, N_ {i}) + h (N_ {i}) \ leq c (N_ {i + 1}, N_ {i }) + c (N_ {i}, N_ {i-1}) + h (N_ {i-1}) \ leq c (N_ {i + 1}, N_ {i}) + c (N_ {i} , N_ {i-1}) + ... + c (N_ {1}, N_ {0}) + h (N_ {0})}$${\ displaystyle \ sum _ {i = 1} ^ {n} c (N_ {i}, N_ {i-1})}$

În mod clar, inversul nu este adevărat, deoarece putem construi întotdeauna o euristică care este întotdeauna sub costul adevărat, dar este totuși inconsecventă, de exemplu, prin creșterea estimării euristice de la cel mai îndepărtat nod pe măsură ce ne apropiem și, atunci când estimarea devine cel mult cost adevărat , facem . ${\ displaystyle h (N_ {i})}$${\ displaystyle h ^ {*} (N_ {i})}$${\ displaystyle h (N_ {i-1}) = h (N_ {i}) - c (N_ {i}, N_ {i-1})}$

Consecințele monotoniei

Compararea unei funcții de evaluare euristică admisibilă, dar inconsistentă și consistentă.

Euristicile consistente sunt numite monotone, deoarece costul final estimat al unei soluții parțiale este monotonic nedescrescând de-a lungul celei mai bune căi către obiectiv, unde este costul celei mai bune căi de la nodul de pornire la . Este necesar și suficient ca un euristic să asculte inegalitatea triunghiului pentru a fi consecvent. ${\ displaystyle f (N_ {j}) = g (N_ {j}) + h (N_ {j})}$${\ displaystyle g (N_ {j}) = \ sum _ {i = 2} ^ {j} c (N_ {i-1}, N_ {i})}$${\ displaystyle N_ {1}}$${\ displaystyle N_ {j}}$

În algoritmul de căutare A * , folosirea unei euristici consistente înseamnă că, odată ce un nod este extins, costul cu care a fost atins este cel mai mic posibil, în aceleași condiții pe care algoritmul lui Dijkstra le cere pentru rezolvarea celei mai scurte probleme de cale (fără margini de cost negative ). De fapt, dacă graficului de căutare i se dă un cost pentru o consecvență , atunci A * este echivalentul celei mai bune căutări pe acel grafic folosind algoritmul lui Dijkstra. În cazul neobișnuit în care o euristică admisibilă nu este consecventă, un nod va avea nevoie de expansiune repetată de fiecare dată când se obține un nou cel mai bun cost (până acum). ${\ displaystyle c '(N, P) = c (N, P) + h (P) -h (N)}$${\ displaystyle h}$

Dacă euristica dată este admisibilă, dar nu este consecventă, se poate forța în mod artificial valorile euristice de-a lungul unei căi să fie monotonice nedescrescând folosind ${\ displaystyle h}$

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

ca valoare euristică pentru în loc de , unde este nodul imediat precedent pe cale și . Această idee se datorează lui László Mérō și este acum cunoscută sub numele de pathmax. Contrar credinței obișnuite, pathmax nu transformă o euristică admisibilă într-o euristică consistentă. De exemplu, dacă A * folosește pathmax și o euristică admisibilă, dar care nu este consecventă, nu este garantat să aibă o cale optimă către un nod atunci când este extins pentru prima dată. ${\ displaystyle P}$${\ displaystyle h (P)}$${\ displaystyle N}$${\ displaystyle P}$${\ displaystyle h '(start) = h (start)}$

Vezi si

• Euristic admisibil

Referințe