et steg opp fra dijkstras algoritme er en* (les: «en stjerne»). Når Det gjelder pathfinding, Vil dijkstras algoritme prøve ut hver bane og hvert toppunkt for å finne den korteste banen mellom startpunkt og destinasjon, Mens A* har et ekstra attributt, en heuristisk, som skal tillate det å finne den korteste banen uten å måtte sjekke hver bane og toppunkt. Hver algoritme har sine brukssaker, men generelt Sett kan Både Dijkstra og A* finne den korteste banen, Men A * vil gjøre det raskere.

jeg vil anbefale å vite litt Om dijkstras algoritme før du går inn i denne artikkelen, da det er mange sammenligningspunkter. Eller enda bedre, les min siste artikkel om emnet! https://medium.com/swlh/pathfinding-dijkstras-algorithm-65e71c346629

jeg må sette opp noen ting for mine eksempler, pluss gi en definisjon av hva en heuristisk er. For å starte, la meg vise deg hvilken type graf jeg vil bruke til eksemplene mine.

Knapt en graf. Mer av et sjakkbrett.

Dette er litt abstrakt, men jeg vil bruke et rutet brett som min graf, og jeg vil tillate bevegelse mellom rutene. Hvis jeg legger over tilsvarende graf med hjørner og kanter, bør det se slik ut.

Det er for linjer. Kanskje ikke så nyttig…

La oss ta midtplassen / toppunktet, E, For eksempel. Den har åtte nærliggende hjørner, slik at vi kan bevege oss opp, ned, venstre, høyre og i alle diagonale kombinasjoner av hver. Og det er egentlig alt jeg prøvde å sette opp her: jeg skal bruke et sjakkbrett, og jeg vil tillate bevegelse i åtte retninger. Litt langvarig, men nå la oss begynne å se på bevegelse og kostnaden for bevegelse.Starter enkelt, vil jeg si at å flytte opp, ned, venstre og høyre har en bevegelseskostnad på 1. Styret blir opptatt, så jeg trekker ut grafen, og legger til at bevegelseskostnaden på som kantvekter.

avstand.

hvis disse vektene er avstander, og hvis forholdene og naboene er lagt ut slik, kan geometri fortelle oss om kostnaden for diagonale bevegelser. Ved Hjelp Av Pythagoras Teorum, bør vi få √(12 + 12) = √2, som er omtrent 1.41421356237… Som ikke er et veldig fint nummer å jobbe med. Så, jeg stjeler en ide (og sitere mine kilder!), og multiplisere og runde kostnadene ned. For begge typer bevegelser, vil jeg flere dem med ti, og deretter avkorte deres desimaler. Dette vil gi oss endelige kostnader på 10 for opp, ned, venstre og høyre bevegelser, og 14 for diagonale bevegelser.

Fine runde tall for alt. Dette betyr også at diagonale bevegelser er billigere enn å lage to ikke-diagonale bevegelser til samme firkant (10 + 10 >14)

Heuristikk

jeg føler at disse er vanskelig for meg å definere, så jeg begynner Med Wikipedias åpningslinje om emnet:

innen informatikk, kunstig intelligens og matematisk optimalisering er en heuristisk (fra gresk εὑρίσκω «jeg finner, oppdager») en teknikk designet for å løse et problem raskere når klassiske metoder er for sakte, eller for å finne en omtrentlig løsning når klassiske metoder ikke finner noen eksakt løsning. Dette oppnås ved å handle optimalitet, fullstendighet, nøyaktighet eller presisjon for fart. På en måte kan det betraktes som en snarvei.

er det nyttig? Skjønner du? Fordi jeg ikke skjønner det. Jeg mener, jeg forstår det, og det er en nøyaktig beskrivelse, men hvis dette var den første du noensinne hadde hørt om en heuristisk, er jeg ikke sikker på at du vil få hele bildet av hva heuristikken er fra dette. Kanskje hvis jeg bare forteller deg om en * s pathfinding heuristisk, får du en bedre forståelse.

Med dijkstras algoritme var fokuset på en verdi: den korteste avstanden fra startindeksen. Som, når du tenker på det, er litt rart. Du har denne algoritmen prøver å finne nye, kortere veier til noen destinasjon, men fokuset er alltid på hvor det startet. Tenk deg at noen går ut for dagligvarer, men går bakover hele veien, prøver å holde øye med deres hjem til de kom til butikken. I virkeligheten ville dette sannsynligvis ikke fungere, men kanskje hvis du ga dem tid til å gå over hele byen, kan det til slutt fungere.

Går av denne goofy analogien, A * er forskjellig Fra Dijkstra fordi Det antyder å snu seg og gå fremover. A*, som Dijkstra, holder også oversikt over hvor langt hjemmefra det er, men den unike funksjonen er at den holder styr på hvor langt det er fra reisemålet også. Når du gjør sitt neste skritt, Vil Dijkstra se på hvilken vei som for tiden er den korteste, Men A * går et skritt videre og vurderer også om det trinnet beveger det nærmere målet. Mer enkelt, A* har et grovt estimat av gjenværende avstand til målet, og når dette estimatet kommer nærmere null, vet Det at det beveger seg i riktig retning. Dette er den heuristiske vi skal bruke i våre eksempler.

Stepping Gjennom Algoritmen

Dette kommer til å være et ganske enkelt eksempel, men det skal vise deg grunnleggende flyt og repetisjon av algoritmen. Jeg skal sørge for å gi lenker i mine referanser til andre, mer kompliserte eksempler, men dette bør være en god primer for dem. Jeg bruker et oppsett som ligner På Hvordan Jeg demonstrerte Dijkstra.

figcaption > la oss gå over disse komponentene. Først har vi et 4×3 bord som vil være vår graf. Vårt mål vil være å finne den korteste veien Mellom A Og L. jeg skal fjerne bokstavene når jeg begynner å vise trinnene, men her er deres etiketter for nå. Under brettet er to sett som brukes til å holde styr på hjørnene. I motsetning Til I Dijkstra, holder vi ikke hvert toppunkt i et startsett (som «Unvisited»), men vi legger dem Til Å Åpne når de blir oppdaget som naboer til dagens toppunkt. Til slutt, bordet. Mye Som Dijkstra, men med to kolonner for heuristisk avstand og summen av de to avstandene.

En forskjell mellom Dijkstra og A * er At Dijkstra får begynne å looping umiddelbart, Men A * må gjøre litt oppsett for startpunktet. Så la oss gjøre det nå, og få litt av en ide om hvordan bordet skal fungere.

først legger vi til et åpent sett. For det andre vil Vi finne Ut A ‘ s avstand fra starten. Naturligvis er avstanden fra A til a null, så det vil bli lagt til bordet, og jeg vil ha det tallet i øverste venstre hjørne av a ‘ s firkant. For det tredje bestemmer vi den heuristiske avstanden. Vi kan gjøre dette på en rekke måter, alt som er viktig er at vi måler denne avstanden på samme måte for hver rute. Jeg skal bruke en» som luftlinje » avstand for alle heuristiske avstander, noe som betyr at jeg kan gjøre bruk av Pythagorasetningen igjen. I dette tilfellet beregner vi √(202 + 302), og finner At A er en avstand på 36.0555127546… Fra L (jeg runder desimaler til nærmeste tiende for å spare plass). Jeg legger dette til bordet, og legger det øverst til høyre på a-torget. Til slutt, summen. Jeg legger til den korteste avstanden fra starten til heuristisk avstand, legg den til bordet, og plasser den i Midten Av a ‘ s square.

det er vårt utgangspunkt, og vi kan nå se På a ‘ s naboer, og legge sine verdier til bordet.

først legger vi til b, e og f i det åpne settet. Deretter kan vi finne sine korteste avstander fra starten, og fordi alt er ett skritt fra starten, vil det bare være 10 for B og E, og 14 for diagonal flytte Til F. for heuristisk avstand bruker Vi Pythagorasetningen fra hver firkant til sluttpunktet. Til slutt får vi summene sine, og legger til» A » til hver av sine tidligere vertex-kolonner.

På dette punktet har Vi gjort alt Vi trenger Med A, så det blir flyttet Til Det Lukkede settet, og vi trenger et nytt nåværende toppunkt. For å avgjøre hvilket toppunkt som skal undersøkes neste, ser vi På Det Åpne settet, og finner toppunktet som har den laveste summen. Akkurat Nå er Det F med en sum på 36,1. Så, vi gjør det til det nåværende toppunktet, og begynner å utarbeide verdiene for sine naboer.

f har åtte naboer, men bare fem kommer til å bli endret her. For Det Første er A I Lukket sett nå, så det kan ikke endres nå. For de resterende syv legger vi dem Til Det Åpne settet (med mindre de allerede er en del av det), og la oss jobbe med avstandene fra starten. Dette kommer til å fungere mye Som Dijikstras algoritme, og vi legger Til Fs avstand fra starten til hver av naboens avstand Fra F. På bordet vårt Er fs avstand fra start 14, så vi fyller inn 14+10=24 eller 14+14=28 for disse. Imidlertid Har B og E allerede kortere avstander til starten, slik at deres tabelloppføringer ikke blir oppdatert. Det etterlater fem hjørner som vil bli oppdatert, Med C, I og K får 28, Og G og J får 24 for avstanden fra start. Deretter bruker Du Pythagorasetningen for hver av disse toppunktenes heuristiske avstander, beregner deretter summene, og til slutt legger du til » F » til forrige toppunktkolonne for toppunktene som ble oppdatert.

F er fullført Og vil bli flyttet Til Det Lukkede settet, og et nytt nåværende toppunkt vil bli valgt basert på hvilket toppunkt i Det Åpne settet har den laveste summen. Det er veldig nært, Men K er en tiendedel mindre (og ja, dette er på grunn av en avrundingsforskjell, men i dette tilfellet viser Det seg å være en god tie breaker). K vil være det nye toppunktet å undersøke, så la oss begynne med å se på naboene.

k har seks naboer, hvorav tre allerede er i det åpne settet, så de to siste h og l vil også bli lagt til det åpne settet. Nå beregner vi avstandene fra start. Ks avstand fra start er 28, så vi jobber med 28 + 10=38 For G, J og L, og 28+14=42 For H. G og J har imidlertid allerede mindre avstander å starte, så de vil ikke bli oppdatert. Vi finner de heuristiske avstandene for hver, beregner summene, og legger til » K » til hvert tidligere toppunkt som ble oppdatert.

K er ferdig og flyttet Til Det Lukkede settet, og neste toppunkt I Det Åpne Med den minste summen Er L, vår destinasjon!

nå, at l er det nåværende toppunktet, slutter algoritmen, og vi kan bruke bordet vårt til å spore banen tilbake til starten:

• l forrige toppunkt er k
• k forrige toppunkt er f
• f’ forrige toppunkt er a, start toppunktet.

så dette betyr at den korteste banen Er En > F> L.

Analysere Resultatene

Sammenlignet Med dijkstra algoritme, a * har forlatt ganske rot bak det. La oss se på noen merkelige punkter. Start med å se på vertex C Og avstanden til starten: 28. Det virker rart fordi A Og C bare er to horisontale trekk vekk fra hverandre, så den korteste avstanden skal være 20. Akkurat Nå Synes C å tro at den korteste banen Til A er to diagonale bevegelser gjennom F.

Når dijkstras algoritme er ferdig, bør Den gi et veldig komplett bord med avstander fra utgangspunktet. Omvendt Har a * ‘s tabell feilverdier, og mangler helt vertex D. Men det fikk det samme svaret Som Dijkstra ville ha, og det gjorde mye raskere. Dijkstra ville ha ønsket å se på alle 12 hjørner før de erklærte at den fant den korteste banen; A * behøvde bare å se på 4 før den fant den rette veien. Denne endringen i fart er på grunn av heuristisk vi brukte: så ofte vi kunne, vi ønsket å være å lukke avstanden med vår destinasjon. Hvis Vi går tilbake Til Wikipedias definisjon for heuristikk, har A* handlet fullstendighet for fart.

la oss prøve et annet lite eksempel, men med en hindring på vei til destinasjonen.

utgangspunkt er øverste venstre toppunkt, og a* prøver å finne den korteste banen til nederste høyre toppunkt. De svarte firkantene representerer et gap i grafen og kan ikke krysses. Hvis A * følger sin heuristiske «alltid komme nærmere destinasjonen», vil de svarte firkantene føre den til en blindgyde.

på dette punktet vil a* se etter de minste summene, som vil være rutene like under og til høyre for startpunktet. A * vil utforske begge banene, men den nedadgående banen vil løpe inn i en annen blindgyde, og høyre vei vil finne en vei rundt de svarte firkantene. Det kan spille ut litt annerledes enn dette, men la oss anta at Dette er Hvordan A* håndterte dette scenariet. Selv når det ble trukket inn i døde ender, var det i stand til å gå tilbake og finne en annen sti, og det behøvde ikke å se på hvert toppunkt (det øverste høyre toppunktet ble hoppet over igjen). Dette betyr at Når a * star kjører på sitt absolutt verste, er det i utgangspunktet så fort Som Dijkstras normale ytelse. Hver algoritme har helt gyldige brukssaker, Men Når Det gjelder å finne og finne de korteste stiene, Er A* det bedre valget.