A* algoritam

Algoritam A* za određivanje najkraćeg puta između dva čvora grafa je jedan od fundamentalnih i najpopularnijih algoritama veštačke inteligencije. Algoritam je uopstenje Dajkstrinog algoritma i obično smanjuje broj čvorova grafa koje treba ispitati. To smanjivanje je zasnovano na korišćenju heuristike koja procenjuje donju granicu daljine do ciljnog čvora.

Prvu verziju algoritma A* su razvili Peter E. Hart, Nils Nilson i Bertram Rafael na Istraživačkom institutu Stenford 1968. godine, kao unapređenje Dajkstrinog algoritma iz 1959. godine.

Opis A* algoritma

Algoritam A* obično smanjuje broj čvorova grafa koje treba ispitati. To smanjivanje je zasnovano na korišćenju heuristike koja procenjuje donju granicu daljine do ciljnog čvora. Kao i u Dajkstrinom algoritmu, čvorove koji tek treba obraditi čuvaju se u redu, sortiranom prema nekom kriterijumu. Sve vreme se održavaju lista otvorenih čvorova — čvorova koji su već posećeni ali nisu obrađeni svi njihovi susedi i zatvorenih čvorova — čvorova koji su posećeni i kojima su obrađeni svi njihovi susedi. Ključna razlika je u tome što Dajkstrin algoritam (kao „neinformisani algoritam“) uzima u obzir samo cenu od polaznog do tekućeg čvora, dok A* (kao „informisani algoritam“) koristi funkciju evaluacije $f$ nad čvorovima grafa, definisanu na sledeći način: $f(x)=g(x)+h(x)$ gde je $g(x)$ cena puta od polaznog čvora do čvora $x$, a $h(x)$ je procenjena (heuristička) cena najjeftinijeg puta od čvora $x$ do ciljnog čvora. Dok tragamo za najkraćim putem, uvek znamo tekuću minimalnu cenu od polaznog čvora do čvora $x$ (tj. tekuću vrednost za $g(x)$), ali se vrednost $h(x)$ može samo procenjivati. Da bi se obezbedila optimalnost A* pretrage, funkcija $h$ mora da bude konzistentna (eng. consistent), tj. da za bilo koja dva susedna čvora $x$ i $y$ važi: $h(x)<=c(x,y)+h(y)$ gde je $c(x,y)$ cena pridružena grani $(x,y)$. U nekim specijalnim slučajevima dovoljno je da funkcija $h$ bude dopustiva (eng. admissible), tj. da nikada ne precenjuje cenu stizanja do cilja. Svojstvo konzistentnosti ima za posledicu svojstvo dopustivosti. Dodatno, dopustive funkcije su često i konzistentne.

Istorija algoritma

1968. godine Nils Nilsson je predložio heuristički pristup za navigaciju Shakey the Robot kroz sobu sa preprekama. Ovaj algoritam pronalaženja puteva, nazvan A1, je bio brža verzija tadašnjeg najpoznatijeg formalnog pristupa, Dajkstra algoritma. Bertram Raphael je predložio neka značajna poboljšanja ovog algoritma, nazivajući revidiranu verziju A2. Nakon toga Peter E. Hart je argumentovano pokazao da je A2 , sa manjim izmenama, najbrži algoritam za pronalaženje najkraćih puteva. Hart, Nilsson i Raphael su zatim zajednički razvili dokaz kojim su pokazali da je revidirani A2 algoritam optimalan za pronalaženje najkraćih puteva pod određenim dobro definisanim uslovima. Nazvali su novi algoritam A*.

Faze algoritma

Kao i svi algoritmi pretrage, A* prvo pretražuje puteve koji najverovatnije vode ka cilju. Od pohlepne BFS pretrage ga razlikuje to što A* uzima u obzir rastojanje koje je već prešao; deo heuristike $g(x)$ je cena od početnog čvora, a ne samo lokalna cena od prethodno obiđenog čvora. Polazeći od početnog čvora, on pamti u redu sa prioritetom čvorove koje treba obići, poznat kao otvoren skup. Što je niža vrednost funkcije $f(x)$ za zadat čvor $x$ , veći mu je prioritet. U svakom koraku algoritma, čvor sa najnižom vrednošću funkcije $f(x)$ se uklanja iz reda, ažuriraju se vrednosti $f$ i $g$ njegovih suseda, i oni se ubacuju u red. Algoritam se nastavlja sve dok vrednost $f$ ciljnog čvora ne bude najniža u redu (ili dok ima čvorova u redu). Vrednost $f$ ciljnog čvora predstavlja dužinu najkraćeg puta, s obzirom na to da je vrednost $h$ jednaka nuli u dopustljivoj heuristici.

Prethodno opisan algoritam nam daje samo dužinu najkraćeg puta. Da bi pronašli celokupan redosled koraka, algoritam se može lako prepraviti tako da svaki čvor na putu pamti svog prethodnika. Nakon što je algoritam završen, svaki čvor će pokazivati na svog prethodnika, sve do ciljnog čvora. Pored toga, ako je heuristika monotona (ili konzistentna), zatvoren skup čvorova koji su posećeni se može iskoristiti da unapredi pretragu.

Pseudokod

Algoritam: Algoritam A*

Ulaz: Graf G, polazni čvor source i ciljni čvor goal.

Izlaz: najkraći put od čvora source do čvora goal u grafu G (ako postoji put između ova dva čvora).

1. Inicijalno je zatvorena lista prazna.
2. Dodaj polazni čvor (zajedno sa procenjenom cenom do ciljnog čvora, koja je određena funkcijom h u otvorenu listu čvorova koje je potrebno razmotriti.
3. Izvršavaj sledeću petlju dok god ima elemenata u otvorenoj listi:
   • Izaberi čvor n (zvaćemo ga tekući čvor) iz otvorene liste koji ima najmanju vrednost f(n).
   • Ako je tekući čvor ciljni čvor, izvesti o uspehu, konstruiši put od polaznog do ciljnog čvora (idući unazad - od ciljnog čvora) i zaustavi izvršavanje petlje.
   • Ispitaj sve čvorove koji su direktno dostupni iz tekućeg čvora i pri tome ne pripadaju zatvorenoj listi. Za svaki takav čvor m uradi sledeće:
     • Ako on nije u otvorenoj listi, dodaj ga u otvorenu listu. Označi tekući čvor kao roditelja ovog čvora (što je važno za konstruisanje staze na kraju). Izračunaj i zapamti vrednosti f(m), g(m) i h(m) za čvor. (Primetimo da se vrednosti g(m) mogu izračunati na inkrementalan i efikasan način: vrednost g(m) jednaka je zbiru vrednosti funkcije g za roditelj čvora m i ceni puta od roditelja do m).
     • Ako je on već u otvorenoj listi, proveri da li je odgovarajući put od polaznog čvora do m bolji od tekućeg puta (preko čvora n). Za tu proveru koristi se vrednost g(m). Manja vrednost g znači da je taj put bolji. Ako je tekući put bolji, promeni informaciju o roditelju čvora m na čvor n i ažuriraj vrednosti g(m) i f(m).

   • Izbriši tekući čvor iz otvorene liste i dodaj ga u zatvorenu listu čvorova (on ne treba da ponovo bude ispitivan).

4. Na kraju, ako je petlja završena a da nije prijavljen uspeh (tada je otvorena lista prazna), onda ne postoji traženi put. Inače, put je pronađen i on se konstruiše od dete-roditelj veza (idući unazad od ciljnog čvora).

 1    function A*(start,goal)
 2        closedset := the empty set    // The set of nodes already evaluated.
 3        openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
 4        came_from := the empty map    // The map of navigated nodes.
 5
 6        g_score[start] := 0    // Cost from start along best known path.
 7        // Estimated total cost from start to goal through y.
 8        f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)
 9    
 10        while openset is not empty
 11            current := the node in openset having the lowest f_score[] value
 12            if current = goal
 13                return reconstruct_path(came_from, goal)
 14        
 15            remove current from openset
 16            add current to closedset
 17            for each neighbor in neighbor_nodes(current)
 18                tentative_g_score := g_score[current] + dist_between(current,neighbor)
 19                if neighbor in closedset and tentative_g_score >= g_score[neighbor]
 20                    continue
 21
 22                if neighbor not in openset or tentative_g_score < g_score[neighbor] 
 23                    came_from[neighbor] := current
 24                    g_score[neighbor] := tentative_g_score
 25                    f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
 26                    if neighbor not in openset
 27                        add neighbor to openset
 28
 29        return failure
 30
 31    function reconstruct_path(came_from, current_node)
 32        if current_node in came_from
 33            p := reconstruct_path(came_from, came_from[current_node])
 34            return (p + current_node)
 35        else
 36            return current_node

Primer

Ilustracija A* algoritma za pronalaženje puta od početnog čvora do cilja u problemu planiranja kretanja robota. Prazni krugovi predstavljaju čvorove iz otvorenog skupa, tj. one čvorove koje tek treba ispitati, i obojeni krugovi predstavljaju čvorove iz zatvorenog skupa. Boja svakog čvora iz zatvorenog skupa ukazuje na udaljenost od početnog čvora: što je čvor zeleniji bliži je cilju. Može se primetiti da se algoritmom uvek kreće pravolinijski od početnog čvora ka cilju, kada se na putu naiđe na prepreku ispituju se alternativni putevi kroz čvorove iz otvorenog skupa.

Види још: Dajkstrin algoritam

Primer A* algoritma je traženje puta u grafu gde čvoriovi predstavljaju gradove, a grane puteve između gradova, gde je h(x) pravolinijsko rastojanje od početnog do krajnjeg grada:

Zelena: Početni grad.
Plava: Krajnji grad.

Narandzasta: Posećeni grad.

Svojstva

Kao i Pretraga u Širinu, A* algoritam je kompletan i uvek pronalazi rešenje, ukoliko ono postoji. Ako je heustička funkcija $h$ dopustiva, što znači da nikad ne precenjuje minimalnu cenu za postizanje cilja, onda je i sam A* algoritam dopustiv (optimalan), ako ne koristimo zatvoren skup. Ukoliko pak, koristimo zatvoren skup, onda $h$ takođe mora biti monotona (konzistentna) da bi A* bio optimalan. Ovo znači da za svaki par susednih čvorova $x$ i $y$ , gde je $d(x,y)$ dužina grane između njih, mora da važi: $h(x)<=d(x,y)+h(y)$ Ovim je obezbeđeno da za svaki put $X$ od početnog čvora do $x$ važi:

$L(X)+h(x)<=L(X)+d(x,y)+h(y)=L(Y)+h(y)$

gde je sa $L(\cdot )$ označena dužina puta, a $Y$ je put $X$ koji obuhvata čvor $y$. Drugim rečima, nemoguće je smanjiti (ukupno rastojanje do sad + preostao rastojanje ) proširivanjem puta susednim čvorom. Monotonost podrazumeva dopustivost kada je heuristička procena u bilo kom ciljnom čvoru nula, jer (dopuštajući da $P=(f,v_{1},v_{2},\ldots ,v_{n},g)$ bude najkraći put od bilo kog čvora $f$ do najbližeg ciljnog čvora $g$ ):

$h(f)<=d(f,v_{1})+h(v_{1})<=d(f,v_{1})+d(v_{1},v_{2})+h(v_{2})<=\ldots <=L(P)+h(g)=L(P)$

A* je takođe optimalan za bilo koju heuristiku $h$, što znači da bilo koji algoritam koji koristi istu heuristiku, neće biti optimalniji od A*, osim ukoliko postoji više parcijalnih rešenja gde $h$ tačno predviđa cenu najkraćeg puta. Čak i u ovom slučaju, za svaki graf postoji neki red prekidanja veza u redu sa prioritetom takav da A* ispituje što je manje čvorova.

Specijalni slučajevi

Obilasci grafa u dubinu i širinu mogu se smatrati specijalnim slučajevima algoritma A*.

Za obilazak grafa u dubinu, može se koristiti algoritam A* sa g = 0 i pogodno odabranom funkcijom h. Na primer, neka je brojač C inicijalizovan na neku veoma veliku vrednost. Kad god obrađujemo neki čvor dodajemo vrednost C svim njegovim susedima. Nakon svake dodele smanjujemo vrednost C za jedan. Time će vrednost h(x) da bude veća za čvorove na koje se ranije naišlo. Primetimo da ovako definisana funkcija h nije nužno dopustiva.

Dajkstrin algoritam, kao specijalni slučaj obilaska grafa u širinu takođe je specijalni slučaj algoritma A* gde je h(x) = 0 za svaki čvor x. Ovakva funkcija h je dopustiva i konzistentna i garantuje nalaženje optimalnog puta.
Za g = 0, algoritam A* ponaša se u skladu sa najpre-najboljim, pohlepnim pristupom koji najpre obrađuje čvorove sa najpovoljnijom heursitičkom vrednošću. Ova varijanta algoritma nije nužno optimalna.

Opšti algoritam A* često se primenjuje za nalaženje puta na uniformnoj mreži čvorova (koja odgovara, na primer, diskretizovanoj mapi). Tada on dobija specifičnu formu. Pretpostavimo da je mreža pravilna (sačinjena od kvadrata) i da ima pravougaonu formu. Dodatno, pretpostavljamo da neki čvorovi (tj. neki kvadrati, neka polja mreže) nisu dostupni i da oni predstavljaju prepreke. Svako polje je povezano sa svakim susednim poljem (osim sa preprekama), te ima (izuzev polja na rubu) osam susednih polja (ali neka od njih mogu biti prepreke i kao takve nedostupne). U ovoj varijanti problema, cene su pridružene čvorovima (poljima), a ne granama grafa (vezama između susednih čvorova). U ovom kontekstu, funkcija g(n) je zbir svih cena polja duž puta od polaznog do polja n. Na primer, svakom „horizontalnom“ ili „vertikalnom“ pokretu može se pridružiti cena 1 a svakom dijagonalnom cena $1.414\approx {\sqrt {2}}$ (ovakva cena odgovara Euklidskom rastojanju između središta polja). Funkcija h može se opisati na različite načine. Jedan od njih je Euklidsko rastojanje između dva čvora, a jedan metod Menhetn u kojem se broji ukupan broj polja pređenih horizontalno ili vertikalno da bi se došlo od polaznog polja do tekućeg polja. Primetimo da ukoliko su dozvoljeni dijagonalni potezi, onda Menhetn metod potencijalno precenjuje rastojanje do ciljnog čvora i zbog toga ne garantuje nalaženje najkraćeg puta. No, ovaj metod u praksi obično daje dobre rezultate i nađeni putevi su obično dovoljno dobri, čak i ako nisu najkrači. Kada se određuje vrednost h, mogu da se ignorišu sve prepreke jer vrednost h(n) je procenjeno a ne stvarno rastojanje.

Kada se algoritam A* primenjuje za nalaženje puta na uniformnoj mreži, on daje korake u osam mogućih smerova što kasnije često dovodi do neprirodnih puteva sačinjenih od segmenata sa jednim od osam nagiba. Omekšavanje (eng. smoothing) je tehnika za unapređivanje takvih puteva tako da oni izgledaju prirodnije.

Potpunost i optimalnost

Može se dokazati da je algoritam A* potpun i da je, pod određenim uslovima optimalan:

• Potpunost: Ako postoji put između dva čvora, algoritam A* će naći jedan takav (naravno, ukoliko je raspoloživo dovoljno vreme i memorijski prostor). Čak i ako je heuristička funkcija veoma loša, ciljni čvor če biti dostignut u konačnom broju koraka.
• Optimalnost: Od svih puteva između dva data čvora, biče izabran najkraći put, ukoliko je funkcija heuristike $h$ konzistentna. Ukoliko funkcija $h$ nije dopustiva, ali ne precenjuje stvarno cenu za više od d, onda je cena puta koji će pronaći algoritam A* skuplji od najkraćeg za ne više od d.

Ukoliko se ne koristi lista zatvorenih čvorova (tj. ukoliko se razmatraju i susedni čvorovi koji su već bili tekući), da bi algoritam bio optimalan dovoljno je da funkcija $h$ bude dopustiva (nije neophodno da bude konzistentna).

Ukoliko se koristi nad stablima, da bi algoritam bio optimalan dovoljno je da funkcija $h$ bude nenegativna i dopustiva. Ukoliko funkcija $f$ odgovara optimalnom putu, onda algoritam A* obrađuje sve čvorove za koje važi $f(n)<f^{*}(n)$ i neke čvorove n za koje važi $f(n)=f^{*}(n)$.

Složenost

Vremenska složenost algoritma A* zavisi od heuristike. U najgorem slučaju, broj obrađenih čvorova je eksponencijalan u odnosu na dužinu najkraćeg puta, ali je polinomijalan ako funkcija heuristike $h$ zadovoljava sledeći uslov:
$|h(x)-h^{*}(x)|\leq O(logh^{*}(x))$

gde je $h^{*}$ optimalna heuristika, tj. funkcija koja vraća tačnu cenu puta od čvora x do ciljnog čvora. Drugim rečima, greška funkcije $h$ ne treba da raste brže od logaritma idealne heuristike.

Varijante A* algoritma

• D*
• IDA*
• Ivična pretraga
• Inkrementalno heurističko pretraživanje
• SMA*
• Teta*

Literatura

• Veštačka inteligencija, profesor Predrag Janičić, MATF, Beograd 2010. godina.
• A* with Jump point search
• Clear visual A* explanation, with advice and thoughts on path-finding
• Variation on A* called Hierarchical Path-Finding A* (HPA*)
• A* Algorithm tutorial

Spoljašnje veze

• A* Implementation in Java
• A* Implementation in C#
• A* Pathfinding in Objective-C (Xcode)
• StraightEdge open source java 2D path finding and lighting project focused on performance, with demos.