Kiinalainen postinkantajaongelma

Abstract

Kiinalaisessa postinkantajaongelmassa (engl. Chinese Postman Problem) etsitään lyhintä mahdollista reittiä, joka postinkantajan täytyy kulkea, jotta hän voi jakaa postin alueensa jokaiselle kadulle ja palata lopuksi takaisin aloituspisteeseen. Tässä tutkielmassa tarkastellaan kiinalaista postinkantajaongelmaa optimointiongelmana ja esitetään yksi tapa löytää siihen ratkaisu.

Ennen ongelman käsittelyä esitellään graafiteorian peruskäsitteitä ja tutkielman aiheen kannalta keskeisimpiä määritelmiä, kuten graafi, multigraafi, painotettu graafi, solmun aste ja solmujen välinen reitti. Lisäksi esitellään Eulerin graafin määritelmä ja todistetaan tutkielman kannalta olennainen tulos, jonka mukaan graafi on Eulerin graafi, jos ja vain jos sen jokaisen solmun aste on parillinen.

Kolmannessa luvussa taustoitetaan tutkielman aihetta esittelemällä Königsbergin siltaongelma, joka voidaan tulkita myös kiinalaisen postinkantajaongelman erityistapaukseksi. Leonhard Euler esitti ensimmäisenä ratkaisun Königsbergin siltaongelmaan vuonna 1735, ja tätä pidetään usein koko graafiteorian alkuna.

Tutkielman pääluvussa esitellään kiinalainen postinkantajaongelma ja sen määrittely optimointiongelmana. Tämän jälkeen esitellään ongelman algoritmisen ratkaisun idea yleisesti, minkä jälkeen esitetään ratkaisun eri vaiheissa käytettävät algoritmit ja esimerkit niiden käytöstä. Ratkaisun ensimmäisessä vaiheessa graafin paritonasteisten solmujen väliset reitit ja niiden pituudet etsitään Dijkstran algoritmilla. Toisessa vaiheessa etsitään pienimmän mahdollisen painon sovitus unkarilaisella algoritmilla. Lopuksi kolmannessa vaiheessa etsitään Eulerin piiri, joka on ongelman ratkaisu. Kaikkia ratkaisun vaiheita havainnollistetaan esimerkkien lisäksi kuvien avulla.