Iskalni algoritem A*
A* je niz korakov (algoritem), s katerimi lahko računalniki ugotovijo, kako hitro priti nekam med dvema krajema. Če imate seznam lokacij in kako težko je priti od ene naravnost do druge, lahko z uporabo A* hitro določite najhitrejšo pot. Povezan je z Dijkstrovim algoritmom, vendar pametno ugiba, tako da ne porablja toliko časa za iskanje počasnih poti. To je dober niz korakov, če želite le pot med dvema krajema. Če želite poiskati več poti z istega zemljevida, obstajajo hitrejši načini, ki najdejo vse odgovore naenkrat, kot je algoritem Floyd-Warshall. A* ne bo deloval, če želite na eni poti obiskati več krajev (problem potujočega prodajalca).
Koraki
A* najprej potrebuje seznam vseh krajev, kamor lahko greste, nato pa še seznam, kako daleč je pot med posameznimi kraji. Nato vam bo povedal najhitrejšo pot od kraja A do kraja Z.
Za primer bomo rekli, da je A povezan z mestoma B in C, B in C pa sta povezana z D in E. D in E sta povezana z Z. Iz A v Z lahko greste na štiri načine: A-B-D-Z, A-C-D-Z, A-B-E-Z ali A-C-E-Z. Računalnik, ki uporablja A*, najprej pogleda, kako težko je priti iz A v B in iz A v C. To so "stroški" za ta mesta. Stroški kraja pomenijo, kako težko je priti od kraja A do tega kraja. Ko zapiše oba stroška, računalnik pogleda, kako težko je priti od B do D, in to prišteje stroškom B. To zapiše kot strošek D. Nato računalnik pogleda, kako težko je priti od C do D, in to prišteje k stroškom C. To je drugačen strošek za D, in če je manjši od tistega, ki ga že ima, bo zamenjal starega. Računalnik želi poznati le najboljšo pot, zato pot z višjimi stroški zanemari. Zapomnil si bo le eno od poti A-B-D in A-C-D, odvisno od tega, katera je hitrejša.
Računalnik nadaljuje in poišče najhitrejšo pot do točke E. Nazadnje gre od točke D do točke Z in ugotovi stroške, od točke E do točke Z pa ugotovi stroške. Dobi končni strošek za Z in to je najmanjši strošek, ki ga lahko dobi. Zdaj računalnik ve, katera pot je najhitrejša, in ima odgovor. Računalnik lahko opravi podoben niz korakov, vendar z veliko več kraji. Vsakič bo pogledal mesto, ki je najbližje mestu A, in seštel stroške sosednjih mest tega mesta.
Zgornji niz korakov imenujemo Dijkstrov algoritem. Dijkstrov algoritem je lahko počasen, ker bo pogledal na veliko krajev, ki bi lahko šli v napačno smer od točke Z. Če bi računalnik vprašali, kako priti iz enega mesta v bližnje, bi lahko Dijkstrov algoritem na koncu iskal v drugi državi.
A* to težavo odpravlja. A* omogoča, da računalniku napoveste, kako daleč bo od vsakega kraja do konca. Računalnik lahko na podlagi te domneve približno ugotovi, kako daleč bo treba priti od določenega kraja do kraja Z. Namesto da bi izbral kraj, ki je najbližji kraju A, bo pogledal kraj, ki bo verjetno imel najnižjo skupno vsoto. To vsoto najde tako, da stroške prišteje k pričakovani preostali razdalji. Na ta način lahko pogleda samo v smeri, kjer se bodo stvari verjetno izboljšale. Nič hudega, če uganka ni popolna, vendar lahko že preprosta slaba uganka povzroči, da bo program deloval veliko hitreje. Če poskušate najti pot med dvema krajema v resničnem svetu, je dobra domneva samo razdalja med njima v ravni črti. Resnična pot po cestah bo daljša, vendar tako lahko program ugiba in ne bo šel v napačno smer.
V matematični ali računalniški literaturi je ta domneva pogosto funkcija kraja in se imenuje hevristika. Vsak kraj je vrh, vsaka pot med dvema krajema pa je rob. To so besede iz teorije grafov.
