Algoritmi de cautare

Algoritmul A* prin comparatie cu Dijkstra

A* extinde algoritmul Dijkstra folosind o estimare a costului ramas pana la destinatie, pentru a orienta cautarea catre solutia optima.

1. Cum functioneaza Dijkstra?

Dijkstra porneste dintr-un nod initial S si calculeaza progresiv costurile minime ale drumurilor catre celelalte noduri. La fiecare pas, alege nodul cu cel mai mic cost cunoscut de la S:

g(n)

g(n) este costul minim cunoscut de la S la nodul n.

Dijkstra nu foloseste informatii despre apropierea de destinatie. Poate explora noduri in directii nepromitatoare doar pentru ca sunt ieftin de atins din S.

2. Ce modifica A*?

A* pastreaza mecanismul de actualizare a costurilor din Dijkstra, dar schimba prioritatea de explorare:

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

Alege nodul cu g(n) minim: cat a costat drumul pana aici?

A*

Alege nodul cu f(n) minim: cat ar costa drumul complet prin acest nod?

3. Exemplu comparativ

Presupunem ca urmatoarele trei noduri sunt candidate pentru explorare:

Nodg(n)h(n)f(n) = g(n) + h(n)
A31215
B549
C718
Apasa unul dintre butoane pentru a vedea alegerea algoritmului.

Valorile sunt ilustrative: nu reprezinta un graf complet. Ele arata doar cum difera criteriul de selectie.

4. Ce ramane neschimbat?

  1. Costul nodului de plecare este initializat cu zero.
  2. Se mentine o multime de noduri candidate.
  3. Se extrage nodul cu prioritatea cea mai buna.
  4. Se examineaza vecinii si se actualizeaza costurile daca se descopera un drum mai ieftin.
  5. Se continua pana cand destinatia este extrasa pentru explorare.

Diferenta esentiala: Dijkstra prioritizeaza dupa g(n), iar A* dupa g(n) + h(n). Pentru A*, regulile de redeschidere a nodurilor depind de proprietatile euristicii.

5. Comparatie sintetica

CaracteristicaDijkstraA*
Cost acumulatg(n)g(n)
Estimare a costului ramasNuh(n)
Prioritateg(n)g(n) + h(n)
Informatii despre destinatieNuDa
OptimalitatePentru costuri nenegativeCu euristica si implementare adecvate

6. Relatia dintre cei doi algoritmi

Daca folosim euristica h(n) = 0 pentru toate nodurile, atunci:

f(n) = g(n) + 0 = g(n)

Dijkstra este un caz particular al algoritmului A*.

Pentru a garanta solutia optima, euristica trebuie sa respecte anumite conditii. O euristica admisibila nu supraestimeaza costul minim real ramas. O euristica consistenta respecta, pentru orice arc (u,v) de cost c(u,v), inegalitatea:

h(u) ≤ c(u,v) + h(v)

In varianta uzuala de A* pe graf, consistenta permite inchiderea definitiva a nodurilor. Cu o euristica doar admisibila, poate fi necesara redeschiderea lor pentru a garanta optimalitatea.

O euristica informativa poate reduce numarul de noduri explorate fata de Dijkstra, dar nu garanteaza o reducere in orice graf.

Ideea fundamentala

Dijkstra decide unde sa continue pe baza costului deja acumulat. A* combina acest cost cu o estimare a costului ramas pana la destinatie.

A* nu schimba obiectivul cautarii drumului de cost minim. Schimba ordinea in care sunt explorate posibilitatile de a ajunge la solutia optima.