Kauppamatkustajan ongelma
Annettu n kaupungin (täydellinen) etäisyystaulukko D[1..n, 1..n]. Tehtävänä on löytää lyhin sellainen kaupunkikierros, joka kulkee täsmälleen kerran kunkin kaupungin kautta -- siis sellainen lukujen 1,…,n permutaatio p(1),…,p(n), joka minimoi kustannuksen
c(p) = å1n-1 D[p(i), p(i+1)] + D[p(n), p(1)].
Tämä ”kauppamatkustajan ongelma” (engl. TSP = ”traveling salesman problem”) esiintyy jossain muodossa lukuisissa käytännön sovelluksissa: jakeluautojen reittisuunnittelussa, piirilevyjen porauksessa, rinnakkaistietokoneiden töiden-järjestelyssä, DNA-jonojen sekvenoinnissa jne.
Vaikka ongelma päällisin puolin hieman muistuttaa lyhimpien reittien määritysongelmaa, se on huomattavasti vaikeampi.