Kauppamatkustajan ongelma

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?

Kauppamatkustajan ongelma on laskennallinen ongelma, joka on erittäin vaikea ratkaista tietoteknisesti.

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

Matemaattisesti ilmaistuna: kun annetaan täydellinen painotettu graafi, etsi graafille 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.

Ongelmalle ei ole helppoja ratkaisuja, mutta ratkaisuilla on merkitystä monella alalla, kuten logistiikassa.