Kauppamatkustajan ongelma

Kauppamatkustajan ongelma on tietotekniikassa kenties tunnetuin laskennallinen ongelma, ja myös helpoimpia ”maallikolle” selitettäviä alan tärkeitä kysymyksiä.

Jos kauppamatkustaja aloittaa pisteestä A ja jos kaikki kahden pisteen väliset etäisyydet tiedetään, mikä on lyhin reitti, joka käy kaikissa pisteissä ja palaa pisteeseen A?

Ongelma voidaan kuvata kansantajuisesti seuraavasti: jos kauppamatkustaja tietää kaupunkien keskinäiset etäisyydet, miten hän voi laskea itselleen nopeimman (lyhimmän, halvimman) kulkureitin, jossa palataan lopussa lähtökaupunkiin ja käydään kaikkien muiden kaupunkien kautta tasan kerran?

Ongelman teoriassa ratkaiseva tietokoneohjelma sinänsä on helppo tehdä. Ongelma kuuluu joukkoon tehtäviä, joille oletetaan olevan mahdotonta laatia "käytännössä laskettavissa olevaa" ratkaisualgoritmia, joskaan tätä ei ole todistettu. Käytännössä laskettava tarkoittaa tässä sitä, että suoritusaika kasvaisi kaupunkien määrän kasvaessa enintään polynomiaalisesti, esimerkiksi siten, että kaupunkien määrän $n$ -kertaistuessa suoritusaika kasvaisi $n^{2}$ -kertaiseksi tai $n^{3}$ -kertaiseksi.

Matemaattisesti kuvattuna ongelmassa on annettu täydellinen painotettu graafi, jolle pitää etsiä Hamiltonin kierros, jolla on pienin kokonaispaino.

Ongelman voi ratkaista laskemalla kaikki mahdolliset kulkureitit ja valitsemalla nopein, mutta jos graafin solmuja (kaupunkeja) on $n$ kappaletta, tähän ratkaisuun vaaditaan $(n-1)!$ permutaatiota, joten tämä ratkaisu muuttuu nopeasti epäkäytännölliseksi solmumäärän kasvaessa. Dynaamisen ohjelmoinnin kautta paras mahdollinen aikakompleksisuusluokka on $O(2^{n})$ . Kyllä/ei-ongelmamuodossa ("Jos joukosta valitaan reitti x, jonka hinta tiedetään, onko olemassa kulkureitti, joka on halvempi kuin x?") ongelma on NP-täydellinen.

Ratkaisuilla on merkitystä monella alalla, kuten logistiikassa. Vaikka täydellistä ratkaisua ei todennäköisesti voida laskea, on olemassa ohjelmia, jotka etsivät käytännössä riittävän hyviä reittejä.

Esimerkki. Puutarhaan on istutettu 16 kasvia säännölliseen ruudukkoon, ja puutarhurin on käytävä kunkin kasvin luona ja poistuttava tulopaikan kautta. Tässä tapauksessa on selvää, että optimaalinen ratkaisu on se, jossa kukin siirtymä on yhtä suuri kuin kahden vierekkäisen kasvin väli (tässä merkitty luvulla 1). Alla olevissa kuvissa viimeinen siirtymä on jätetty piirtämättä.

Eräs optimaalinen ratkaisu on:

 o->o——o——o
          |
 o  o——o——o
 |  |            kuljettu matka = 15 + 1
 o  o——o——o
 |        |
 o——o——o——o

Eräs huonompi ratkaisu on:

 o->o——o——o
          |
 o——o——o——o
 |               kuljettu matka = 15 + 3
 o——o——o——o
          |
 o——o——o——o

Kirjallisuutta muokkaa

Ruohonen, Keijo: Graafiteoria. Opintomoniste 136. Tampere: TTKK, 1990. ISBN 951-721-530-4.