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  nad čvorovima grafa, definisanu na sledeći način:

gde je  cena puta od polaznog čvora do čvora , a  je procenjena (heuristička)
cena najjeftinijeg puta od čvora  do ciljnog čvora. Dok tragamo za najkraćim
putem, uvek znamo tekuću minimalnu cenu od polaznog čvora do čvora  
(tj. tekuću vrednost za ), ali se vrednost  može samo procenjivati. Da
bi se obezbedila optimalnost A* pretrage, funkcija  mora da bude konzistentna
(eng. consistent), tj. da za bilo koja dva susedna čvora  i  važi:

gde je  cena pridružena grani . U nekim specijalnim slučajevima
dovoljno je da funkcija  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  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  za zadat čvor  , veći mu je prioritet. U svakom koraku algoritma, čvor sa najnižom vrednošću funkcije  se uklanja iz reda, ažuriraju se vrednosti  i  njegovih suseda, i oni se ubacuju u red. Algoritam se nastavlja sve dok vrednost  ciljnog čvora ne bude najniža u redu (ili dok ima čvorova u redu). Vrednost  ciljnog čvora predstavlja dužinu najkraćeg puta, s obzirom na to da je vrednost  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).
 Inicijalno je zatvorena lista prazna.
 Dodaj polazni čvor (zajedno sa procenjenom cenom do ciljnog čvora, koja je određena funkcijom h u otvorenu listu čvorova koje je potrebno razmotriti.
 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).

 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 

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  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 
 takođe mora biti monotona (konzistentna) da bi A* bio optimalan. Ovo znači da za svaki par susednih čvorova  i  , gde je  dužina grane između njih, mora da važi:

Ovim je obezbeđeno da za svaki put  od početnog čvora do  važi:

gde je sa  označena dužina puta, a  je put  koji obuhvata čvor . 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  bude najkraći put od bilo kog čvora  do najbližeg ciljnog čvora  ):

A* je takođe optimalan za bilo koju heuristiku , š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  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 deﬁnisana 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 speciﬁč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  (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  konzistentna. Ukoliko funkcija  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  bude dopustiva (nije neophodno da bude konzistentna). 

Ukoliko se koristi nad stablima, da bi algoritam bio optimalan dovoljno je da funkcija  bude nenegativna i dopustiva.
Ukoliko funkcija  odgovara optimalnom putu, onda algoritam A* obrađuje sve čvorove za koje važi  i neke čvorove n za koje važi .

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  zadovoljava sledeći uslov: 

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

Varijante A* algoritma

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.}-

Графовски алгоритми
Комбинаторна оптимизација
Усмеривачки алгоритми
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 godine , kao unapređenje Dajkstrinog algoritma iz 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 nad čvorovima grafa , definisanu na sledeći način : gde je cena puta od polaznog čvora do čvora , a je procenjena ( heuristička ) cena najjeftinijeg puta od čvora do ciljnog čvora . Dok tragamo za najkraćim putem , uvek znamo tekuću minimalnu cenu od polaznog čvora do čvora ( tj. tekuću vrednost za ) , ali se vrednost može samo procenjivati . Da bi se obezbedila optimalnost A * pretrage , funkcija mora da bude konzistentna ( eng. consistent ) , tj. da za bilo koja dva susedna čvora i važi : gde je cena pridružena grani \ . U nekim specijalnim slučajevima dovoljno je da funkcija 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 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 za zadat čvor , veći mu je prioritet . U svakom koraku algoritma , čvor sa najnižom vrednošću funkcije se uklanja iz reda , ažuriraju se vrednosti i njegovih suseda , i oni se ubacuju u red . Algoritam se nastavlja sve dok vrednost ciljnog čvora ne bude najniža u redu ( ili dok ima čvorova u redu ) . Vrednost ciljnog čvora predstavlja dužinu najkraćeg puta , s obzirom na to da je vrednost 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 ) . Inicijalno je zatvorena lista prazna . Dodaj polazni čvor ( zajedno sa procenjenom cenom do ciljnog čvora , koja je određena funkcijom h u otvorenu listu čvorova koje je potrebno razmotriti . 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 ) . 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 ). function A*( start,goal ) closedset \ := the empty set / / The set of nodes already evaluated. openset \ := { start } / / The set of tentative nodes to be evaluated , initially containing the start node came_from \ := the empty map / / The map of navigated nodes. 5 g_score[ start ] \ := / / Cost from start along best known path . / / Estimated total cost from start to goal through y. f_score[ start ] \ := g_score[ start ] + heuristic_cost_estimate( start , goal ) while openset is not empty current \ := the node in openset having the lowest f_score [ ] value if current = goal return reconstruct_path( came_from , goal ) remove current from openset add current to closedset for each neighbor in neighbor_nodes( current ) tentative_g_score \ := g_score[ current ] + dist_between( current,neighbor ) if neighbor in closedset and tentative_g_score >= g_score[ neighbor ] continue if neighbor not in openset or tentative_g_score < g_score[ neighbor ] came_from[ neighbor ] \ := current g_score[ neighbor ] \ := tentative_g_score f_score[ neighbor ] \ := g_score[ neighbor ] + heuristic_cost_estimate( neighbor , goal ) if neighbor not in openset add neighbor to openset return failure function reconstruct_path( came_from , current_node ) if current_node in came_from p \ := reconstruct_path( came_from , came_from[ current_node ] ) return ( p + current_node ) else return current_node Primer 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 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 takođe mora biti monotona ( konzistentna ) da bi A * bio optimalan . Ovo znači da za svaki par susednih čvorova i , gde je dužina grane između njih , mora da važi : Ovim je obezbeđeno da za svaki put od početnog čvora do važi : gde je sa označena dužina puta , a je put koji obuhvata čvor \ . 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 bude najkraći put od bilo kog čvora do najbližeg ciljnog čvora ) : A * je takođe optimalan za bilo koju heuristiku , š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 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 =- 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 deﬁnisana 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 ) =- za svaki čvor -{ x }- . Ovakva funkcija -{ h }- je dopustiva i konzistentna i garantuje nalaženje optimalnog puta . Za -{ g =- , 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 speciﬁč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 cenaa svakom dijagonalnom cena ( 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 konzistentna . Ukoliko funkcija 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 bude dopustiva ( nije neophodno da bude konzistentna ) . Ukoliko se koristi nad stablima , da bi algoritam bio optimalan dovoljno je da funkcija bude nenegativna i dopustiva . Ukoliko funkcija odgovara optimalnom putu , onda algoritam A * obrađuje sve čvorove za koje važi i neke čvorove n za koje važi \ . 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 zadovoljava sledeći uslov : gde je optimalna heuristika , tj. funkcija koja vraća tačnu cenu puta od čvora x do ciljnog čvora . Drugim rečima , greška funkcije ne treba da raste brže od logaritma idealne heuristike . Varijante A * algoritma Literatura - { Veštačka inteligencija , profesor Predrag Janičić , MATF , Beograd 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 path finding and lighting project focused on performance , with demos . }- Графовски алгоритми Комбинаторна оптимизација Усмеривачки алгоритми