A*-algoritmin variantit
1.67 MB
avoin
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
Lataukset435
Pysyvä osoite
Verkkojulkaisu
DOI
Tiivistelmä
Yksittäistä agenttia käsitteleviä paras ensin -hakualgoritmeja on käytetty vuosikymmenien ajan ratkaisuina hyvin monentyyppisiin ja monia aloja koskettaviin ongelmiin. Yksi tärkeimmistä on jo vuonna 1968 esitelty A*-algoritmi (lausutaan "A tähti").
Vaikka A* on hyvin laajalti käytetty, tietyissä tilanteissa se on osoittautunut riittämättömäksi. Tämän vuoksi A*:een on esitelty suuri määrä laajennoksia vuosien saatossa. A*:n laajennoksia on jo vuosien ajan kategorisoitu sen mukaan mitä A*:n ongelmia tai puutteita kyseinen laajennos pyrkii korjaamaan. Vaikka kategorioita on löydettävissä kirjallisuudesta lukuisia,tässä tutkielmassa keskitytään neljään kategoriaan. Näitä ovat inkrementaaliset, anytime, reaaliaikaiset sekä any-angle-algoritmit.
Inkrementaaliset algoritmit käyttävät peräkkäisiä keskenään hyvin samankaltaisia hakuja hyväksi seuraavissa hauissa. Anytime-algoritmit kykenevät antamaan toteuttamiskelpoisen arvion reitistä milloin tahansa (paitsi ensimmäisen laskennan aikana). Algoritmin oletetaan kykenevän myös parantamaan reittiä mitä enemmän laskentaan annetaan aikaa. Reaaliaika-algoritmien yhteinen piirre on, että ne kykenevät toimimaan hyvin tarkkojen aikarajojen puitteissa. Any-angle-algoritmit eivät rajoita liikkumista solmujen välillä lainkaan.
Tässä tutkielmassa esitellään ensin yksi algoritmi jokaisesta kategoriasta, D* Lite, ARA*, LSS-LRTA* sekä Field D*. Nämä algoritmit toteutetaan Python-ohjelmointikielellä ja niiden suorituskykyä testataan tuntemattomassa ympäristössä. Tämän jälkeen niiden suorituskykyä testiympäristössä arvioidaan.