Laborator 13: Best-first search și A*

În sensul cel mai general, putem spune că un algoritm de căutare este de tipul Best-First dacă păstrează o evidenţă cu candidaţii şi alege să verifice mereu candidaţii cu potenţial mai mare înainte de a-i verifica pe cei cu potenţial mai mic(cu alte cuvinte, verifică întâi candidatul cel mai bun - cu cel mai mare potenţial).

• Trebuie să atribuim un „potenţial de rezultat“ fiecărui candidat, adică să găsim o metodă cu care să decidem dacă un candidat prezintă mai mult interes decât altul, dacă avem aşteptări mai mari de a găsi rezultatul dorit alegând acest candidat.
• În multe cazuri, este mai ușor să măsurăm cât de „rău“ este un candidat. Funcţia de „cost potenţial“ ne ajută să descriem potenţialul de rezultat. Cu cât este mai mare costul la care ne aşteptăm de la un candidat, cu atât este mai mic potenţialul lui de a ne duce la rezultatul căutat. Cu alte cuvinte, putem spune că cel mai bun candidat este cel mai puţin costisitor candidat.
• După ce definim o funcţie de acest fel, putem introduce candidaţii într-o coadă prioritară(priority queue) în funcţie de costul aşteptat în aşa fel încât primul candidat din coadă să fie cel mai bun candidat.

Folosind noţiunile de mai sus, încercăm să identificăm funcţiile de cost potenţial pentru următoarea problemă: găsirea unui drum de cost minim de la un nod sursă(S) la un nod destinaţie(D) într-un graf.

• Candidaţii = nodurile din graf care urmează să fie incluse în soluţie
• Un candidat face parte din soluţie dacă drumul căutat trece prin el
• Nodurile S şi D au costul potenţial = 0, dar considerăm nodul D „nedescoperit“ iniţial şi plecăm din nodul S
• Toate celelalte noduri au iniţial costul potenţial infinit
• Presupunem că ne aflăm la nodul curent(C) extras de la începutul cozii şi evaluăm nodurile vecine ale acestuia

Definim funcţia de cost potenţial h(N) = posibilul cost din nodul curent(C), prin nodul vecin(N), până la nodul destinaţie(D)

Metoda Greedy construieşte soluţia alegând mereu optimul local, cu alte cuvinte

• h(C) = 0, pentru că deja am inclus nodul C în soluţia parţială
• h(N) = costul muchiei (C,N), pentru orice nod N care nu este deja în soluţia parţială

Definim funcţia de cost potenţial g(N) = costul minim al drumului din punctul iniţial(S) până în nodul N

• În general, nu este necesar şi nici suficient ca funcţia de cost potenţial a unui nod să fie 0 pentru ca acel nod să facă parte din soluţia finală.
• Metoda Greedy poate duce la funcţia g(N) = 0 pentru noduri care par bune pe moment, dar nu se poate ajunge la D fără revenirea în nodul C(căutarea unui nou optim local după ce acesta a eşuat complet).
• La algoritmul lui Dijkstra, în afară de nodurile S şi D, celelalte noduri au cost potenţial nenul(excepţie dacă există muchii de cost 0).

• Metoda Greedy obţine foarte repede un rezultat(un drum de la S la D), dar, în multe cazuri, acesta nu este cel mai scurt(de cost minim).
• Algoritmul lui Dijkstra cu coadă prioritară are nevoie de mai mult timp pentru a obţine un rezultat, dar este garantat că, în momentul în care descoperă nodul D, a găsit cel mai scurt drum şi algoritmul se poate opri.

• Putem găsi o cale de mijloc care să fie mai rapidă decât algoritmul lui Dijkstra şi care să ducă la soluţia dorită?
• Când putem defini o funcţie f(N) care să fie o combinaţie a funcţiilor g(N) şi h(N)) care să ducă la un algoritm mai bun?

Algoritmul A* este definit, în sens general, ca fiind un algoritm de căutare de tip BFS(Best-First) ce foloseşte funcţia de cost potenţial

f(N) = g(N) + h(N), unde
g(N) = costul minim pentru un drum de la S la N
h(N) = estimarea pentru costului minim pentru un drum de la N la D

Definirea funcţiei g nu ridică probleme(putem folosi aceeaşi funcţie ca la algoritmul lui Dijkstra), dar, din punct de vedere al funcţiei h, numită funcţie euristică, distingem câteva cazuri:

• dacă funcţia h(N) = 0 peste tot, algoritmul coincide cu Dijkstra cu coadă prioritară → soluţie optimă garantată, dar lent
• dacă funcţia h(N) < costul minim al drumului de la N la D, oricare ar fi N → soluţie optimă garantată, mai rapid
• dacă funcţia h(N) = costul minim al drumului de la N la D, oricare ar fi N → cel mai rapid algoritm cu soluţia optimă garantată
• dacă funcţia h(N) > costul minim al drumului de la N la D(chiar şi pentru câteva noduri N) → optimul nu e garantat, dar e şi mai rapid
• dacă funcţia h(N) domină, atunci g(N) nu mai are efect, iar algoritmul A* devine Greedy Best-First Search.

O estimare iniţială bună creşte performanţa algoritmului şi păstrează rezultatul optim.

Presupunem următoarul caz:

• într-un oraş, oricare două străzi sunt paralele sau perpendiculare între ele;
• orice zonă mărginită de străzi are formă pătrată de latură = Lat(metri), iar pe colţurile pătratului sunt intersecţii;
• unele intersecţii sunt blocate şi ştim care sunt acestea
• se dau intersecţiile S şi D

Dacă putem reduce orice intersecţie la un punct, găsiţi drumul cel mai scurt pe care poate merge un taxi din S în D(fără a trece prin intersecţiile blocate)

• Putem reprezenta intersecţiile cu o matrice.
• Ne putem deplasa doar pe orizontală sau pe verticală, deci, în cel mai bun caz, lungimea drumului minim de la un punct oarecare N la D poate fi exprimată in funcţie de coordonatele intersecţiilor
• Fie (Nx, Ny) = poziţia lui N, fie (Dx, Dy) = poziţia lui D şi fie dMin(N, D) = lungimea drumului minim de la N la D.
• Atunci, în cel mai bun caz, dMin(N, D) = |Nx - Dx| + |Ny - Dy|
• Putem defini h(N) = dMin(N, D) ca funcţie euristică pentru acest caz