A* iskalni algoritem A-zvezda definicija in iskanje poti

A* je algoritem za iskanje najkrajših poti: niz korakov (algoritem), s katerimi računalnik izračuna, kako priti od točke A do točke B po grafu ali mreži. Če imate seznam lokacij (vozlišč) in težo povezav (robov) med njimi, A* hitro določi pot, ki minimizira skupne stroške. Povezan je z Dijkstrovim algoritmom, vendar A* uporablja oceno razdalje (heuristiko), da "pametno ugiba" in tako ne preiskuje nepotrebnih, počasnih poti. To je učinkovit algoritem, kadar želite najti posamezno pot med dvema krajema. Če želite poiskati vse pare najkrajših poti, so primernejši algoritmi, kot je Floyd–Warshall; A* prav tako ni primeren, če želite poiskati pot, ki obišče več krajev v neki optimalni zaporednosti (npr. problem potujočega prodajalca).

Kaj sestavlja A*

Glavne komponente A* so:

g(n): strošek najcenejše znane poti od začetka do vozlišča n.
h(n): heuristična ocena stroška od vozlišča n do cilja (napoved prihodnjega stroška).
f(n) = g(n) + h(n): ocena skupnega stroška poti skozi n — uporablja se za razvrščanje v vrsti (fronti).

Kako deluje (poenostavljen potek)

Začetno vozlišče dajte v odprto množico (open set) z g(start)=0 in f=start + h(start).
Dokler odprta množica ni prazna: izberite vozlišče z najmanjšo vrednostjo f (običajno prioritetna vrsta) in ga odstranite iz odprte množice.
Če je izbrano vozlišče cilj, rekonstruirajte pot z uporabo kazalcev na starše (parent) in končajte.
Za vsakega soseda trenutnega vozlišča izračunajte možen nov g-kos (g_current + teža roba). Če je ta boljši od prej znanega g(sosed), posodobite g, izračunajte novo f in nastavite starša; sosed dodajte v odprto množico (če še ni v njej).
Ko obdelate vozlišče, ga premaknite v zaprto množico (closed set), da ga ne obdelujete znova (ali uporabite kontrolni mehanizem za zaznavanje že obdelanih z nižjim stroškom).

Heuristika in optimalnost

Če je heuristika admisibilna (nikoli ne preceni dejanskega stroška do cilja), potem je A* optimalen — zagotovi najcenejšo pot.
Če je heuristika konsistentna (monotona), potem je iskanje učinkovitejše in ni potrebe po ponovnem obdelovanju vozlišč; konsistentnost običajno pomeni: h(n) ≤ cost(n,m) + h(m) za vsak rob (n,m).
Primeri heuristik:
- Evklidska razdalja (za neomejeno gibanje v ravnini).
- Manhattanska razdalja (za mreže z gibanjem v štirih smereh).
- Chebyshevova razdalja (za dovoljena diagonalna gibanja z enakimi stroški).
- H(n)=0 — če heuristika vedno vrača 0, A* postane Dijkstra.

Lastnosti in omejitve

Popolnost: A* je popoln, če obstaja končna pot in če so vozlišča razširljiva; s primerno implementacijo vrne pot, če obstaja.
Optimalnost: zagotovljena z admisibilno (in za praktične izboljšave še konsistentno) heuristiko.
Časovna in pomnilniška zahtevnost: v najslabšem primeru eksponentna glede števila raziskanih vozlišč; pomnilnik je predvsem problem, saj A* hrani odprto množico (celotna meja iskanja). Kakovost heuristike močno vpliva na hitrost.
Uporaba: igre (AI za premikanje enot), navigacija (GPS), načrtovanje poti za robote, simulacije v mrežah in logistika.
Neprimerna uporaba: za iskanje vseh najkrajših poti med vsemi pari vozlišč, ali za NP‑težke probleme, kot je optimalna pot, ki obišče mnogo mest (npr. TSP).

Praktični nasveti za implementacijo

Uporabite prioritetno vrsto (binary heap, fibonacci heap ali podobno) za odprto množico, kjer je ključ f(n). Za hitro posodabljanje ključev je lahko koristna podpora za "decrease-key" ali dodatna tabela s položaji.
Shranite mapo staršev (parent) za rekonstruiranje poti, ko dosežete cilj.
Pri velikih mrežah razmislite o varčevanju z pomnilnikom ali o iterativnih različicah, npr. IDA* (iterative deepening A*), ali o prilagoditvah za dinamične okolje (D* in njene variante).
Za hitrejše iskanje v več primerih na istem zemljevidu lahko predračunate (preprocesirate) strukture (npr. graf razdeljen na cone, hierarhično iskanje) — to je pogosto bolj učinkovito kot večkratni A* od začetka do cilja.
Pazite na ravnanje s plavajočimi vrednostmi pri primerjavi heuristik in stroškov; pri mrežnih igrah je pogosto koristno dodati tie-breaking (npr. prioritetno manjši h pri enakih f), da dobite bolj "naravne" poti.

Zaključek

A* je močan in prilagodljiv algoritem za iskanje najcenejše poti med dvema točkama, kadar imate na voljo dobro heuristiko. Zaradi svoje kombinacije dejanskega odhodnega stroška g in ocene preostanka h pogosto poišče cilj hitreje kot Dijkstra, ne da bi pri tem izgubil optimalnost (če je heuristika ustrezna). V izbiri algoritma pa upoštevajte velikost problema, omejitve pomnilnika ter ali potrebujete eno pot ali več parov poti hkrati.

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.