A*-søgning
Dijkstras algoritme finder den korteste vej til et mål, men den søger i alle retninger på én gang, også væk fra målet. A*-søgning tilføjer én ekstra viden, et gæt på, hvor langt der stadig er til målet, og pludselig styrer søgningen lige mod det.
Idéen
Når du leder efter en rute på et kort, undersøger du ikke veje, der fører væk fra dit mål, lige så grundigt som veje, der fører hen mod det. A*-søgning gør det samme. Hver knude får en score: afstanden fra starten indtil nu, g, plus et gæt på den afstand, der er tilbage, h. Søgningen fortsætter altid fra knuden med den laveste score, så knuder, der ligger mod målet, kommer først.
Trin for trin
Giv starten afstand 0, og sæt den i en kø med scoren h(start). Gentag: tag knuden med den laveste score, og gør dens afstand endelig. Er det målet, så stop: følger du de huskede knuder tilbage, får du vejen. Ellers skal du for hver nabo, der ikke er endelig, beregne dens afstand via denne knude. Er den kortere end naboens afstand indtil nu, så sænk den, husk denne knude som vejen dertil, og giv naboen scoren for sin nye afstand plus sit gæt. Når to scorer er lige store, når man som regel målet hurtigere ved først at tage knuden med det mindste gæt.
Et eksempel
Tag en start A og et mål D. A–B er 2 lang og B–D 2, mens A–C er 1 og C–D 5. Gættene i luftlinje til D er 3 fra A, 2 fra B og 3 fra C. A starter med scoren 0 + 3 = 3. At tage A giver B scoren 2 + 2 = 4 og C scoren 1 + 3 = 4. Ved lige score tager A* B, knuden med det mindste gæt, og B giver D scoren 4 + 0 = 4. D har nu den laveste score med det mindste gæt, så den tages: den korteste vej er A → B → D med længde 4, og C, der fører den forkerte vej, bliver aldrig endelig. Dijkstras algoritme ville have gjort C endelig først, fordi den er den knude, der ligger nærmest A.
Et godt gæt
Gættet må aldrig være længere end den virkelige afstand til målet; et sådant gæt kaldes tilladeligt, og med det finder A* altid en korteste vej. Den lige linje er tilladelig, fordi ingen rute er kortere end en lige linje. Hvis gættet heller aldrig falder mere end en kants længde fra én knude til den næste, er det konsistent, og ingen endelig knude skal nogensinde ses på igen. Jo tættere gættet er på sandheden, jo færre knuder skal A* bruge. Et gæt på 0 er tilladeligt, men nytteløst: så bliver A* til Dijkstras algoritme. Et for stort gæt gør A* hurtigere, men kan overse den korteste vej.
Historie og anvendelser
Peter Hart, Nils Nilsson og Bertram Raphael fra Stanford Research Institute offentliggjorde A* i 1968, mens de arbejdede på Shakey, en af de første mobile robotter. Deres tidligere versioner hed A1 og A2; stjernen markerede den version, de beviste var optimal. I dag flytter A* figurer uden om forhindringer i computerspil, planlægger ruter og robotbevægelser og løser puslespil som 15-spillet, hvor gættet lægger sammen, hvor langt hver brik er fra sin plads.
Prøv det selv
Åbn appen, og tryk på Trin. Tallene på kanterne er deres længder, som her svarer til, hvor lange de er tegnet, og den stiplede linje viser gættet i luftlinje til målet. Køen under grafen viser knuderne efter score, laveste først. Når målet er endeligt, sammenligner statuslinjen, hvor mange knuder A* gjorde endelige, med hvor mange Dijkstras algoritme ville have brugt. Prøv et mål i et fjernt hjørne af en stor graf for at se den største forskel.
Ofte stillede spørgsmål
Hvad betyder stjernen i A*?
Hart, Nilsson og Raphael beskrev først algoritmer, de kaldte A1 og A2. A* ("A-stjerne") var den version, som de beviste finder en korteste vej og udvider færrest knuder blandt sammenlignelige algoritmer med samme gæt, når gættet er konsistent.
Hvad er tidskompleksiteten af A*?
I værste fald, med et nytteløst gæt, laver A* det samme arbejde som Dijkstras algoritme: O((V + E) log V) med en binær hob. Med et godt gæt gør den kun en brøkdel af knuderne endelige, og derfor er den hurtig i praksis.
Hvad gør en heuristik god til A*?
Den skal være hurtig at beregne, aldrig overvurdere den virkelige afstand og ligge så tæt på den som muligt. På et gitter, hvor man kun kan flytte sig op, ned, til venstre og til højre, er Manhattan-afstanden et almindeligt valg; på et kort afstanden i luftlinje.
Hvad hvis heuristikken overvurderer?
Så kan A* returnere en vej, der ikke er den korteste, fordi den kan blive færdig, før den har set på den bedre rute. Nogle programmer gør det med vilje (vægtet A*) for at bytte lidt vejkvalitet for meget fart.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv A*-søgning