A*-søgningsalgoritme
A* er et sæt trin (en algoritme), som computere kan bruge til at finde ud af, hvordan de hurtigt kan komme et sted hen mellem to steder. Hvis du har en liste over steder, og hvis du ved, hvor svært det er at komme direkte fra det ene sted til det andet, kan du ved hjælp af A* hurtigt finde frem til den hurtigste vej. Den er beslægtet med Dijkstras algoritme, men den foretager intelligente gæt, så den ikke bruger så lang tid på at prøve langsomme veje. Det er en god række trin, hvis du kun ønsker vejen mellem to steder. Hvis du skal spørge efter mange stier fra det samme kort, er der hurtigere måder, som finder alle svarene på én gang, som Floyd-Warshall-algoritmen. A* vil ikke fungere, hvis du vil besøge flere steder på én tur (det rejsende sælgerproblem).
Trinene
A* har først brug for en liste over alle de steder, du kan tage til, og derefter en liste over, hvor langt vejen er mellem hvert enkelt sted. Derefter vil den fortælle dig den hurtigste måde at komme fra sted A til sted Z på.
Som eksempel kan vi sige, at A er forbundet med B og C, og at B og C begge er forbundet med D og E. D og E er begge forbundet med Z. Der er 4 mulige måder at gå fra A til Z på. Du kan gå A-B-D-Z, A-C-D-Z, A-B-E-Z eller A-C-E-Z. En computer, der bruger A*, ser først på, hvor svært det er at komme fra A til B og fra A til C. Dette er "omkostningerne" for disse steder. Omkostningerne for et sted betyder, hvor svært det er at komme fra A til det pågældende sted. Når computeren har skrevet begge omkostninger ned, ser den på, hvor svært det er at komme fra B til D, og lægger dette til B's omkostninger. Den skriver dette ned som D's omkostninger. Derefter ser computeren på, hvor svært det er at komme fra C til D, og lægger dette til C's omkostninger. Dette er en anden omkostning for D, og hvis den er mindre end den, den allerede har, erstatter den den gamle. Computeren ønsker kun at kende den bedste vej, så den ignorerer den vej med de højere omkostninger. Den vil kun huske en af A-B-D og A-C-D, alt efter hvilken der er den hurtigste.
Computeren fortsætter og finder den hurtigste vej til E. Endelig går den fra D til Z og finder en omkostning, og fra E til Z og finder en omkostning. Den får en endelig omkostning for Z, og det er den mindste omkostning, den kan få. Nu ved computeren, hvilken vej der er den hurtigste, og den har svaret. Computeren kan udføre en lignende række trin, men med mange mange flere steder. Hver gang kigger den på det sted, der ligger tættest på A, og lægger omkostningerne til dette steds naboer sammen.
Ovenstående række af trin kaldes Dijkstras algoritme. Dijkstras algoritme kan være langsom, fordi den vil kigge på mange steder, der måske går den forkerte vej fra Z. Hvis du spørger computeren, hvordan du kommer fra en by til en nærliggende by, vil Dijkstras algoritme måske ende med at kigge i en anden stat.
A* løser dette problem. Med A* kan du give computeren et gæt på, hvor langt der vil være fra hvert sted til slutningen. Computeren kan bruge dette gæt til at fortælle, hvor langt det vil tage at komme fra et bestemt sted til Z. I stedet for blot at vælge det sted, der ligger tættest på A, vil den kigge på det sted, der sandsynligvis vil have den laveste totalsum. Den finder denne totalsum ved at lægge omkostningerne til den forventede resterende afstand. På denne måde kan den kun kigge i den retning, hvor det sandsynligvis bliver bedre. Det er okay, hvis gættet ikke er perfekt, men selv et simpelt dårligt gæt kan få programmet til at gå meget hurtigere. Hvis du forsøger at finde en vej mellem to steder i den virkelige verden, er et godt gæt blot afstanden mellem dem i en lige linje. Den virkelige vej over veje vil være længere, men dette lader programmet gætte den, og det vil ikke gå i den forkerte retning.
I matematisk eller datalogisk litteratur er dette gæt ofte en funktion af stedet, og det kaldes en heuristik. Hvert sted er et toppunkt, og hver vej mellem to steder er en kant. Dette er ord fra grafteori.
