Kauppamatkustajan ongelma
Wikipedia
Kauppamatkustajan ongelma on laskennallinen ongelma, joka on erittäin vaikea ratkaista tietoteknisesti.
Ongelma voidaan kuvata kansantajuisesti seuraavasti: jos kauppamatkustajalla, jonka tarkoituksena on käydä eri kaupungeissa, on käytössään kartta ja aikataulu, ja hän tietää kaupunkien etäisyydet ja millaisia ongelmia eri tieosuuksilla on, voiko hän laskea itselleen automaattisesti nopeimman kulkureitin, jossa palataan lopussa lähtökaupunkiin ja käydään kaikkien tarvittavien kaupunkien kautta ilman, että käydään samassa kaupungissa kahdesti, ja jos voi, miten?
Matemaattisesti ilmaistuna: kun annetaan täydellinen painotettu graafi, laske graafille täydellinen (hamiltonilainen) kulkureitti, jolla on pienin kokonaispainoarvo.
Ongelman voi ratkaista "raa'alla voimalla" (ts. lasketaan kaikki mahdolliset kulkureitit ja valitaan 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(2n). Ongelmamuodossa ("Jos annetaan hinta ja x, päätä, onko olemassa kulkureitti, joka on halvempi kuin x") ongelma on NP-täydellinen.
Ongelmalle ei ole helppoja ratkaisuja, mutta ratkaisuilla on merkitystä monella alalla. Logistiikka on vain yksi käyttökohde. Ongelma on myös kognitiivisen psykologian probleema: miten ihminen voi ratkaista tämän ongelman tehokkaammin kuin tietokone?
