Heuristiikka reitinhaussa ja sen vaikutus A*-algoritmin suorituskykyyn

Metsola, Mikko (2019)
 
Avaa tiedosto
Lataukset: 



Metsola, Mikko
2019

Tieto- ja sähkötekniikan TkK tutkinto-ohjelma
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2019-11-04
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-201909113251
Tiivistelmä
A*-algoritmi on yleinen reitinhakualgoritmi, joka hyödyntää heuristiikkaa. Heuristiikka on arvio kahden pisteen välisestä etäisyydestä ja sen tavoitteena on nopeuttaa reitinhakua. Heuristiikan liiallinen painottaminen voi kuitenkin johtaa huonoihin tuloksiin. Tässä työssä tutkitaan A*-algoritmin käyttäytymistä neljällä eri heuristiikalla ja erilaisilla painotuksilla. Heuristiikan painottamisen on tarkoitus korostaa heuristiikan vaikutusta reitinhaussa ja nopeuttaa hakua entisestään.

A*-algoritmin suorituskykyä tarkkailtiin kaksiulotteisessa ruudukossa JavaScript-ohjelmalla reitinhakuun soveltuvaa kirjastoa käyttäen. Tutkielman tuloksissa tulee esiin heuristiikkojen väliset ainutlaatuiset piirteet sekä niiden muutos heuristiikan painottamisen myötä. Vaikka Manhattan-etäisyydellä laskettu heuristiikka on testikohteelle tarkoitettu tapa mitata heuristiikkaa, ovat sen erot muihin heuristiikkoihin nähden vähäisiä.
Kokoelmat