A* är en uppsättning steg (en algoritm) som datorer kan använda för att räkna ut hur man snabbt kan ta sig mellan två platser. Om du har en lista över platser och hur svårt det är att ta sig från den ena platsen direkt till den andra, kan du med hjälp av A* snabbt få reda på den snabbaste vägen. Den är besläktad med Dijkstras algoritm, men gör smarta gissningar så att den inte spenderar lika lång tid på att försöka hitta långsamma vägar. Det är en bra serie steg om du bara vill ha vägen mellan två platser. Om du ska fråga efter många vägar från samma karta finns det snabbare metoder som hittar alla svaren på en gång, till exempel Floyd-Warshall-algoritmen. A* fungerar inte om du vill besöka flera platser på en och samma resa (Travelling salesman-problemet).

Hur A* fungerar (kortfattat)

A* söker i en graf från en startnod till ett mål genom att kombinera:

  • g(n) — den hittills kända kostnaden från start till noden n, och
  • h(n) — en heuristisk uppskattning av kostnaden från n till målet.
Algoritmen prioriterar noder efter värdet f(n) = g(n) + h(n), det vill säga en kombination av redan uppnådd kostnad och en förväntad återstående kostnad. Praktiskt implementeras detta med en prioritetskö (open set) och en lista över redan besökta noder (closed set).

Heuristik: admissibel och konsistent

Heuristiken h(n) är avgörande för A*s effektivitet och korrekthet. Två vanliga egenskaper är:

  • Admissibel: h(n) underskattar aldrig den verkliga lägsta kostnaden från n till målet. Om h är admissibel garanterar A* att hitta en optimal (kostnadsminimerande) väg.
  • Konsistent (monoton): för varje kant mellan n och en efterföljare n' gäller h(n) ≤ cost(n,n') + h(n'). Konsistens gör att värdet f(n) aldrig minskar längs en sökväg och förenklar implementationen eftersom noder behöver inte upprepade gånger flyttas i kön.
Exempel på heuristik på ett rutnät: Manhattan-avståndet (för rörelse i 4 riktningar) eller Euclidean-avståndet (för rörelse i fritt plan). Båda kan vara admissibla beroende på hur kanter kostas.

Garantier och komplexitet

Om heuristiken är admissibel (och grafen har icke-negativa kantvikter) garanterar A* optimalitet — den hittar en kortaste väg. Om h(n)=0 för alla n reduceras A* till Dijkstras algoritm. Komplexiteten beror starkt på kvalitén hos h(n): i värsta fall (t.ex. trivials heuristik) söker A* i hela sökutrymmet, vilket kan bli exponentiellt i problemstorleken. Med en bra heuristik kan A* däremot vara mycket snabbare i praktiken.

Praktiska implementeringstips

  • Använd en effektiv prioritetskö (t.ex. binärt heap eller en specialiserad heap) för open set.
  • Spara för varje nod dess g-värde och pekare till föregångaren för att kunna återskapa vägen när målet nås.
  • Tänk på hur du bryter lika f-värden — en bra tie-breaking-policy (t.ex. preferera större g) kan minska onödig expansion.
  • Om minnet är begränsat finns varianter som IDA* (iterative deepening A*) och SMA* (Simplified Memory-bounded A*) som använder mindre minne.
  • A* fungerar inte med negativa kantvikter (samma begränsning som Dijkstra).

Varianter och vidareutvecklingar

Det finns flera varianter av A* för olika behov:

  • Weighted A* — multiplicerar heuristiken med en faktor >1 för snabbare men icke-optimal sökning.
  • Bidirectional A* — söker från både start och mål för att snabba upp sökningen i stora grafer.
  • IDA* — iterativt djupbegränsad sökning med heuristik, minnesvänligare.

Tillämpningar

A* används ofta inom:

  • Spelutveckling för karaktärers och NPC:ers pathfinding på kartor.
  • Robotik och ruttplanering (t.ex. autonoma fordon).
  • Karttjänster och navigation där snabb beräkning av en väg behövs.
  • Sökproblem i artificiell intelligens där man söker en sekvens av tillstånd (med en lämplig heuristik).

Enkelt exempel (rutnät)

Anta ett 2D-rutnät där varje steg horisontellt/vertikalt kostar 1. Start i (0,0), mål i (4,3). Manhattan-heurstiken h(n) = |x_goal - x_n| + |y_goal - y_n| är admissibel här. A* kommer att expandera noder som verkar lovande enligt f = g + h och snabbt hitta optimal väg utan att undersöka hela rutnätet.

Kort pseudokod

 open = priority queue med startnoden (f = h(start)) g[start] = 0 while open inte tom:     n = pop nod med lägst f     om n är mål: återskapa och returnera väg     flytta n till closed     för varje granne n' till n:         tent_g = g[n] + cost(n, n')         om n' i closed och tent_g >= g[n']: fortsätt         om n' inte i open eller tent_g < g[n']:             föregångare[n'] = n             g[n'] = tent_g             f[n'] = g[n'] + h(n')             om n' inte i open: lägg till n' i open

Sammanfattning: A* kombinerar känd kostnad och heuristisk uppskattning för att hitta effektiva och ofta snabba vägar i grafer. Valet av heuristik avgör både hastighet och om resultatet blir optimalt.