Hyppää sisältöön
    • Suomeksi
    • In English
  • Suomeksi
  • In English
  • Kirjaudu
Näytä aineisto 
  •   Etusivu
  • 1. Kirjat ja opinnäytteet
  • Pro gradu -tutkielmat ja diplomityöt sekä syventävien opintojen opinnäytetyöt (kokotekstit)
  • Näytä aineisto
  •   Etusivu
  • 1. Kirjat ja opinnäytteet
  • Pro gradu -tutkielmat ja diplomityöt sekä syventävien opintojen opinnäytetyöt (kokotekstit)
  • Näytä aineisto
JavaScript is disabled for your browser. Some features of this site may not work without it.

A*-algoritmin variantit

Nygård, Ville (2020-12-23)

A*-algoritmin variantit

Nygård, Ville
(23.12.2020)
Katso/Avaa
DIfinal.pdf (1.671Mb)
Lataukset: 

Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
avoin
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe202101222415
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.
Kokoelmat
  • Pro gradu -tutkielmat ja diplomityöt sekä syventävien opintojen opinnäytetyöt (kokotekstit) [9224]

Turun yliopiston kirjasto | Turun yliopisto
julkaisut@utu.fi | Tietosuoja | Saavutettavuusseloste
 

 

Tämä kokoelma

JulkaisuajatTekijätNimekkeetAsiasanatTiedekuntaLaitosOppiaineYhteisöt ja kokoelmat

Omat tiedot

Kirjaudu sisäänRekisteröidy

Turun yliopiston kirjasto | Turun yliopisto
julkaisut@utu.fi | Tietosuoja | Saavutettavuusseloste