TSP-ongelman ratkaisuyritelmiä
Triviaaliratkaisu: Kokeillaan n kaupungin kartalla kaikki n! mahdollista reittiä ja valitaan niistä lyhin.
Ei onnistu käytännössä: jos esim. n = 22, niin n! on noin 1021. Jos pystyttäisiin tutkimaan esim. 1 reitti millisekunnissa, vaatisi kaikkien reittien tutkiminen noin 36 miljardia vuotta. (Nykykäsityksen mukaan on maailmankaikkeuden tähänastinen ikä 10-20 miljardia vuotta.)
Parannusidea: Ostetaan nopeampi tietokone: esimerkiksi miljoonan prosessorin rinnakkaiskone, jonka kukin prosessori tutkii yhden reitin nano-sekunnissa.
Ei auta: 20 mrd vuotta riittää silti vasta 30 kaupungin karttoihin.
Parempi idea: keksitään tehokkaampi algoritmi.
- rajoitusheuristiikat, ”simuloitu jäähdytys”, ”geneettiset algoritmit”
- auttavat muutamien kymmenien (joskus satojen) kaupunkien tapauksiin asti, mutta eivät pidemmälle