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.