Lyhimmän polun etsimisen nopeuttaminen kontraktiohierarkialla
Zechner, Reetu (2021)
2021
Tekniikan ja luonnontieteiden kandidaattiohjelma - Bachelor's Programme in Engineering and Natural Sciences
Tekniikan ja luonnontieteiden tiedekunta - Faculty of Engineering and Natural 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ä
2021-06-08
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202105255438
https://urn.fi/URN:NBN:fi:tuni-202105255438
Tiivistelmä
Lyhimmän polun etsimistä graafista hyödynnetään useissa sovelluksissa, kuten esimerkiksi navigoinnin reittiohjeissa. Klassiset lyhimmän polun algoritmit kuten Dijkstran algoritmi ovat usein liian hitaita suurilla graafeilla, eivätkä ne välttämättä skaalaudu tehokkaasti suorituskyvyn kanssa. Kontraktiohierarkia (engl. contraction hierarchies) on esikäsittelyalgoritmi, jonka tarkoituksena on nopeuttaa lyhimmän polun etsimistä suuresta graafista. Tässä työssä perehdytään Dijkstran algoritmin ja kontraktiohierarkian toimintaan ja ominaisuuksiin. Työssä esitellään myös tarvittavat esitiedot graafeista ja poluista. Työn tarkoituksena on selvittää kontraktiohierarkian toimivuus esikäsittelyalgoritmina, sekä vertailla sitä Dijkstran algoritmiin empiirisesti.
Työ jakaantuu kolmeen osaan. Ensimmäisessä osassa johdatellaan graafiteoriaan sekä lyhimmän polun ongelmaan. Toisessa osassa perehdytään Dijkstran algoritmin toimintaan teoreettisesti sekä esimerkkisuorituksen kautta. Algoritmin suoritusajan analyysin perusteella todettiin, että algoritmin asymptoottinen suoritusaika on liian huono suurille graafeille. Viimeisessä osassa tarkastellaan kontraktiohierarkiaa ja sen kahta eri vaihetta. Hitaassa esikäsittelyvaiheessa graafiin lisätään oikopolkuja, joiden avulla voidaan ohittaa hierarkiassa alempana olevia solmuja. Oikopolut ja alkuperäinen graafi muodostavat yhdessä kontraktiohierarkian. Nopeassa hakuvaiheessa oikopolkuja hyödynnetään pienentämään algoritmin hakuavaruutta, sillä haku tarkastelee vain hierarkiassa ylempänä olevia solmuja.
Empiirisessä analyysissä kontraktiohierarkiaa verrattiin Dijkstran algoritmiin kirjallisuudesta saadulla datalla. Molemmille algoritmeille arvottiin satunnaisesti 100000 alku- ja loppusolmua, joiden välille algoritmit etsivät lyhimmän polun. Euroopan tieverkossa kontraktiohierarkia oli keskimäärin noin 10000 kertaa nopeampi löytämään lyhimmän polun. Samalla käsiteltyjen solmujen määrä oli noin 10000 kertaa pienempi. Tuloksien perusteella voidaan todeta, että kontraktiohierarkia on järkevä tapa nopeuttaa lyhimmän polun etsimistä suuresta graafista.
Työ jakaantuu kolmeen osaan. Ensimmäisessä osassa johdatellaan graafiteoriaan sekä lyhimmän polun ongelmaan. Toisessa osassa perehdytään Dijkstran algoritmin toimintaan teoreettisesti sekä esimerkkisuorituksen kautta. Algoritmin suoritusajan analyysin perusteella todettiin, että algoritmin asymptoottinen suoritusaika on liian huono suurille graafeille. Viimeisessä osassa tarkastellaan kontraktiohierarkiaa ja sen kahta eri vaihetta. Hitaassa esikäsittelyvaiheessa graafiin lisätään oikopolkuja, joiden avulla voidaan ohittaa hierarkiassa alempana olevia solmuja. Oikopolut ja alkuperäinen graafi muodostavat yhdessä kontraktiohierarkian. Nopeassa hakuvaiheessa oikopolkuja hyödynnetään pienentämään algoritmin hakuavaruutta, sillä haku tarkastelee vain hierarkiassa ylempänä olevia solmuja.
Empiirisessä analyysissä kontraktiohierarkiaa verrattiin Dijkstran algoritmiin kirjallisuudesta saadulla datalla. Molemmille algoritmeille arvottiin satunnaisesti 100000 alku- ja loppusolmua, joiden välille algoritmit etsivät lyhimmän polun. Euroopan tieverkossa kontraktiohierarkia oli keskimäärin noin 10000 kertaa nopeampi löytämään lyhimmän polun. Samalla käsiteltyjen solmujen määrä oli noin 10000 kertaa pienempi. Tuloksien perusteella voidaan todeta, että kontraktiohierarkia on järkevä tapa nopeuttaa lyhimmän polun etsimistä suuresta graafista.
Kokoelmat
- Kandidaatintutkielmat [8935]