Portale:Informatica/Voce della settimana/Settimana 2
Il problema del commesso viaggiatore, o TSP (dall'inglese Traveling Salesman Problem) è un problema di teoria dei grafi, uno dei casi di studio tipici dell'informatica teorica e della teoria della complessità.
Il nome nasce dalla sua più tipica rappresentazione: data una rete di città, connesse tramite delle strade, trovare il percorso di minore distanza che un commesso viaggiatore deve seguire per visitare tutte le città una e una sola volta.