A* hakualgoritmi
A* on joukko vaiheita (algoritmi), joiden avulla tietokoneet voivat selvittää, miten päästä nopeasti jonnekin kahden paikan välillä. Jos sinulla on luettelo paikoista ja siitä, kuinka vaikeaa on päästä yhdestä paikasta suoraan toiseen, A*:n avulla voit nopeasti selvittää nopeimman reitin. Se on sukua Dijkstran algoritmille, mutta se tekee älykkäitä arvauksia, joten se ei käytä niin kauan aikaa hitaiden keinojen etsimiseen. Se on hyvä askelten sarja, jos haluat vain reitin kahden paikan välillä. Jos aiot kysyä useita polkuja samasta kartasta, on olemassa nopeampia tapoja, jotka löytävät kaikki vastaukset kerralla, kuten Floyd-Warshallin algoritmi. A* ei toimi, jos haluat käydä useassa paikassa yhdellä matkalla (travelling salesman -ongelma).
Vaiheet
A* tarvitsee ensin luettelon kaikista paikoista, joihin voit mennä, ja sitten luettelon siitä, kuinka pitkä matka kunkin paikan välillä on. Sen jälkeen se kertoo, mikä on nopein tapa päästä paikasta A paikkaan Z.
Esimerkkinä sanotaan, että A on yhdistetty paikkoihin B ja C, ja B ja C ovat molemmat yhdistettyinä paikkoihin D ja E. D ja E ovat molemmat yhdistettyinä paikkoihin Z. A:sta Z:hen voi mennä neljällä eri tavalla: A-B-D-Z, A-C-D-Z, A-B-E-Z tai A-C-E-Z. Tietokone, joka käyttää A*:ta, tarkastelee ensin, kuinka vaikeaa on päästä A:sta B:hen ja A:sta C:hen. Tämä on näiden paikkojen "kustannus". Paikan kustannukset tarkoittavat sitä, kuinka vaikeaa on päästä paikasta A kyseiseen paikkaan. Kun tietokone on kirjannut ylös molemmat kustannukset, se tarkastelee, kuinka vaikeaa on päästä B:stä D:hen, ja lisää tämän B:n kustannuksiin. Se kirjoittaa tämän ylös D:n kustannuksiksi. Sitten tietokone tarkastelee, kuinka vaikeaa on päästä C:stä D:hen, ja lisää tämän C:n kustannuksiin. Tämä on eri kustannus D:lle, ja jos se on pienempi kuin jo olemassa oleva kustannus, se korvaa vanhan. Tietokone haluaa tietää vain parhaan reitin, joten se ei ota huomioon reittiä, jonka kustannukset ovat korkeammat. Se muistaa vain jommankumman vaihtoehdoista A-B-D ja A-C-D, sen mukaan, kumpi on nopeampi.
Tietokone jatkaa matkaa ja etsii nopeimman tavan päästä kohteeseen E. Lopuksi se menee D:stä Z:hen ja löytää kustannukset, ja E:stä Z:hen ja löytää kustannukset. Se saa lopullisen kustannuksen Z:lle, ja tämä on pienin mahdollinen kustannus. Nyt tietokone tietää, mikä tie on nopein, ja sillä on vastaus. Tietokone voi tehdä samanlaisen sarjan vaiheita, mutta paljon, paljon useammassa paikassa. Joka kerta se tarkastelee paikkaa, joka on lähimpänä A:ta, ja laskee yhteen kyseisen paikan naapurien kustannukset.
Edellä mainittua vaihesarjaa kutsutaan Dijkstran algoritmiksi. Dijkstran algoritmi voi olla hidas, koska se tarkastelee monia paikkoja, jotka saattavat kulkea väärään suuntaan kohteesta Z. Jos kysyisit tietokoneelta, miten päästä yhdestä kaupungista läheiseen kaupunkiin, Dijkstran algoritmi saattaisi päätyä etsimään toiseen osavaltioon.
A* korjaa tämän ongelman. A*:n avulla voit kertoa tietokoneelle arvion siitä, kuinka pitkä matka on kustakin paikasta loppuun. Tietokone voi käyttää arvausta kertoakseen, kuinka pitkä matka tietystä paikasta on suunnilleen matkaan Z. Sen sijaan, että se valitsisi vain A:ta lähimmän paikan, se tarkastelee sitä, jonka kokonaismatka on todennäköisesti pienin. Se löytää tämän kokonaismäärän lisäämällä kustannukset jäljellä olevaan odotettuun etäisyyteen. Näin se voi katsoa vain suuntaan, jossa asiat todennäköisesti paranevat. Ei haittaa, jos arvaus ei ole täydellinen, mutta yksinkertainenkin huono arvaus voi saada ohjelman etenemään paljon nopeammin. Jos yrität löytää reitin kahden paikan välillä reaalimaailmassa, hyvä arvaus on vain niiden välinen etäisyys suorassa linjassa. Todellinen polku teiden yli on pidempi, mutta näin ohjelma voi arvata sen, eikä se mene väärään suuntaan.
Matematiikan tai tietojenkäsittelytieteen kirjallisuudessa tämä arvaus on usein paikan funktio, ja sitä kutsutaan heuristiikaksi. Kukin paikka on piste, ja jokainen kahden paikan välinen polku on reuna. Nämä ovat sanoja graafiteoriasta.
