askel ylöspäin Dijkstran algoritmista on a* (Lue: ”tähti”). Mitä pathfinding, Dijkstra n algoritmi haluaa kokeilla jokainen polku ja jokainen huippupiste löytää lyhin polku välillä sen lähtökohta ja määränpää, kun taas* on ylimääräinen attribuutti, heuristic, jonka pitäisi mahdollistaa sen löytää lyhin polku tarvitsematta tarkistaa jokainen polku ja huippupiste. Jokaisella algoritmilla on käyttötapauksensa, mutta yleisesti ottaen sekä Dijkstra että A* löytävät lyhimmän polun, mutta a* tekee sen nopeammin.
suosittelisin tietämään hieman Dijkstran algoritmista ennen kuin menen tähän artikkeliin, sillä vertailukohtia on paljon. Tai mikä vielä parempaa, lue viimeinen kirjoitukseni tästä aiheesta! https://medium.com/swlh/pathfinding-dijkstras-algorithm-65e71c346629
minun täytyy perustaa muutamia asioita esimerkeilleni, sekä antaa määritelmä siitä, mitä heuristinen on. Aluksi, anna minun näyttää tyypin kaavion haluan käyttää minun esimerkkejä.
Tämä on hieman abstrakti, mutta haluan käyttää ruutua graafinani, ja haluan sallia liikkeen sen ruutujen välillä. Jos olen overlay vastaavan kuvaajan kanssa vertices ja reunat, sen pitäisi näyttää jotain tällaista.
otetaan esimerkiksi Keskustori / vertex, e. Siinä on kahdeksan vierekkäistä vertices, joten voimme liikkua ylös, alas, vasemmalle, oikealle, ja kaikissa lävistäjä yhdistelmiä kunkin. Ja se on oikeastaan kaikki mitä yritin järjestää täällä: aion käyttää ruutua, ja sallin liikkeen kahdeksaan suuntaan. Vähän pitkäveteinen, mutta nyt aletaan tarkastella liikettä ja liikkumisen kustannuksia.
yksinkertaisesta aloittaen sanon, että ylös, alas, vasemmalle ja oikealle liikkumishinta on 1. Laudalla alkaa olla kiire, joten otan kaavion ja lisään liikkeen hinnan reunapainoiksi.
Jos nämä painot ovat etäisyyksiä, ja jos suhteet ja naapurit on aseteltu näin, geometria voi kertoa diagonaaliliikkeiden kustannuksista. Käyttämällä Pythagoraan Theorum, meidän pitäisi saada √(12 + 12) = √2, se on noin 1,41421356237, – joka ei ole kovin mukava luku työskennellä. Niin, minä varastaa idea (ja siteerata lähteeni!), ja moninkertaistaa ja pyöristää kustannukset alas. Toistan ne kymmenellä ja lyhennän desimaaleja. Tämä antaa meille lopulliset kustannukset 10 ylös, alas, vasemmalle ja oikealle liikkeitä, ja 14 diagonaalinen liikkeitä.
heuristiikka
koen näiden olevan minulle vaikeita määritellä, joten aloitan Wikipedian avausviivalla aiheesta:
tietojenkäsittelytieteessä, tekoälyssä ja matemaattisessa optimoinnissa heuristinen (kreikan sanasta εὑρίσκω ”löydän, löydän”) on tekniikka, joka on suunniteltu ratkaisemaan ongelma nopeammin, kun klassiset menetelmät ovat liian hitaita, tai löytämään likimääräinen ratkaisu, kun klassiset menetelmät eivät löydä täsmällistä ratkaisua. Tämä saavutetaan kaupankäynnin optimaalisuus, täydellisyys, tarkkuus, tai tarkkuus nopeuden. Tavallaan sitä voidaan pitää oikotienä.
onko siitä hyötyä? Ymmärrätkö? Koska en tajua sitä. Ymmärrän sen, ja se on tarkka kuvaus, mutta jos tämä oli ensimmäinen heuristinen, – en ole varma, saatko kokonaiskuvaa siitä, mitä heuristiikka on. Ehkä jos vain kerron sinulle A*n Polunetsintä heuristic, saat paremman käsityksen.
Dijkstran algoritmilla keskityttiin yhteen arvoon: lyhimpään etäisyyteen lähtöindeksistä. Se on tavallaan outoa. Sinulla on tämä algoritmi yrittää löytää uusia, lyhyempiä polkuja johonkin kohteeseen, mutta sen painopiste on aina siitä, mistä se alkoi. Kuvittele, että joku menee ostoksille, mutta kävelee koko matkan takaperin ja yrittää pitää silmällä kotiaan, kunnes he tulevat kauppaan. Tosielämässä tämä ei varmaan toimisi, mutta jos antaisit heille aikaa kiertää kaupunkia, se voisi lopulta onnistua.
tämän hessuvertauksen jälkeen A* eroaa Dijkstran vertauksesta, koska se ehdottaa kääntymistä ympäri ja eteenpäin kävelemistä. A*, kuten Dijkstra n, myös pitää kirjaa siitä, kuinka kaukana kotoa se on, mutta sen ainutlaatuinen piirre on, että se pitää kirjaa siitä, kuinka kaukana se on määränpäästä, liian. Seuraavaa askelta tehdessään Dijkstra katsoo, mikä polku on tällä hetkellä lyhin, mutta A* menee askeleen pidemmälle ja pohtii myös, onko tuo askel viemässä sitä lähemmäs tavoitettaan. Yksinkertaisemmin, A* on karkea arvio sen jäljellä etäisyys tavoitteeseensa, ja kun tämä arvio tulee lähemmäksi nollaa, se tietää se liikkuu oikeaan suuntaan. Tätä heuristista käytämme esimerkeissämme.
algoritmin läpikäyminen
tästä tulee melko yksinkertainen esimerkki, mutta sen pitäisi näyttää algoritmin perusvirtaus ja toisto. Varmistan tarjota linkkejä minun viittauksia muihin, monimutkaisempi esimerkkejä, mutta tämän pitäisi olla hyvä pohjamaali niille. Käytän samanlaista asetelmaa kuin Dijkstran.
figcaption>käydään läpi nämä komponentit. Ensinnäkin, meillä on 4×3 aluksella, joka on meidän kaavio. Tavoitteenamme on löytää lyhin polku välillä A ja L. aion poistaa kirjaimet, kun alan näyttää vaiheet, mutta tässä ovat niiden etiketit toistaiseksi. Alla aluksella on kaksi sarjaa käytetään pitämään kirjaa, vertices. Toisin kuin Dijkstra: ssa, emme pidä jokaista huippupistettä aloitusjoukossa (kuten ”Unvisited”), mutta lisäämme ne auki, kun ne havaitaan nykyisen huippupisteen naapureina. Lopuksi pöytä. Paljon samanlainen kuin Dijkstra, mutta kaksi saraketta enemmän heuristinen Etäisyys ja summa kahden etäisyydet.
vielä yksi ero Dijkstran ja A*: n välillä on se, että Dijkstran saa aloittaa silmukoinnin heti, mutta A*: n on tehtävä pieni asetelma aloitusvertikseen. Joten tehdään se nyt, ja saadaan vähän käsitys siitä, miten pöytä tulee toimimaan.
ensin lisätään a avoimeen joukkoon. Toiseksi selvitämme A: n etäisyyden alusta. Luonnollisesti etäisyys A: sta A: han on nolla, joten se lisätään taulukkoon, ja minulla on se numero A: n neliön vasemmassa yläkulmassa. Kolmanneksi, määritämme heuristisen etäisyyden. Voimme tehdä tämän monella tavalla, tärkeintä on, että mittaamme tämän etäisyyden samalla tavalla jokaiselle neliölle. Aion käyttää” as the crow flies ” – etäisyyttä kaikkiin heuristisiin etäisyyksiin, mikä tarkoittaa, että voin käyttää Pythagoraan teoreemaa uudelleen. Tässä tapauksessa meidän on laskettava √(202 + 302), ja todeta, että A on etäisyys 36.0555127546… L (I ’ ll Pyöreä desimaalin tarkkuudella lähimpään kymmenesosa säästää tilaa). Lisään tämän pöytään ja asetan sen A: n neliön oikeaan yläkulmaan. Lopuksi summa. Lisään lyhimmän matkan alusta heuristiseen etäisyyteen, lisään sen taulukkoon ja asetan sen keskelle A: n neliötä.
se on meidän lähtökohtamme, ja voimme nyt katsoa A: n naapureita ja lisätä niiden arvot taulukkoon.
ensin lisätään avoimeen joukkoon B, E ja f. Seuraavaksi voimme löytää niiden lyhimmät etäisyydet alusta, ja koska kaikki on yksi askel alusta, se ’ll vain 10: n B ja E, ja 14: n lävistäjä siirtyä F. varten heuristic etäisyys, me’ ll käyttää Pythagoraan lause kunkin neliön ja päättyy huippupiste. Lopuksi, saamme niiden summat, ja lisätä ” A ” kunkin edellisen huippupiste sarakkeet.
tässä vaiheessa olemme tehneet kaiken tarvittavan A: n kanssa, joten se siirretään suljettuun sarjaan, ja tarvitsemme uuden nykyisen huippupisteen. Voit määrittää, mitkä huippupiste olisi tutkittava seuraavaksi, me ’ LL tarkastella avoimen joukon, ja löytää huippupiste, joka on pienin summa. Tällä hetkellä se on F, jonka summa on 36,1. Niin, teemme siitä nykyisen huippupiste, ja alkaa selvittää arvot sen naapurit.
f: llä on kahdeksan naapuria, mutta vain viisi aiotaan vaihtaa täällä. Ensinnäkin, A on suljettu joukko nyt, joten sitä ei voi muuttaa nyt. Loput seitsemän, lisäämme ne avoimeen sarjaan (elleivät ne ole jo osa sitä), ja sitten työstetään niiden etäisyydet alusta. Tämä tulee toimimaan paljon kuten Dijikstran algoritmi, ja lisäämme F: n etäisyyden alusta jokaisen naapurinsa etäisyyteen F: stä.pöydällämme F: n etäisyys startista on 14, joten täytämme 14+10=24 tai 14+14=28 näille. B: llä ja E: llä on kuitenkin jo lyhyemmät etäisyydet starttiin, joten niiden taulukkoennätykset eivät päivity. Tämä jättää viisi vertices, joka päivitetään, c, I, ja K saada 28, ja G ja J saada 24 niiden etäisyys alusta. Seuraavaksi käytetään Pythagoraan teoreemaa jokaiselle näistä verticesin heuristisista etäisyyksistä, lasketaan sitten niiden summat ja lisätään lopuksi ”F” edelliseen huippupistesarakkeeseen niiden vertices-pisteiden osalta, joita päivitettiin.
F on valmis ja siirretään suljettuun joukkoon, ja valitaan Uusi nykyinen huippupiste sen perusteella, mikä avoimen joukon huippupiste on pienin summa. Se on hyvin lähellä, mutta K on kymmenesosa pienempi (ja kyllä, tämä johtuu pyöristysero, mutta tässä tapauksessa, se osoittautuu hyvä tie katkaisija). K on uusi huippupiste tutkittavaksi, joten aloitetaan katsomalla sen naapureita.
k: ssa on kuusi naapuria, joista kolme on jo avoimessa joukossa, joten kaksi viimeistä h ja L lisätään myös avoimeen joukkoon. Laskemme niiden etäisyydet alusta. K: n etäisyys aloituksesta on 28, joten G: lle, J: lle ja L: lle tulee 28+10=38 ja H: lle 28+14=42.G: llä ja J: llä on kuitenkin jo pienemmät etäisyydet aloitettavana, joten niitä ei päivitetä. Etsimme heuristiset etäisyydet jokaiselle, laskemme niiden summat ja lisäämme ”K” jokaiseen edelliseen huippupisteeseen, joka päivitettiin.
K on valmis ja siirretty suljettuun joukkoon, ja seuraava avoimeen kärkipisteeseen, jonka pienin summa on L, meidän määränpää!
nyt, että L on nykyinen huippupiste, algoritmi päättyy, ja voimme taulukkomme avulla jäljittää polun takaisin alkuun:
- l: n edellinen huippupiste on k
- k: n edellinen huippupiste on f
- F’ edellinen huippupiste on a, aloituspiste.
näin lyhin polku on > F > k > L.
tulosten analysointi
verrattuna Dijkstran algoritmiin A* on jättänyt jälkeensä melkoisen sotkun. Katsotaanpa muutamia outoja kohtia. Aloita vertex C ja sen etäisyys alkuun: 28. Se tuntuu oudolta, koska A ja C ovat vain kahden vaakasuuntaisen siirron päässä toisistaan, joten lyhimmän etäisyyden pitäisi olla 20. Juuri nyt C näyttää ajattelevan, että sen lyhin tie A: han on kaksi lävistäjää F: n kautta.
kun Dijkstran algoritmi päättyy, sen pitäisi tarjota hyvin täydellinen taulukko etäisyyksistä lähtöpisteestä. Kääntäen, A* ’ S taulukossa on vääriä arvoja, ja on täysin puuttuu huippupiste D. mutta se sai saman vastauksen, että Dijkstra n olisi, ja se teki paljon nopeammin. Dijkstra ’ s olisi halunnut tarkastella kaikkia 12 vertices ennen julistamista se löysi lyhin polku; a* tarvitsi vain tarkastella 4 ennen kuin se löysi oikean polun. Tämä nopeuden muutos johtuu käyttämästämme heuristiikasta: halusimme niin usein kuin mahdollista olla päättämässä matkaa määränpäähämme. Jos palaamme Wikipedian määritelmään heuristiikasta, A* on vaihtanut täydellisyyden nopeuteen.
kokeillaan toista pientä esimerkkiä, mutta matkalla määränpäähän on este.
lähtöpiste on vasemmanpuoleinen huippupiste, ja A* yrittää löytää lyhimmän polun oikeaan alakulmapisteeseen. Mustat neliöt edustavat kuilua kuvaajassa,eikä niitä voi ylittää. Jos a* seuraa sen heuristista ”aina päästä lähemmäksi määränpäätä”, nuo Mustat ruudut johtavat sen umpikujaan.
tässä vaiheessa a* etsii pienimpiä summia, jotka ovat neliöt juuri alla ja oikealla alkavan huippupisteen kohdalla. A* tutkii molemmat polut, mutta alaspäin kulkeva polku törmää toiseen umpikujaan, ja oikea polku löytää tien mustien neliöiden ympäri. Se voi pelata ulos hieman eri tavalla kuin tämä, mutta oletetaan, että tämä on miten a* käsitteli tämän skenaarion. Vaikka se sai vedetään umpikujaan, se pystyi menemään takaisin ja löytää toisen polun, ja se ei tarvitse tarkastella jokaista huippupiste (aivan oikeassa yläkulmassa huippupiste sai ohitetaan uudelleen). Tämä tarkoittaa sitä, että kun* tähti juoksee absoluuttisella pahimmillaan, se on periaatteessa yhtä nopea kuin Dijkstran normaali suoritus. Jokaisella algoritmilla on täysin kelvolliset käyttötapaukset, mutta polkujen etsimisen ja lyhyimpien polkujen löytämisen kannalta A* on parempi valinta.