3. sija, kansainvälinen sarja:

Ville Syrjänen

Extending the Dijsktra Algorithm for the Dynamic Shortest Path Problem

18-vuotias Ville Syrjänen opiskelee Helsingin Suomalaisessa Yhteiskoulussa.

Ville käsittelee kilpailutyössään klassisesta verkkoteoriasta tuttua lyhimmän polun ongelmaa ja kehittää sille uuden ratkaisualgoritmin. Ville on tutkinut, mitä tapahtuu, kun kaarien painot tunnetussa Dijsktran algoritmissa ovat vakioiden sijaan ajan funktioita, ja soveltanut tätä dynaamisen lyhimmän polun ongelmaan. Dijkstran algoritmi on klassinen algoritmi, joka muodostaa pohjan monelle muulle algoritmille. Se etsii graafille lyhimmän polun yhdestä pisteestä kaikkiin muihin pisteisiin, ja sitä käytetään muun muassa tietoliikenneverkkojen reitityksessä.  

”Päädyin tutkimaan juuri tätä aihetta aika hassun sattuman kautta. Katsoin, mitä tapahtuu, jos Dijkstran algoritmissa verkon kaarien painot ovatkin funktioita vakioiden sijaan. Vasta sen jälkeen löysin kirjastosta tämän aiheen nimen. Oikeastaan kehitin siis algoritmia jo ennen kuin tiesin, että on edes olemassa dynaamisen lyhimmän polun ongelma”, kertoo Ville.

Ratkaisualgoritmia voidaan hyödyntää esimerkiksi liikenteen reitityksessä

Lähteenä tutkimuksessa on käytetty Dijsktran alkuperäistä julkaisua, tieteellisiä artikkeleita ja verkkoteorian oppikirjoja. Työssä esittämänsä todistukset ja analyysit Ville toteutti itsenäisesti. Työn ohjaajalta, matematiikan opettajaltaan Jarmo Hurrilta hän sai apua aiheen tarkentamiseen, käsitteiden määrittelyyn ja tekstin selkeyttämiseen.

Villen työssään kehittämää ratkaisualgoritmia voidaan soveltaa käytäntöön esimerkiksi liikenteen reitityksessä. Kun tiedetään etukäteen, kuinka paljon aikaa vaikkapa työmatkan kunkin osan kulkemiseen kuluu eri kellonaikoina, algoritmi kertoo lähtöajan perusteella nopeimman työmatkareitin.

Arvioijien kommentit

Arvioijien mukaan Villen aihe on hyvin haastava. Aiheen käsittely on puhtaan teoreettista ja vaatii tutkijaltaan huomattavaa matemaattista lahjakkuutta. Uuden, innovatiivisen ratkaisualgoritmin kehittäminen on osoitus kirjoittajan luovuudesta. Uusi algoritmi on johdettu huolellisesti, ja sen toimintaa on havainnollistettu yksinkertaisen esimerkin avulla. Villen kehittämällä algoritmilla on useita merkittäviä käytännön sovellustapoja esimerkiksi tietoliikenne- tai tieverkkoja suunniteltaessa.

Ulkoasultaan kilpailutyö muistuttaa ammattitutkijan artikkelia. Tutkimusmenetelmät on valittu huolella, työ on hyvin kirjoitettu ja tiivistelmä kuvailee tarkasti työn sisällön tavoitteineen. Tekijä on osannut myös tarkastella kehittämiään menetelmiä kriittisesti. Villellä on ammattimainen ote tutkimustyöhön, ja hän hallitsee matemaattisen todistustekniikan erinomaisesti.

Villen harrastukset: Shakki, punttisalilla käyminen