Algortimul de Cautare A Star

A* (A star)

A* este cel mai cunoscut algoritm de căutare. A* gasește durmul cu costul cel mai mic de la un nod inițial dat pană la un nod-scop,unde nodul inițial reprezintă locația curentă si nodu-scop locația in care trebuie sa se ajungă. Algoritmul urmarește mereu soluția care pare cea mai aproape de surs. Costul reprezintă timpul de trecere dintr-un nod in altul, a* gasește dumul cu costul cel mai mic. Pentru fiecare nod definim o funcție de evaluare f care indică cît de promițator este un nod in gasirea unui drum catre nodul-scop(cu cît f este mai mic cu atat nodul este mai promițător).

f(nod)=g(nod)+h(nod)

g(nod)-este drumul parcurs de la nodul ințial pană la nodul curent

h(nod)- este o estimare euristică de la nod pana la cea mai apropiată soluție

Algoritmul folosește doua mulțimi:

1) close- indică nodurile deja explorate (s-a trecut deja prin nodurile respective, ele nu vor fi niciodată reexplorate)

2) open- indică nodurile descoperite(nodurile prin care urmează să treacă)

A star functionează în felul următor: se introduce în mulțimea open nodul corespunzător stării inițiale . Nodurile care urmează să fie explorate vor fi introduse in mulțimea open. La fiecare trecere se extrage din open nodul cu f(n) minim,care reprezintă si drumul cel mai scurt pană la nodul-scop. După ce un nod a fost explorat va fi introdus in close.

Exemplu: Figura 1 poate fi considerat o hartă in care S reprezintă punctul de plecare, G este punctul final si X reprezintă anumite obstacole . A star trebuie să gasescă drum cel mai scurt de la S la G ținînd cont de obstacole.Direcțiile programului sunt:sus,jos,dreapta și stanga.

0 1 2 3 4

0

1

2

3

4

Figură 1-Hartă

Euristicul (h)

f=g+h(x,y)

Open-pozitia nodul prin care trece

Valoarea g=5(drumul parcrus,pană in momentul

de fată s-au parcurs 5 noduri)

Euristicul h=3(estimare euristică ea este aleasă din

tabelul euristic)

open[4,1] 5,8 (f=5+3)

Acuma programul va avea două direcți,va trebui să caute drumul cu valorea f cea mai mică.

open[4,2]

Valoarea g=6

Euristicul h=2

open[4,2] 6,8 (f=6+2)

open[3,2] 7,10

Valoarea g=7

Euristicul h=3

open[3,2] 7,10 (f=7+3)

Dacă va merge in sus incepe incepe să se departeze de punctul final iar valorea f crește.

Open[4,3]

Valoarea g=7

Eurisitul h=1

Open[4,3] 7,8(f=7+1)

Din moment ce se urmrește o valorea f mai mică a star va merge in dreapta deoarece nodul din dreapta are valore f mai mică, scăzînd valorea lui f a star să se apropie de punctul final.

Traseul cel mai scurt gasit de program