A* (A-stjärna)-algoritmen är en heuristisk sökalgoritm som används inom datavetenskap för att hitta den kortaste vägen mellan två noder i en graf. Det är en förlängning av Dijkstras algoritm, som hittar den kortaste vägen men inte använder heuristik.
Intuition
A* använder heuristik, information om problemdomänen som hjälper dess sökning. Dessa heuristiker kallas ofta tillåtna eller distansheuristiker, eftersom de aldrig överskattar den faktiska kostnaden för att nå målet. I många fall hittar A* optimala lösningar, även om det inte alltid är garanterat att det gör det.
Hur fungerar A*?
A* bibehåller två uppsättningar noder under sin sökning:ÖPPEN (frans) och STÄNGD
ÖPPEN innehåller alla noder som har genererats, men ännu inte helt utvärderade. Den ordnas efter F-poängen (diskuteras nedan) för dess medlemmar, med den lägsta F-poängen längst fram.
STÄNGD innehåller alla noder som har utvärderats fullt ut.
Algoritmen börjar med att placera startnoden i OPEN, medan målnoden initialt ligger i STÄNGD. Vid varje steg i algoritmen tar A* bort noden i OPEN med lägst F-poäng, expanderar den och lägger till alla dess grannar till OPEN. Om en granne inte redan är i ÖPPEN eller STÄNGD, beräknar A* en G-poäng (den faktiska kostnaden för att nå grannen från startnoden) och en H-poäng (en uppskattning av kostnaden för att nå målet från grannen) för det , och lägger till den i OPEN. Om en granne redan är i ÖPPEN jämförs den nya G-poängen med den nuvarande G-poängen, och om den nya G-poängen är lägre uppdateras grannen. Om en granne redan är i STÄNGD jämförs den nya G-poängen med den nuvarande G-poängen, och om den nya G-poängen är lägre flyttas grannen från STÄNGD till ÖPPEN och uppdateras.
Uppsägning
Algoritmen avslutas på ett av två sätt. För det första, om en granne till noden som expanderas är målet, returnerar algoritmen vägen till målet. För det andra, om OPEN blir tom, avslutas algoritmen utan framgång, vilket indikerar att det inte finns någon giltig väg från startnoden till målet.
Komplexitet
Den värsta tänkbara tidskomplexiteten för A*-algoritmen är exponentiell i storleken på grafen. Men i praktiken presterar A* bra på många problem, och den hittar ofta optimala lösningar inom rimlig tid.
