Descrizione
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 attraversavano la Germania e la Svizzera. Anche se l’intenzione di tali appunti era chiaramente di risoluzione pratica, non di studio teorico, vista la completa assenza di dettagli matematici.
Sempre nel diciannovesimo secolo, però, il matematico, fisico e astronomo irlandese William Hamilton, inventò un gioco, the icosian game, che consisteva nell’unire tutti i vertici di un dodecaedro con un unica linea continua chiusa. E, guarda caso, la soluzione di tale gioco era proprio la soluzione al problema del commesso viaggiatore prendendo in considerazione 20 città.
Ad ogni modo, i primi studi veri e propri sul TSP iniziarono negli anni ‘30 del secolo scorso e fu subito chiaro che il problema in questione fosse di tipo cosiddetto NP-completo: cioè, in primo luogo, si tratta di un è problema che non può essere risolto in modo efficiente; e, oltre a ciò, ha la caratteristica che qualsiasi altro problema NP può essere può essere matematicamente trasformato in un’istanza del TSP.
Queste sue caratteristiche lo resero immediatamente abbastanza famoso nei circoli matematici e la sua fama crebbe ancora, quando, negli anni ‘50 e ‘60 iniziarono ad essere offerti premi in denaro a chi fosse riuscito a risolverlo in maniera efficiente.
Nonostante tali incentivi, però, ad oggi il TSP è ancora un problema privo di una soluzione efficiente: l’unico modo per ottenere la soluzione esatta, infatti, è tracciare tutti i possibili percorsi e valutarne il migliore, ma è chiaro che se parliamo di 3 o 4 città è un conto, mentre consideriamo, ad esempio, 150 città, il carico di lavoro diventa praticamente ingestibile.
Il risultato di ciò è che, attualmente, per la risoluzione del TSP per quantità importanti di nodi vengono utilizzati degli algoritmi euristici, cioè algoritmi la cui soluzione è solo probabilmente esatta: cioè che non assicurano che essa sia quella ottima.
Negli ultimi anni, il problema del commesso viaggiatore ha iniziato ad attirare attenzione anche al di fuori della comunità matematica ed informatica. In particolare sono stati condotti studi su esseri viventi per determinare la loro capacità di trovare la soluzione ottima.
Gli esseri umani, ad esempio, sono risultati particolarmente adatti, riuscendo ad individuare rapidamente, a colpo d’occhio, soluzioni molto vicine a quella ottima, con una perdita di efficienza di circa l'1% in caso di 10 o 20 nodi e che saliva fino all'11% in caso di 120 nodi.
Anche studi condotti sui piccioni, hanno mostrato come essi siano in grado di pianificare itinerari complessi e quasi ottimali per visitare in modo efficiente una serie di mangiatoie. Dimostrando come anche tali animali vantino abilità naturali nell’avvicinarsi alla soluzione ottima del TSP.
Negli anni ‘10 la fama del problema del commesso viaggiatore raggiunse perfino le grandi masse. La stampa generalista diffuse infatti la notizia che gli esemplari di alcune specie di api fossero in grado istintivamente di risolvere il problema del commesso viaggiatore, con titoli del calibro di “Il piccolo cervello delle api batte i computer”.
Sarebbe stato bello, ma in effetti si trattò semplicemente di una cattiva interpretazione del paper di una ricerca scientifica.
Le api, infatti, si sono dimostrate abili nello spostarsi da un fiore all’altro scegliendo il percorso più breve, questo è vero, ma ciò è ben lontano dall’essere in grado di risolvere il problema del commesso viaggiatore. In più, non essendo noi stessi in grado di calcolare l’ottimo percorso tra centinaia o addirittura migliaia di fiori utilizzando un computer, come potremmo giudicare se quello effettuato da un ape sia effettivamente l’ottimo o meno?
Sostieni il progetto
Sostieni tramite SatispaySostieni tramite Revolut
Sostieni tramite PayPal
Sostieni utilizzando i link affiliati di Pensieri in codice: Amazon, Todoist, Readwise Reader Proton Mail, Proton VPN, Proton Pass, Satispay
Partner
GrUSP (Codice sconto per tutti gli eventi: community_PIC)Schrödinger Hat
Crediti
Sound design - Alex RaccugliaVoce intro - Maria Chiara Virgili
Voce intro - Spad
Musiche - Kubbi - Up In My Jam, Light-foot - Moldy Lotion, Creativity, Old time memories
Suoni - Zapsplat.com
Cover e trascrizione - Francesco Zubani
Mostra testo dell'episodio
Quello che segue è lo script originale dell'episodio.
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 attraversavano la Germania e la Svizzera. Anche se l’intenzione di tali appunti era chiaramente di risoluzione pratica, non di studio teorico, vista la completa assenza di dettagli matematici.
Sempre nel diciannovesimo secolo, però, il matematico, fisico e astronomo irlandese William Hamilton, inventò un gioco, the icosian game, che consisteva nell’unire tutti i vertici di un dodecaedro con un unica linea continua chiusa. E, guarda caso, la soluzione di tale gioco era proprio la soluzione al problema del commesso viaggiatore prendendo in considerazione 20 città.
Ad ogni modo, i primi studi veri e propri sul TSP iniziarono negli anni ‘30 del secolo scorso e fu subito chiaro che il problema in questione fosse di tipo cosiddetto NP-completo: cioè, in primo luogo, si tratta di un è problema che non può essere risolto in modo efficiente; e, oltre a ciò, ha la caratteristica che qualsiasi altro problema NP può essere può essere matematicamente trasformato in un’istanza del TSP.
Queste sue caratteristiche lo resero immediatamente abbastanza famoso nei circoli matematici e la sua fama crebbe ancora, quando, negli anni ‘50 e ‘60 iniziarono ad essere offerti premi in denaro a chi fosse riuscito a risolverlo in maniera efficiente.
Nonostante tali incentivi, però, ad oggi il TSP è ancora un problema privo di una soluzione efficiente: l’unico modo per ottenere la soluzione esatta, infatti, è tracciare tutti i possibili percorsi e valutarne il migliore, ma è chiaro che se parliamo di 3 o 4 città è un conto, mentre consideriamo, ad esempio, 150 città, il carico di lavoro diventa praticamente ingestibile.
Il risultato di ciò è che, attualmente, per la risoluzione del TSP per quantità importanti di nodi vengono utilizzati degli algoritmi euristici, cioè algoritmi la cui soluzione è solo probabilmente esatta: cioè che non assicurano che essa sia quella ottima.
Negli ultimi anni, il problema del commesso viaggiatore ha iniziato ad attirare attenzione anche al di fuori della comunità matematica ed informatica. In particolare sono stati condotti studi su esseri viventi per determinare la loro capacità di trovare la soluzione ottima.
Gli esseri umani, ad esempio, sono risultati particolarmente adatti, riuscendo ad individuare rapidamente, a colpo d’occhio, soluzioni molto vicine a quella ottima, con una perdita di efficienza di circa l'1% in caso di 10 o 20 nodi e che saliva fino all'11% in caso di 120 nodi.
Anche studi condotti sui piccioni, hanno mostrato come essi siano in grado di pianificare itinerari complessi e quasi ottimali per visitare in modo efficiente una serie di mangiatoie. Dimostrando come anche tali animali vantino abilità naturali nell’avvicinarsi alla soluzione ottima del TSP.
Negli anni ‘10 la fama del problema del commesso viaggiatore raggiunse perfino le grandi masse. La stampa generalista diffuse infatti la notizia che gli esemplari di alcune specie di api fossero in grado istintivamente di risolvere il problema del commesso viaggiatore, con titoli del calibro di Il piccolo cervello delle api batte i computer.
Sarebbe stato bello, ma in effetti si trattò semplicemente di una cattiva interpretazione del paper di una ricerca scientifica.
Le api, infatti, si sono dimostrate abili nello spostarsi da un fiore all’altro scegliendo il percorso più breve, questo è vero, ma ciò è ben lontano dall’essere in grado di risolvere il problema del commesso viaggiatore. In più, non essendo noi stessi in grado di calcolare l’ottimo percorso tra centinaia o addirittura migliaia di fiori utilizzando un computer, come potremmo giudicare se quello effettuato da un ape sia effettivamente l’ottimo o meno?
Nascondi