A*-algoritmen: heuristisk sökning för snabbaste vägen i grafer

A*-algoritmen: Lär dig heuristisk sökning för att hitta snabbaste vägen i grafer — effektiv punkt-till-punktruttsökning med smarta gissningar jämfört med Dijkstra.

Författare: Leandro Alegsa

07-02-2026 09:05

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.

Stegen

A* behöver först en lista över alla platser du kan åka till och sedan en lista över hur långt vägen är mellan dem. Därefter får du veta vilket som är det snabbaste sättet att ta sig från plats A till plats Z.

Som exempel kan vi säga att A är ansluten till platserna B och C, och B och C är båda anslutna till D och E. D och E är båda anslutna till Z. Det finns fyra sätt att gå från A till Z. Du kan gå A-B-D-Z, A-C-D-Z, A-B-E-Z eller A-C-E-Z. En dator som använder A* tittar först på hur svårt det är att ta sig från A till B och från A till C. Detta är "kostnaden" för dessa platser. Kostnaden för en plats innebär hur svårt det är att ta sig från A till den platsen. Efter att ha skrivit ner båda kostnaderna tittar datorn på hur svårt det är att ta sig från B till D och lägger till detta till B:s kostnad. Den skriver ner detta som D:s kostnad. Sedan tittar datorn på hur svårt det är att ta sig från C till D och lägger till detta till C:s kostnad. Detta är en annan kostnad för D, och om den är lägre än den som redan finns kommer den att ersätta den gamla kostnaden. Datorn vill bara veta den bästa vägen, så den ignorerar vägen med den högre kostnaden. Den kommer bara att komma ihåg en av A-B-D och A-C-D, beroende på vilken som är snabbast.

Datorn fortsätter och hittar det snabbaste sättet att ta sig till E. Slutligen går den från D till Z och hittar en kostnad, och från E till Z och hittar en kostnad. Den får fram en slutlig kostnad för Z, och detta är den minsta kostnad som den kan få fram. Nu vet datorn vilken väg som är snabbast, och den har svaret. Datorn kan göra en liknande serie steg, men med många många fler platser. Varje gång tittar den på den plats som ligger närmast A och lägger ihop kostnaderna för den platsens grannar.

Man kallar denna serie steg för Dijkstras algoritm. Dijkstras algoritm kan vara långsam, eftersom den tittar på många platser som kan gå åt fel håll från Z. Om du frågar datorn hur du ska ta dig från en stad till en närliggande stad kan Dijkstras algoritm hamna i en annan stat.

A* löser detta problem. Med A* kan du ge datorn en gissning om hur långt det kommer att vara från varje plats till slutet. Datorn kan använda gissningen för att ungefär säga hur långt det tar att ta sig från en viss plats till Z. I stället för att bara välja den plats som ligger närmast A att titta på, tittar den på den plats som förmodligen kommer att ha den lägsta totalsumman. Den får fram denna totalsumma genom att addera kostnaden till den förväntade sträckan kvar. På så sätt kan den bara titta i den riktning där det förmodligen kommer att bli bättre. Det är okej om gissningen inte är perfekt, men även en enkel dålig gissning kan få programmet att gå mycket snabbare. Om du försöker hitta en väg mellan två platser i den verkliga världen är en bra gissning bara avståndet mellan dem i en rak linje. Den verkliga vägen över vägar kommer att vara längre, men detta gör att programmet kan gissa sig fram, och det kommer inte att gå i fel riktning.

I litteraturen om matematik och datavetenskap är denna gissning ofta en funktion av platsen och kallas en heuristik. Varje plats är en vertex och varje väg mellan två platser är en kant. Detta är ord från grafteori.

Sök