Grafice și rețeleSalesman

Până acum am ignorat faptul că unele orașe ar putea fi mai departe de altele. În viața reală, însă, aceasta este o considerație foarte importantă: nu dorim doar să găsim vreo cale, ci vrem să o găsim pe cea mai scurtă. Aceasta se numește Travelling Travelling Problem . Trebuie rezolvat nu numai în transport și logistică, ci și atunci când poziționați tranzistoarele pe microcipuri, pentru a face computere mai rapide sau când analizați structura ADN-ului .

O metodă simplă ar fi să încercați toate căile posibile, găsind lungimea fiecăreia, apoi selectând cea mai scurtă. Cu toate acestea, tocmai am arătat asta, chiar și cu doar ${tsn2} orașe există ${tsn2} ! = ${factorial(tsn2)} căi posibile. După ce ai sute sau mii de vertexuri, încercarea tuturor căilor posibile devine imposibilă, chiar și folosind computere puternice.