A* (A-stjerne)-algoritmen er en heuristisk søkealgoritme som brukes i informatikk for å finne den korteste veien mellom to noder i en graf. Det er en utvidelse av Dijkstras algoritme, som finner den korteste veien, men ikke bruker heuristikk.

Intuisjon

A* bruker heuristikk, informasjon om problemdomenet som hjelper søket. Disse heuristikkene kalles ofte tillatte eller avstandsheuristikk, fordi de aldri overvurderer den faktiske kostnaden for å nå målet. I mange tilfeller finner A* optimale løsninger, selv om det ikke alltid er garantert å gjøre det.

Hvordan fungerer A*?

A* opprettholder to sett med noder under søket:ÅPEN (Fringe) og LUKKET

ÅPEN inneholder alle noder som er generert, men som ennå ikke er fullstendig evaluert. Den er sortert etter F-poengsum (diskutert nedenfor) til medlemmene, med laveste F-poengsum foran.

STENGT inneholder alle noder som er fullstendig evaluert.

Algoritmen starter med å plassere startnoden i ÅPEN, mens målnoden i utgangspunktet ligger i STENGT. Ved hvert trinn i algoritmen fjerner A* noden i OPEN med lavest F-poengsum, utvider den og legger til alle naboene til OPEN. Hvis en nabo ikke allerede er i ÅPEN eller STENGT, beregner A* en G-poengsum (den faktiske kostnaden for å nå naboen fra startnoden) og en H-score (et estimat av kostnaden for å nå målet fra naboen) for det , og legger den til OPEN. Hvis en nabo allerede er i ÅPEN, sammenlignes den nye G-skåren med den nåværende G-skåren, og hvis den nye G-skåren er lavere, oppdateres naboen. Hvis en nabo allerede er i STENGT, sammenlignes den nye G-skåren med den nåværende G-skåren, og hvis den nye G-skåren er lavere, flyttes naboen fra STENGT til ÅPEN og oppdateres.

Oppsigelse

Algoritmen avsluttes på en av to måter. For det første, hvis en nabo til noden som utvides er målet, returnerer algoritmen banen til målet. For det andre, hvis OPEN blir tom, avsluttes algoritmen uten hell, noe som indikerer at det ikke er noen gyldig vei fra startnoden til målet.

Kompleksitet

Den verste tidskompleksiteten til A*-algoritmen er eksponentiell i størrelsen på grafen. Men i praksis klarer A* seg godt på mange problemer, og den finner ofte optimale løsninger i løpet av rimelig tid.