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) 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:
- g(n) = costul minim cunoscut de la S la n.
- h(n) = estimarea costului minim ramas de la n pana la destinatie.
- f(n) = estimarea costului total al unui drum care trece prin n.
Alege nodul cu g(n) minim: cat a costat drumul pana aici?
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:
| Nod | g(n) | h(n) | f(n) = g(n) + h(n) |
|---|---|---|---|
| A | 3 | 12 | 15 |
| B | 5 | 4 | 9 |
| C | 7 | 1 | 8 |
Valorile sunt ilustrative: nu reprezinta un graf complet. Ele arata doar cum difera criteriul de selectie.
4. Ce ramane neschimbat?
- Costul nodului de plecare este initializat cu zero.
- Se mentine o multime de noduri candidate.
- Se extrage nodul cu prioritatea cea mai buna.
- Se examineaza vecinii si se actualizeaza costurile daca se descopera un drum mai ieftin.
- 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
| Caracteristica | Dijkstra | A* |
|---|---|---|
| Cost acumulat | g(n) | g(n) |
| Estimare a costului ramas | Nu | h(n) |
| Prioritate | g(n) | g(n) + h(n) |
| Informatii despre destinatie | Nu | Da |
| Optimalitate | Pentru costuri nenegative | Cu euristica si implementare adecvate |
6. Relatia dintre cei doi algoritmi
Daca folosim euristica h(n) = 0 pentru toate nodurile, atunci:
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:
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.