A*-haku
Dijkstra suuntavaistolla. Jokaisen paikan kustannukseen se lisää arvion jäljellä olevasta kustannuksesta, joten se kokeilee ensin paikkoja, jotka näyttävät olevan lähimpänä maalia.
- aika O((V + E) log V)
- tila O(V)
- käyttää prioriteettijonoa
Mitä nämä tarkoittavat?
- Kustannus: mitä siirto maksaa. Sokkelossa maa maksaa 1, muta 3 ja vesi 9; graafissa kaaren luku.
- Prioriteettijono: jono, jossa halvin menee ensin, ei ensimmäisenä tullut.
- Arvio (h): arvaus jäljellä olevasta kustannuksesta. A* pysyy tarkkana vain, jos se ei ole koskaan liian suuri.
- Kaaren relaksointi: tarkistetaan, antaako kulku nykyisen paikan kautta naapurille pienemmän kustannuksen, ja otetaan se, jos antaa.
- jonossa
- nykyinen
- valmis
- halvin reitti
- maa · 1
- muta · 3
- vesi · 9
- seinä
Uusi: Lähtö ruudusta A1, kustannus 0 ja arvio 26 maaliin. Se on ainoa jonossa.
Välilyönti: toisto tai tauko. Nuolinäppäimet: askel. Home ja End: alkuun tai loppuun.
Kokeile tätä: Valitse avoin kenttä ja vaihda Dijkstran ja A*:n välillä: molemmat löytävät yhtä kalliin reitin, mutta A* ottaa jonosta paljon vähemmän ruutuja.
Miten se toimii
A* toimii kuin Dijkstra, mutta järjestää jonon arvon f = kustannus tähän asti + h mukaan, missä h arvioi jäljellä olevan kustannuksen. Sokkelossa h on siirtojen määrä M:ään seinistä ja mudasta välittämättä; graafissa linnuntie jaettuna 10:llä. Kunhan h ei koskaan arvioi liian suureksi, reitti, joka A*:lla on maalin ottohetkellä, on halvin, aivan kuten Dijkstralla. Mitä parempi arvio, sitä vähemmän paikkoja on katsottava.
Milloin se on hyvä valinta
Käytä A*:ta, kun etsit yhtä maalia ja osaat arvioida, kuinka kaukana se on: reitinhaku peleissä, robotit, reittisuunnittelijat kartalla. Kun h = 0, se on täsmälleen Dijkstra. Liian suureksi arvioiva arvio nopeuttaa A*:ta, mutta voi viedä halvimman reitin.