Episode Details

Oggi parliamo del Problema del Commesso Viaggiatore che affascina da anni matematici ed informatici.
Pensieri in codice

Attrezzatura utilizzata:
Shure Microfono Podcast USB MV7
Neewer NW-5 Pannello fonoassorbente

Fonti dell’episodio di oggi:
https://en.wikipedia.org/wiki/Travelling_salesman_problem
https://books.google.com/books?id=qbFlMwEACAAJ
https://zs.thulb.uni-jena.de/receive/jportal_jparticle_00248075
https://www.daviddarling.info/encyclopedia/I/Icosian_Game.html
https://docs.lib.purdue.edu/jps/vol1/iss1/4/
https://link.springer.com/article/10.3758/BF03213088
https://link.springer.com/article/10.1007/s10071-011-0463-9
https://www.themarysue.com/bees-havent-solved-traveling-salesman-problem/

Il problema del commesso viaggiatore (anche noto come TSP, dall’inglese “Traveling Salesman Problem”) consiste nell’individuare il percorso più breve che un ipotetico commesso viaggiatore dovrebbe compiere per visitare un certo numero di città, e tornare poi al punto di partenza, senza mai passare due volte per la stessa città.

Si tratta di un problema matematico di ottimizzazione, cioè un problema la cui soluzione consiste nel trovare il valore ottimo di una determinata funzione obiettivo, tenendo in conto specifiche limitazioni, note anche come vincoli.

Lungi dall’essere un semplice artificio matematico, il TSP ha moltissime applicazioni pratiche: una fra tutte è ovviamente la logistica, la pianificazione di percorsi ed itinerari, che migliora notevolmente fattori come il traffico o l’efficienza nella consegna e distribuzione delle merci.

Oltre a questa poi, altri esempi di applicazioni forse un po’ meno intuitivi sono la pianificazione di risorse, la realizzazione di microchip, l’apprendimento di algoritmi di Intelligenza Artificiale, perfino il sequenziamento del DNA.

L’origine del TSP non è chiarissima. Se ne parla addirittura in un libretto di appunti per commessi viaggiatori del 1832, con tanto descrizione del problema ed esempi di tragitti che at