Back

ⓘ A* algoritam




                                     

ⓘ A* algoritam

Algoritam A* za odredivanje najkraćeg puta izmedu 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 unapredenje Dajkstrinog algoritma iz 1959. godine.

                                     

1. 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 obradeni svi njihovi susedi i zatvorenih čvorova - čvorova koji su posećeni i kojima su obradeni 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 {\displaystyle f} nad čvorovima grafa, definisanu na sledeći način: f x = g x + h x {\displaystyle fx=gx+hx} gde je g x {\displaystyle gx} cena puta od polaznog čvora do čvora x {\displaystyle x}, a h x {\displaystyle hx} je procenjena heuristička cena najjeftinijeg puta od čvora x {\displaystyle x} do ciljnog čvora. Dok tragamo za najkraćim putem, uvek znamo tekuću minimalnu cenu od polaznog čvora do čvora x {\displaystyle x} tj. tekuću vrednost za g x {\displaystyle gx}), ali se vrednost h x {\displaystyle hx} može samo procenjivati. Da bi se obezbedila optimalnost A* pretrage, funkcija h {\displaystyle h} mora da bude konzistentna eng. consistent, tj. da za bilo koja dva susedna čvora x {\displaystyle x} i y {\displaystyle y} važi: h x