Căutarea A*
Algoritmul lui Dijkstra găsește cel mai scurt drum până la o țintă, dar caută în toate direcțiile deodată, chiar și în sens opus țintei. Căutarea A* adaugă o singură informație, o estimare a cât de departe mai este ținta, și dintr-odată căutarea se îndreaptă direct spre ea.
Ideea
Când căutați un traseu pe o hartă, nu examinați drumurile care duc departe de destinație la fel de atent ca pe cele care duc spre ea. Căutarea A* face la fel. Fiecare nod primește un scor: distanța de la start de până acum, g, plus o estimare a distanței rămase, h. Căutarea continuă mereu din nodul cu cel mai mic scor, așa că nodurile aflate spre țintă vin primele.
Pas cu pas
Dați startului distanța 0 și puneți-l într-o coadă cu scorul h(start). Repetați: luați nodul cu cel mai mic scor și marcați-i distanța ca definitivă. Dacă este ținta, opriți-vă: urmând înapoi nodurile reținute obțineți drumul. Altfel, pentru fiecare vecin care nu este definitiv, calculați distanța lui prin acest nod. Dacă este mai mică decât distanța lui de până acum, micșorați-o, rețineți acest nod ca drum până acolo și dați vecinului scorul egal cu noua distanță plus estimarea lui. Când două scoruri sunt egale, dacă luați întâi nodul cu estimarea mai mică, ajungeți de obicei mai repede la țintă.
Un exemplu
Luați un start A și o țintă D. A–B are lungimea 2 și B–D 2, iar A–C are 1 și C–D 5. Estimările în linie dreaptă până la D sunt 3 din A, 2 din B și 3 din C. A pornește cu scorul 0 + 3 = 3. Luarea lui A îi dă lui B scorul 2 + 2 = 4 și lui C scorul 1 + 3 = 4. La egalitate, A* îl ia pe B, nodul cu estimarea mai mică, iar B îi dă lui D scorul 4 + 0 = 4. Acum D are cel mai mic scor și cea mai mică estimare, deci este luat: cel mai scurt drum este A → B → D, de lungime 4, iar C, care duce în direcția greșită, nu devine niciodată definitiv. Algoritmul lui Dijkstra l-ar fi făcut definitiv întâi pe C, pentru că este cel mai apropiat nod de A.
O estimare bună
Estimarea nu trebuie să fie niciodată mai mare decât distanța reală până la țintă; o astfel de estimare se numește admisibilă, iar cu ea A* găsește întotdeauna un drum minim. Linia dreaptă este admisibilă, pentru că niciun traseu nu este mai scurt decât o linie dreaptă. Dacă, în plus, estimarea nu scade niciodată cu mai mult decât lungimea muchiei de la un nod la următorul, ea este consistentă, iar niciun nod definitiv nu mai trebuie examinat din nou. Cu cât estimarea este mai aproape de adevăr, cu atât A* are nevoie de mai puține noduri. O estimare de 0 este admisibilă, dar inutilă: A* devine atunci algoritmul lui Dijkstra. O estimare prea mare îl face pe A* mai rapid, dar poate rata cel mai scurt drum.
Istorie și utilizări
Peter Hart, Nils Nilsson și Bertram Raphael de la Stanford Research Institute au publicat A* în 1968, în timp ce lucrau la Shakey, unul dintre primii roboți mobili. Versiunile lor anterioare se numeau A1 și A2; steaua marca versiunea despre care au demonstrat că este optimă. Astăzi, A* mută personaje în jurul obstacolelor în jocurile video, planifică rute și mișcări ale roboților și rezolvă puzzle-uri precum jocul 15, unde estimarea adună cât de departe este fiecare piesă de locul ei.
Explorați
Deschideți aplicația și apăsați Pas. Numerele de pe muchii sunt lungimile lor, care aici corespund cu cât de lungi sunt desenate, iar linia întreruptă arată estimarea în linie dreaptă până la țintă. Coada de sub graf listează nodurile după scor, cel mai mic primul. Când ținta este definitivă, linia de stare compară câte noduri a făcut definitive A* cu câte ar fi avut nevoie algoritmul lui Dijkstra. Încercați o țintă într-un colț îndepărtat al unui graf mare ca să vedeți cea mai mare diferență.
Întrebări frecvente
Ce înseamnă steaua din A*?
Hart, Nilsson și Raphael au descris mai întâi algoritmi pe care i-au numit A1 și A2. A* („A stea”) a fost versiunea despre care au demonstrat că găsește un drum minim extinzând cele mai puține noduri dintre algoritmii comparabili care folosesc aceeași estimare, atunci când estimarea este consistentă.
Care este complexitatea în timp a lui A*?
În cel mai rău caz, cu o estimare inutilă, A* face aceeași muncă precum algoritmul lui Dijkstra: O((V + E) log V) cu un heap binar. Cu o estimare bună face definitive doar o parte din noduri, de aceea este rapid în practică.
Ce face o euristică bună pentru A*?
Trebuie să fie rapid de calculat, să nu supraestimeze niciodată distanța reală și să fie cât mai aproape de ea. Pe o grilă unde vă puteți mișca doar sus, jos, stânga și dreapta, distanța Manhattan este o alegere obișnuită; pe o hartă, distanța în linie dreaptă.
Ce se întâmplă dacă euristica supraestimează?
Atunci A* poate returna un drum care nu este cel mai scurt, pentru că poate termina înainte să examineze traseul mai bun. Unele programe fac asta intenționat (A* ponderat) ca să schimbe puțină calitate a drumului pe multă viteză.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Încercați căutarea A*