Lyhimmän polun löytäminen graafissa

Abstract

Lyhimmän polun ongelma on graafimatematiikan keskeisimpiin kuuluva tutkimuskohde. Sille on valtava määrä eri sovelluskohteita, kuten navigointi tiekartalla kaupungista toiseen. Usein sovelluskohteissa graafi on hyvin suuri, ja ratkaisu vaaditaan saada sekunneissa. Tässä työssä luodaan katsaus ongelman perinteiseen ratkaisualgoritmiin ja joihinkin sen tehostamismenetelmiin. Klassinen ratkaisu ongelmaan on Dijkstran algoritmi. Se käy graafin solmuja yksi kerrallaan läpi edeten aina halvimpaan mahdolliseen ja löytää lopulta kohteeseen. Algoritmi ei kuitenkaan ole käytännössä riittävän nopea suurilla graafeilla, sillä sen asymptoottinen tehokkuus on yleisessä tapauksessa neliöllinen. Dijkstran algoritmia voidaan tehostaa muun muassa muuntamalla haku kaksisuuntaiseksi eli aloittamalla etsiminen samanaikaisesti myös toisesta suunnasta. Tämä jopa puolittaa algoritmin suoritusajan. Toinen yksinkertainen tehostustapa on käyttää heuristiikkafunktion tarjoamaa graafin ulkopuolelta tulevaa lisäinformaatiota, jolloin Dijkstran algoritmi muuttuu tehokkaammaksi A*-algoritmiksi. Tuoreimpia lyhimmän polun ongelman ratkaisuun pyrkiviä algoritmeja ovat erilaiset hierarkiamenetelmät, joiden tehostamisvaikutus on hyvin suuri. Hierarkiamenetelmät pyrkivät tunnistamaan graafista sille ominaisia hierarkisia rakenteita ja hyödyntämään niitä. Hierarkiamenetelmissä graafi ensin esikäsittellään, minkä jälkeen graafissa voidaan suorittaa hakuja. Tehokkuus perustuu siihen, että vaikka esikäsittelyyn kuluu aikaa ja muistia, sen jälkeen voidaan suorittaa useampia hakuja tarvitsematta tehdä esikäsittelyä uudelleen. Työssä esitellään kaksi sovelluskohteissa käytössä olevaa hierarkiamenetelmää. Valtatiehierarkiassa graafi jaetaan esikäsittelyssä solmujen tärkeyden mukaan eri kerroksiin. Tämä aiheuttaa sen, että tutkittavien solmujen määrä vähenee, kun alempien hierarkiatasojen solmuja ei tarvitse aina tutkia. Kontraktiohierarkiassa taas jokainen solmu muodostaa oman hierarkiatasonsa. Graafiin luodaan oikoteitä, jolloin lyhimmän polun löytäminen tehostuu. Hierarkiamenetelmät ovat tavallista Dijkstran algoritmia jopa tuhat kertaa tehokkaampia.