Reitinhaun optimoinnin haasteet
Klemola, Sakari (2022)
Klemola, Sakari
2022
Tieto- ja sähkötekniikan kandidaattiohjelma - Bachelor's Programme in Computing and Electrical Engineering
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ä
2022-10-11
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202209147070
https://urn.fi/URN:NBN:fi:tuni-202209147070
Tiivistelmä
Tänä päivänä reitinhaku on osa jokapäiväistä elämäämme ja yleistyy jatkuvasti. Reitinhaun keskeisimpänä tavoitteena on löytää lyhyin reitti annetun kahden pisteen välillä tarkasteltavasta ympäristöstä. Reitinhakua hyödynnetään muun muassa autonomisten robottien ohjauksessa, tietokoneohjaamien videopelihahmojen liikkumisessa ja karttasovellusten navigoinnissa. Useissa sovelluskohteissa reitinhaulta vaaditaan tehokkuutta, jotta saavutettaisiin toivottuja lopputuloksia. Reitinhaku on historiallisesti ollut tasapainottelua reitin laskemiseen käytetyn ajan ja lasketun reitin pituuden välillä. Monet tehokkuuteen vaikuttavat tekijät ovat toisistaan riippuvaisia, mikä puolestaan tekee reitinhaun optimoinnista hankalaa.
Tässä työssä tarkastellaan yhden toimijan vapaan liikkeen reitinhaun optimointia tieteellisen kirjallisuuden avulla ja reitinhaun tehokkuutta tarkastellaan lasketun reitin pituuden ja laskemiseen käytetyn ajan näkökulmasta. Työssä käsitellään reitinhaun kaksi pääkomponenttia, jotka ovat graafi ja algoritmi. Näistä osakokonaisuuksista käsitellään graafien erilaisia toteutustapoja sekä reitinhaussa käytettävien algoritmien eroja. Työn tavoitteena on tuoda esiin reitinhaun kompleksisuus ja vertailla erilaisten reitinhakutoteutusten vahvuuksia ja heikkouksia.
Tutkimuksessa havaittiin reitinhakutoteutuksien välillä olevan suuria eroja. Erot toteutusten välillä aiheutuvat reitinhakutavoitteen, graafitoteutuksen ja reitinhakuun käytettävän algoritmin yhteisvaikutuksesta. Reitinhakutoteutukseen vaikuttavat myös reitinhaun ulkopuoliset tekijät, kuten reitinhakua suorittavan laitteiston ominaisuudet, toteutuksen muodostamiseen käytettävissä oleva aika. Tästä syystä optimaalisen reitinhaun saavuttamiseksi tulee reitinhakua käsitellä kokonaisuutena ja huomioida reitinhaun tehokkuuteen vaikuttavien osien vaikutus toisiinsa. Tutkimuksessa todetaan reitinhaun optimaalisuuden määräytyvän sovelluskohteen perusteella ongelman moniulotteisuuden vuoksi, koska tarkasteltavan tapauksen piirteet määräävät optimaalisen reitinhaun luonteen.
Tässä työssä tarkastellaan yhden toimijan vapaan liikkeen reitinhaun optimointia tieteellisen kirjallisuuden avulla ja reitinhaun tehokkuutta tarkastellaan lasketun reitin pituuden ja laskemiseen käytetyn ajan näkökulmasta. Työssä käsitellään reitinhaun kaksi pääkomponenttia, jotka ovat graafi ja algoritmi. Näistä osakokonaisuuksista käsitellään graafien erilaisia toteutustapoja sekä reitinhaussa käytettävien algoritmien eroja. Työn tavoitteena on tuoda esiin reitinhaun kompleksisuus ja vertailla erilaisten reitinhakutoteutusten vahvuuksia ja heikkouksia.
Tutkimuksessa havaittiin reitinhakutoteutuksien välillä olevan suuria eroja. Erot toteutusten välillä aiheutuvat reitinhakutavoitteen, graafitoteutuksen ja reitinhakuun käytettävän algoritmin yhteisvaikutuksesta. Reitinhakutoteutukseen vaikuttavat myös reitinhaun ulkopuoliset tekijät, kuten reitinhakua suorittavan laitteiston ominaisuudet, toteutuksen muodostamiseen käytettävissä oleva aika. Tästä syystä optimaalisen reitinhaun saavuttamiseksi tulee reitinhakua käsitellä kokonaisuutena ja huomioida reitinhaun tehokkuuteen vaikuttavien osien vaikutus toisiinsa. Tutkimuksessa todetaan reitinhaun optimaalisuuden määräytyvän sovelluskohteen perusteella ongelman moniulotteisuuden vuoksi, koska tarkasteltavan tapauksen piirteet määräävät optimaalisen reitinhaun luonteen.
Kokoelmat
- Kandidaatintutkielmat [8709]