Polunhakualgoritmit kaksiulotteisessa ruudukossa

Abstract

Polunhakua tarvitaan nykyään monissa eri teknologioiden osa-alueissa, kuten videopeleissä tai verkkoliikenteen reitityksessä. Varsinkin verkkoliikenteen reitityksessä on tarve tehokkaalle haulle, sillä se voi vaikuttaa esimerkiksi siihen, miten nopeasti tietoa siirretään verkon välityksellä laitteesta toiseen. Polunhaun ja sen tehokkuuden merkitys tulee vielä tulevaisuudessa kasvamaan autonomisten teknologioiden, kuten droonien, kehittyessä. Näihin nykyisiin ja tuleviin käyttökohteisiin tarvitaan eri tilanteisiin sopivia tehokkaita polunhakualgoritmeja.

Tässä tutkielmassa käydään läpi kolme polunhakualgoritmia ja vertaillaan niiden suoritusaikoja kaksiulotteisessa ruudukossa. Tutkielma on rajattu kaksiulotteiseen ruudukkoon, sillä siinä voidaan vertailla selkeästi valittuja algoritmeja. Tämän lisäksi tällaisia ruudukoita käytetään muun muassa videopeleissä, joten kaksiulotteinen ruudukko on realistinen käyttökohde polunhakualgoritmeille.

Tutkielmaan valitut polunhakualgoritmit ovat breadth-first search (BFS, suom. leveyssuuntainen haku), Dijkstran algoritmi ja A* (A-star, suom. A tähti). Näiden teoriaa käydään läpi esittämällä niiden toimintaperiaatteita ja mahdollisia vaihtoehtoisia toteutuksia. Lisäksi algoritmeista esitetään niiden asymptoottinen tehokkuus, mikäli tällainen on selvästi saatavilla.

Polunhakualgoritmien suoritusaikoja vertaillaan ruudukoissa käyttäen avuksi kolmea aikaisemmin tehtyä tutkimusta. Näissä tutkimuksissa algoritmeja suoritettiin erikokoisissa ja -tyyppisissä kaksiulotteisissa ruudukoissa. Tutkimuksissa käytettiin myös vaihtoehtoisia liikkumistapoja ruutujen välillä eli algoritmi sai liikkua joko neljään tai kahdeksaan eri suuntaan ruudusta.

Tutkielman vertailun tuloksista huomataan, että A* on tehokkain valituista polunhakualgoritmeista kaksiulotteisissa ruudukoissa. A*:n käyttämän heuristiikan avulla sillä oli selvästi pienemmät suoritusajat kuin muilla valituilla algoritmeilla lähes jokaisella ruudukkotyypillä. Tämän lisäksi tuloksista huomataan, että BFS on selvästi hitaampi polunhakualgoritmi kaksiulotteisessa ruudukossa kuin Dijkstran algoritmi tai A*.