A* er et sæt trin (en algoritme), som computere kan bruge til at finde ud af, hvordan de hurtigt kan komme et sted hen mellem to steder. Hvis du har en liste over steder, og hvis du ved, hvor svært det er at komme direkte fra det ene sted til det andet, kan du ved hjælp af A* hurtigt finde frem til den hurtigste vej. Den er beslægtet med Dijkstras algoritme, men den foretager intelligente gæt, så den ikke bruger så lang tid på at prøve langsomme veje. Det er en god række trin, hvis du kun ønsker vejen mellem to steder. Hvis du skal spørge efter mange stier fra det samme kort, er der hurtigere måder, som finder alle svarene på én gang, som Floyd–Warshall-algoritmen. A* vil ikke fungere, hvis du vil besøge flere steder på én tur (det rejsende sælgerproblem).

Hvordan A* virker — grundidé

A* leder i rummet af mulige noder (steder) fra en startnode til en målnode. For hver node n beregner algoritmen to tal:

  • g(n): den kendte omkostning fra start til n (den vej, algoritmen allerede har fundet).
  • h(n): en heuristisk estimering af omkostningen fra n til målet (et intelligent gæt).

Algoritmen vælger altid den node med lavest f(n) = g(n) + h(n) og udvider den (ser på dens naboer). På den måde kombinerer A* både hvad der allerede er brugt (g) og hvor langt der sandsynligvis er tilbage (h).

Vigtige egenskaber ved heuristikken

  • Admissibel heuristik: Hvis h(n) aldrig overvurderer den sande billigste omkostning fra n til målet, vil A* finde en optimal (korteste) sti. Eksempel: Manhattan-afstand i et gitter uden diagonal bevægelse.
  • Konsistent (monoton) heuristik: Hvis h(n) ≤ cost(n, m) + h(m) for alle noder n og deres naboer m, så vil A* ikke skulle genåbne noder, og algoritmen bliver mere effektiv i praksis. Konsistens indebærer ofte admissibilitet.

Pseudokode i korte træk

Fremgangsmåden kan opsummeres sådan:

 Åben = {start} Lukket = {} g[start] = 0 h[start] = heuristik(start) f[start] = g[start] + h[start]  mens Åben ikke er tom:   vælg node n i Åben med mindste f(n)   hvis n er mål: returner sti ved at følge forældrepege   flyt n fra Åben til Lukket   for hver nabo m af n:     hvis m i Lukket: fortsæt     tent_g = g[n] + omkostning(n,m)     hvis m ikke i Åben eller tent_g < g[m]:       forælder[m] = n       g[m] = tent_g       h[m] = heuristik(m)       f[m] = g[m] + h[m]       hvis m ikke i Åben: indsæt m i Åben

Kompleksitet og begrænsninger

  • Værste tilfælde: tidskompleksiteten kan være eksponentiel i antallet af noder, især hvis heuristikken er dårlig (f.eks. h ≈ 0 giver Dijkstra's algoritme).
  • Hukommelse: A* gemmer typisk mange noder i hukommelsen (Åben og Lukket), hvilket kan være begrænsende for store søgeområder.
  • Optimalt resultat: Hvis heuristikken er admissibel (og kan antages ikke-negativ), garanterer A* at finde den korteste sti.
  • Ikke egnet til TSP: A* finder en enkelt korteste sti mellem to punkter og hjælper ikke med at løse kombinationsproblemer som det rejsende sælgerproblem effektivt.

Typiske heuristikker og eksempler

  • 2D gitter uden diagonaler: Manhattan distance (|dx| + |dy|).
  • 2D gitter med diagonaler: Euclidisk afstand eller en vægtet variant; for rigtigt gitterbrug kan man bruge 8-retningers afstand med passende diagonalomkostning (√2).
  • Vægtningsstrategi: Weighted A* bruger f = g + w·h (w > 1) for at få hurtigere men potentielt suboptimale løsninger.

Varianter og optimeringer

  • IDA* (Iterative Deepening A*): reducerer hukommelsesforbruget ved at udføre gentagne dybdebegrænsede søgninger med stigende f-grænser.
  • Bidirectional A*: søger fra både start og mål samtidig for at reducere søgeområdet.
  • Jump Point Search: en optimering til regelmæssige gitter, der springer over mange noder og øger hastigheden i games og ruteplanlægning.
  • Theta*: forsøger at finde mere direkte (line-of-sight) stier i gittermiljøer.

Anvendelsesområder

  • Kort og navigation (GPS-ruteplanlægning).
  • Robotteknik og motion-planning.
  • Spiludvikling (NPC-vejfinding, AI-bevægelse).
  • Netværksrutning og logistik, når enkeltparruter skal optimeres.

Praktiske tips

  • Vælg en heuristik der er så tæt på den sande omkostning som mulig, uden at overvurdere (admissibel), for at gøre søgningen hurtigere.
  • For store søgeområder: overvej varianter som IDA* eller anvend rumlig nedbrydning (hierarkier, navmeshes) for at reducere kompleksitet.
  • Til spil: kompromis mellem optimalitet og hastighed er ofte acceptabelt — vægtet A* eller caching kan være praktisk.
  • Når kanter kan have negative omkostninger, virker A* ikke korrekt; A* forudsætter normalt ikke-negative kantomkostninger.

Samlet set er A* en fleksibel og kraftfuld søgealgoritme, som med den rette heuristik kan finde optimale ruter meget effektivt, men man skal være opmærksom på hukommelseskrav og valg af heuristik i forhold til den konkrete anvendelse.