Algoritmul A*

Algoritmul A* se folosește pentru a găsi un drum de cost minim de la un nod-start la un nod-scop într-un graf ponderat.

Informații generale

Date de intrare:

  • graful (nodurile, muchiile împreună cu costurile lor)
  • nodul din care începe căutarea (nodul-start)
  • un scop dat sub forma unei condiții pe care trebuie să o îndeplinească nodul căutat (se poate oferi chiar nodul propriu-zis, condiția fiind relația de egalitate cu acest nod). Vom numi mai departe nodul care îndeplinește condiția nod-scop
  • o estimare (euristică) a costului de la fiecare nod din graf la nodul (nodurile) scop.

Notații:

  • $f$ - costul unui drum
  • $\hat{f}$ - costul estimat al unui drum
  • $g(nod_c)$ - costul unui drum de cost minim de la nodul start la un nod curent, $nod_c$, din drum
  • $h(nod_c)$ - costul efectiv al drumului de cost minim de la nodul curent la nodul scop pe un anumit drum
  • $\hat{h}(nod_c)$ - costul estimat de la nodul curent la nodul scop (euristica)

Pentru un drum dat D, avem formula: $f_D$ = $g_D(nod_c$) + $h_D(nod_c$), unde $nod_c$ e un nod din drumul D

Deoarece pe parcursul construirii arborelui de parcurgere nu cunoaștem costul adevărat de la nodul curent la nodul scop (graful fiind descoperit pe măsura ce e parcurs), ne vom folosi în algoritm de formula costului estimat: $\hat{f}_D$ = $g_D$($nod_c$) + $\hat{h}_D$($nod_c$).

Admisibilitate:

Spunem că euristica este admisibilă dacă îndeplinește condiția: $\hat{h}(nod) \leq h(nod)$

Regula de consistență:

Având o muchie $n_1 \rightarrow n_2$, euristica calculată în nodul $n_1$ trebuie să fie mai mică sau egală decât costul muchiei $n_1 \rightarrow n_2$ adunat la euristica nodului $n_2$

$\hat{h}(n1) \leq cost(n1 \rightarrow n2) + \hat{h}(n2)$

Pașii algoritmului

Se consideră două liste: OPEN (cu nodurile descoperite care înca nu au fost expandate) și CLOSED (cu nodurile descoperite și expandate).

  1. În lista open se pune la început doar nodul de pornire.
  2. Inițial lista closed e vidă
  3. Cât timp lista open nu e vidă se execută repetitiv pașii următori:
    • Se extrage primul nod, n, din lista open și se pune în closed.
    • Dacă nodul n este nod scop, se oprește căutarea și se afișează drumul de la nodul-start până la nodul n.
    • Se extinde nodul n, obținând succesorii lui în graf. Nu se vor lua în considerare succesorii care se află în drumul de la nodul start la n. Toți succesorii îl au ca părinte pe n. Toți succesorii care nu se află deja în open sau closed sunt inserați în lista open astfel încât aceasta să fie în continuare ordonată crescător dupa f.
    • Pentru succesorii care sunt deja în open sau closed, în cazul în care pentru drumul care trece prin n, s-a obținut un f mai mic, li se schimbă părintele în n și li se actualizează f-ul, iar nodurile din open sunt repoziționate în lista astfel încât să rămână ordonată crescător după f.
    • Pentru nodurile din closed (care au fost deja expandate) ar trebui refăcut calculul pentru nodurile succesoare lor, prin urmare cel mai simplu este să le readăugăm direct în open.

Implementare

Pentru implementare putem considera niște clase ajutătoare, care ar fi adaptate la particularitățile problemei curente rezolvate cu A*.

Clasa Nod reprezintă clasa prin care se memorează informațiile despre nodurile din graf. Poate avea următoarele proprietăți:

  • informație - referință către informația nodului
  • părinte - referință către nodul-părinte din arbore. Pentru rădăcina arborelui, părintele va avea valoarea None.
  • g - costul de la rădăcina arborelui până la nodul curent
  • f - costul estimat pentru drumul care pornește de la rădăcină și trece prin nodul curent
  • h - estimarea făcuta pentru nod (valoarea funcției euristice pentru nod)

și următoarele metode:

  • expandează / succesori - care va returna o listă cu toți succesorii posibili ai nodului curent
  • scop - care testează dacă nodul e nod scop

Exerciții

Exercițiile acestui capitol sunt accesibile aici: A Star