Problema del commesso viaggiatore: differenze tra le versioni

Il '''problema del commesso viaggiatore''', o '''TSP''' (dall'[[inglish]] ''Travelling Salesman Problem'' o, se preferite, dal romanesco ''Tanto S'è Perso'') è un problema di teoria dei grafi, uno dei casi di studio tipici dell'[[informatica]] teorica, scienza che si occupa di concepire programmi che non servono a [[nulla]], tipo quelli del [[Programma Di Governo|governo]]. È oggetto di interesse anche per gli studiosi della [[teoria della complessità]], che fanno sicuramente qualcosa di troppo complicato da capire e quindi ce ne freghiamo. Il nome nasce dalla sua più tipica enunciazione:

{{cit2|Data una rete di città, connesse tramite delle strade, trovare il percorso ottimale che un commesso viaggiatore deve seguire per visitare tutte le [[città]] una e una sola volta, che la benzina costa uno sproposito per colpa delle [[Accisa|accise]] e tende a finire.|Brian Amedeo Kernighan, primo enunciatore, mentre va a piedi al distributore più vicino con un tanica in mano.}}