A* (A-stjerne): Heuristisk søgealgoritme til effektiv vejfindning
A*: Hurtig heuristisk søgealgoritme til effektiv vejfindning — find optimale ruter hurtigt ved hjælp af intelligente gæt. Perfekt til kort- og pathfinding-applikationer.
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.
Trinene
A* har først brug for en liste over alle de steder, du kan tage til, og derefter en liste over, hvor langt vejen er mellem hvert enkelt sted. Derefter vil den fortælle dig den hurtigste måde at komme fra sted A til sted Z på.
Som eksempel kan vi sige, at A er forbundet med B og C, og at B og C begge er forbundet med D og E. D og E er begge forbundet med Z. Der er 4 mulige måder at gå fra A til Z på. Du kan gå A-B-D-Z, A-C-D-Z, A-B-E-Z eller A-C-E-Z. En computer, der bruger A*, ser først på, hvor svært det er at komme fra A til B og fra A til C. Dette er "omkostningerne" for disse steder. Omkostningerne for et sted betyder, hvor svært det er at komme fra A til det pågældende sted. Når computeren har skrevet begge omkostninger ned, ser den på, hvor svært det er at komme fra B til D, og lægger dette til B's omkostninger. Den skriver dette ned som D's omkostninger. Derefter ser computeren på, hvor svært det er at komme fra C til D, og lægger dette til C's omkostninger. Dette er en anden omkostning for D, og hvis den er mindre end den, den allerede har, erstatter den den gamle. Computeren ønsker kun at kende den bedste vej, så den ignorerer den vej med de højere omkostninger. Den vil kun huske en af A-B-D og A-C-D, alt efter hvilken der er den hurtigste.
Computeren fortsætter og finder den hurtigste vej til E. Endelig går den fra D til Z og finder en omkostning, og fra E til Z og finder en omkostning. Den får en endelig omkostning for Z, og det er den mindste omkostning, den kan få. Nu ved computeren, hvilken vej der er den hurtigste, og den har svaret. Computeren kan udføre en lignende række trin, men med mange mange flere steder. Hver gang kigger den på det sted, der ligger tættest på A, og lægger omkostningerne til dette steds naboer sammen.
Ovenstående række af trin kaldes Dijkstras algoritme. Dijkstras algoritme kan være langsom, fordi den vil kigge på mange steder, der måske går den forkerte vej fra Z. Hvis du spørger computeren, hvordan du kommer fra en by til en nærliggende by, vil Dijkstras algoritme måske ende med at kigge i en anden stat.
A* løser dette problem. Med A* kan du give computeren et gæt på, hvor langt der vil være fra hvert sted til slutningen. Computeren kan bruge dette gæt til at fortælle, hvor langt det vil tage at komme fra et bestemt sted til Z. I stedet for blot at vælge det sted, der ligger tættest på A, vil den kigge på det sted, der sandsynligvis vil have den laveste totalsum. Den finder denne totalsum ved at lægge omkostningerne til den forventede resterende afstand. På denne måde kan den kun kigge i den retning, hvor det sandsynligvis bliver bedre. Det er okay, hvis gættet ikke er perfekt, men selv et simpelt dårligt gæt kan få programmet til at gå meget hurtigere. Hvis du forsøger at finde en vej mellem to steder i den virkelige verden, er et godt gæt blot afstanden mellem dem i en lige linje. Den virkelige vej over veje vil være længere, men dette lader programmet gætte den, og det vil ikke gå i den forkerte retning.
I matematisk eller datalogisk litteratur er dette gæt ofte en funktion af stedet, og det kaldes en heuristik. Hvert sted er et toppunkt, og hver vej mellem to steder er en kant. Dette er ord fra grafteori.
Søge