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
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Algortimul de Cautare A Star (ID: 149372)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.