A* (A-stjerne) algoritmen er en heuristisk søgealgoritme, der bruges i datalogi til at finde den korteste vej mellem to knudepunkter i en graf. Det er en forlængelse af Dijkstra's algoritme, som finder den korteste vej, men ikke bruger heuristik.

Intuition

A* bruger heuristik, information om problemdomænet, der hjælper med at guide dets søgning. Disse heuristika kaldes ofte tilladelige eller afstandsheuristika, fordi de aldrig overvurderer de faktiske omkostninger for at nå målet. I mange tilfælde finder A* optimale løsninger, selvom det ikke altid er garanteret at gøre det.

Hvordan fungerer A*?

A* bevarer to sæt noder under sin søgning:ÅBEN (Fringe) og LUKKET

ÅBN indeholder alle noder, der er blevet genereret, men endnu ikke fuldt ud evalueret. Det er sorteret efter F-score (omtalt nedenfor) for dets medlemmer, med den laveste F-score forrest.

LUKKET indeholder alle noder, der er blevet fuldt evalueret.

Algoritmen starter med at placere startknudepunktet i ÅBEN, mens målknudepunktet i første omgang ligger i LUKKET. Ved hvert trin i algoritmen fjerner A* noden i OPEN med den laveste F-score, udvider den og tilføjer alle dens naboer til OPEN. Hvis en nabo ikke allerede er i ÅBEN eller LUKKET, beregner A* en G-score (de faktiske omkostninger for at nå naboen fra startknudepunktet) og en H-score (et estimat af omkostningerne for at nå målet fra naboen) for det , og tilføjer den til OPEN. Hvis en nabo allerede er i ÅBEN, sammenlignes den nye G-score med den nuværende G-score, og hvis den nye G-score er lavere, opdateres naboen. Hvis en nabo allerede er i LUKKET, sammenlignes den nye G-score med den nuværende G-score, og hvis den nye G-score er lavere, flyttes naboen fra LUKKET til ÅBEN og opdateres.

Opsigelse

Algoritmen afsluttes på en af ​​to måder. For det første, hvis en nabo til den node, der udvides, er målet, returnerer algoritmen stien til målet. For det andet, hvis OPEN bliver tom, afsluttes algoritmen uden held, hvilket indikerer, at der ikke er nogen gyldig sti fra startknudepunktet til målet.

Kompleksitet

Den værst tænkelige tidskompleksitet af A*-algoritmen er eksponentiel i størrelsen af ​​grafen. Men i praksis klarer A* sig godt på mange problemer, og den finder ofte optimale løsninger inden for rimelig tid.