et trin op fra Dijkstras algoritme er en* (læs: “en stjerne”). Med hensyn til stifinding vil Dijkstras algoritme prøve hver sti og hvert toppunkt for at finde den korteste sti mellem dens udgangspunkt og destination, mens A* har en ekstra attribut, en heuristisk, der skal give den mulighed for at finde den korteste sti uden at skulle kontrollere hver sti og toppunkt. Hver algoritme har sine brugssager, men generelt kan både Dijkstra og A* finde den korteste vej, men A* vil gøre det hurtigere.

Jeg vil anbefale at vide lidt om Dijkstras algoritme, før jeg går ind i denne artikel, da der er mange sammenligningspunkter. Eller endnu bedre, læs min sidste artikel om emnet! https://medium.com/swlh/pathfinding-dijkstras-algorithm-65e71c346629

jeg bliver nødt til at oprette et par ting til mine eksempler, plus give en definition af, hvad en heuristisk er. For at starte, lad mig vise dig den type graf, jeg vil bruge til mine eksempler.

Dette er lidt abstrakt, men jeg vil bruge et ternet bord som min graf, og jeg vil tillade bevægelse mellem dens firkanter. Hvis jeg overlejrer den tilsvarende graf med hjørner og kanter, skal den se sådan ud.

lad os tage midterfeltet/toppunktet, E, for eksempel. Det har otte tilstødende hjørner, så vi kan bevæge os op, ned, venstre, højre og i alle diagonale kombinationer af hver. Og det er virkelig alt, hvad jeg forsøgte at oprette her: jeg skal bruge et tavle, og jeg vil tillade bevægelse i otte retninger. Lidt langvarig, men lad os nu begynde at se på bevægelse og omkostningerne ved bevægelse.

Når jeg starter simpelt, vil jeg sige, at bevægelse op, ned, venstre og højre har en bevægelsesomkostning på 1. Bestyrelsen får travlt, så jeg vil udtrække grafen, og tilføje, at bevægelse omkostninger på som kant vægte.

Hvis disse vægte er afstande, og hvis forholdene og naboerne er lagt ud som dette, kan geometri fortælle os om omkostningerne ved diagonale bevægelser. Ved hjælp af Pythagoras teori skal vi få √(12 + 12) = √2, hvilket er omtrent 1.41421356237 … hvilket ikke er et meget flot nummer at arbejde med. Så jeg stjæler en ide (og citerer mine kilder!), og multiplicere og runde omkostningerne ned. For begge typer bevægelser vil jeg multiplicere dem med ti og derefter afkorte deres decimaler. Dette vil give os endelige omkostninger på 10 for op, ned, venstre og højre bevægelser og 14 for diagonale bevægelser.

heuristik

Jeg har lyst til, at disse er vanskelige for mig at definere, så jeg starter med:

inden for datalogi, kunstig intelligens og matematisk optimering er en heuristisk (fra græsk Kris “jeg finder, opdager”) en teknik designet til at løse et problem hurtigere, når klassiske metoder er for langsomme, eller til at finde en omtrentlig løsning, når klassiske metoder ikke finder nogen nøjagtig løsning. Dette opnås ved at handle optimalitet, fuldstændighed, nøjagtighed eller præcision for hastighed. På en måde kan det betragtes som en genvej.

er det nyttigt? Forstår du det? Fordi jeg ikke forstår det. Jeg mener, jeg forstår det, og det er en nøjagtig beskrivelse, men hvis dette var det første, du nogensinde havde hørt om en heuristisk, er jeg ikke sikker på, at du ville få det fulde billede af, hvad heuristik er fra dette. Måske hvis jeg bare fortæller dig om en*’s pathfinding heuristic, får du en bedre forståelse.

Med Dijkstras algoritme var fokus på en værdi: den korteste afstand fra startindekset. Hvilket, når du tænker over det, er lidt underligt. Du har denne algoritme, der prøver at finde nye, kortere stier til en destination, men dens fokus er altid på, hvor den startede. Forestil dig, at nogen går ud for dagligvarer, men går baglæns hele vejen, forsøger at holde øje med deres hjem, indtil de kom til butikken. I det virkelige liv, dette ville sandsynligvis ikke fungere, men måske hvis du gav dem tid til at gå over hele byen, det kan til sidst fungere.

går ud af denne dumme analogi, A* er forskellig fra Dijkstra ‘ s, fordi det tyder på at dreje rundt og gå fremad. A*, som Dijkstra ‘ s, holder også styr på, hvor langt hjemmefra det er, men dets unikke funktion er, at det også holder styr på, hvor langt det er fra destinationen. Når Dijkstra tager sit næste skridt, vil Dijkstra se på, hvilken sti der i øjeblikket er den korteste, men A* går et skridt videre og overvejer også, om dette trin bevæger det tættere på sit mål. Mere enkelt, A* har et groft skøn over sin resterende afstand til sit mål, og når dette skøn kommer tættere på nul, ved det, at det bevæger sig i den rigtige retning. Dette er den heuristiske vi vil bruge i vores eksempler.

Stepping gennem algoritmen

Dette vil være et ret simpelt eksempel, men det skal vise dig den grundlæggende strømning og gentagelse af algoritmen. Jeg vil sørge for at give links i mine referencer til andre, mere komplicerede eksempler, men dette bør være en god primer for dem. Jeg bruger en opsætning svarende til, hvordan jeg demonstrerede Dijkstra ‘ s.

en yderligere forskel mellem Dijkstra ‘s og A* er, at Dijkstra’ s får at starte looping med det samme, men A* skal lave en lille opsætning til startspidsen. Så lad os gøre det nu, og få lidt af en ide om, hvordan bordet skal fungere.

først tilføjer vi A til det åbne sæt. For det andet finder vi ud af A ‘ S afstand fra starten. Naturligvis er afstanden fra A til a nul, så det vil blive tilføjet til bordet, og jeg får det til at være nummeret i øverste venstre hjørne af A ‘ S firkant. For det tredje bestemmer vi den heuristiske afstand. Vi kan gøre dette på en række måder, alt hvad der er vigtigt er, at vi måler denne afstand på samme måde for hver firkant. Jeg skal bruge en” som kragen flyver ” afstand for alle de heuristiske afstande, hvilket betyder, at jeg kan gøre brug af Pythagoras sætning igen. I dette tilfælde beregner vi kursen(202 + 302) og finder ud af, at A er en afstand på 36.0555127546… fra L (jeg vil runde decimaler til nærmeste tiende for at spare plads). Jeg tilføjer dette til bordet og placerer det i øverste højre hjørne af A ‘ S firkant. Endelig summen. Jeg tilføjer den korteste afstand fra starten til den heuristiske afstand, tilføjer den til bordet og placerer den i midten af A ‘ S firkant.

det er vores udgangspunkt, og vi kan nu se på A ‘ S naboer og tilføje deres værdier til bordet.

først tilføjer vi B, E og F til det åbne sæt. Dernæst kan vi finde deres korteste afstande fra starten, og fordi alt er et skridt fra starten, vil det bare være 10 ‘ erne for B og E og 14 for diagonalen flytte til F. For den heuristiske afstand bruger vi Pythagoras sætning fra hver firkant til slutspidsen. Endelig får vi deres summer og tilføjer “A” til hver af deres tidligere toppunktkolonner.

på dette tidspunkt har vi gjort alt, hvad vi har brug for med A, så det flyttes til det lukkede sæt, og vi har brug for et nyt nuværende toppunkt. For at bestemme hvilket toppunkt der skal undersøges næste, ser vi på det åbne sæt og finder det toppunkt, der har den laveste sum. Lige nu er det F med en sum på 36,1. Så vi gør det til det nuværende toppunkt og begynder at udarbejde værdierne for sine naboer.

f har otte naboer, men kun fem vil blive ændret her. For det første er A i det lukkede sæt nu, så det kan ikke ændres nu. For de resterende syv tilføjer vi dem til det åbne sæt (medmindre de allerede er en del af det), og lad os derefter arbejde på deres afstande fra starten. Dette vil fungere meget som Dijikstras algoritme, og vi tilføjer F ‘S afstand fra starten til hver af sine naboers afstand fra F. på vores bord er F’ S afstand fra start 14, så vi udfylder 14+10=24 eller 14+14=28 for disse. B og E har dog allerede kortere afstande til starten, så deres tabeloptegnelser bliver ikke opdateret. Det efterlader fem hjørner, der vil blive opdateret, med C, jeg, og K får 28, og G og J får 24 for deres afstand fra start. Brug derefter Pythagoras sætning for hver af disse knudepunkter’ heuristiske afstande, Beregn derefter deres summer og tilføj til sidst “F” til den forrige toppunktkolonne for de knudepunkter, der blev opdateret.

F er færdig og flyttes til det lukkede sæt, og et nyt aktuelt toppunkt vælges ud fra hvilket toppunkt i det åbne sæt har den laveste sum. Det er meget tæt, men K er en tiendedel mindre (og ja, det er på grund af en afrundingsforskel, men i dette tilfælde viser det sig at være en god tie breaker). K vil være det nye toppunkt at undersøge, så lad os starte med at se på sine naboer.

k har seks naboer, hvoraf tre allerede er i det åbne sæt, så de sidste to H og l vil også blive tilføjet til det åbne sæt. Nu beregner vi deres afstande fra start. K ‘ S afstand fra start er 28, så vi arbejder med 28+10=38 for G, J og L og 28+14=42 for H. G og J har dog allerede mindre afstande at starte, så de opdateres ikke. Vi finder de heuristiske afstande for hver, beregner deres summer og tilføjer “K” til hvert tidligere toppunkt, der blev opdateret.

K er færdig og flyttet til det lukkede sæt, og det næste toppunkt i det åbne med den mindste sum er L, vores destination!

nu, at l er det aktuelle toppunkt, algoritmen slutter, og vi kan bruge vores tabel til at spore stien tilbage til starten:

• l’ s tidligere toppunkt er k
• k ‘ s tidligere toppunkt er a, startpunktet.

så det betyder, at den korteste vej er en >F >K > L.

analyse af resultaterne

sammenlignet med Dijkstras algoritme har a* efterladt et ret rod bag det. Lad os se på et par ulige punkter. Start med at se på toppunkt C og dens afstand til starten: 28. Det virker underligt, fordi A og C kun er to vandrette bevægelser væk fra hinanden, så den korteste afstand skal være 20. Lige nu synes C at tro, at dens korteste vej til A er to diagonale bevægelser gennem F.

Når Dijkstras algoritme er færdig, skal den give en meget komplet tabel over afstande fra udgangspunktet. Omvendt har A * ‘ S tabel forkerte værdier og mangler helt toppunkt D. Men det fik det samme svar, som Dijkstra ville have, og det gjorde meget hurtigere. Dijkstra ‘ s ville have ønsket at se på alle 12 hjørner, før de erklærede, at den fandt den korteste vej; a* behøvede kun at se på 4, før den fandt den rigtige vej. Denne ændring i hastighed skyldes den heuristiske, vi brugte: så ofte vi kunne, vi ønskede at lukke afstanden med vores destination. Hvis vi går tilbage til definitionen af heuristik, har a* handlet fuldstændighed for hastighed.

lad os prøve et andet lille eksempel, men med en hindring på vej til destinationen.

udgangspunktet er øverste venstre hjørne, og A* forsøger at finde den korteste vej til nederste højre hjørne. De sorte firkanter repræsenterer et hul i grafen og kan ikke krydses. Hvis a * følger sin heuristiske om “altid komme tættere på destinationen”, vil de sorte firkanter føre det til en blindgyde.

på dette tidspunkt vil a* se efter de mindste summer, som vil være firkanterne lige under og til højre for startpunktet. A * vil udforske begge stier, men den nedadgående sti vil løbe ind i en anden blindgyde, og højre sti vil finde en vej rundt om de sorte firkanter. Det kan spille lidt anderledes ud end dette, men lad os antage, at det er sådan, hvordan a* håndterede dette scenario. Selv når det blev trukket ind i blindgyder, var det i stand til at gå tilbage og finde en anden vej, og det behøvede ikke at se på hvert toppunkt (det øverste højre toppunkt blev sprunget over igen). Det betyder, at når en* stjerne kører på sit absolut værste, er det stort set lige så hurtigt som Dijkstras normale ydeevne. Hver algoritme har perfekt gyldige brugssager, men med hensyn til stifinding og finde de korteste stier er A* det bedre valg.