BROADCASTS.com

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

Sostieni tramite Satispay
Sostieni tramite PayPal

Sostenitori di oggi:
Edoardo Secco, Carlo Tomas

---

Sostieni utilizzando i link affiliati di Pensieri in codice:
Amazon Todoist ProtonMail ProtonVPN Satispay

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

Crediti:
Sound design - Alex Raccuglia
Voce intro - Maria Chiara Virgili
Voce intro - Spad
Musiche - Kubbi - Up In My Jam, Light-foot - Moldy Lotion, Creativity, Old time memories
Suoni - Zapsplat.com

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\\xf9 breve che un ipotetico commesso viaggiatore dovrebbe compiere per visitare un certo numero di citt\\xe0, e tornare poi al punto di partenza, senza mai passare due volte per la stessa citt\\xe0.

Si tratta di un problema matematico di ottimizzazione, cio\\xe8 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 \\xe8 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 \\xe8 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\\xf2, il matematico, fisico e astronomo irlandese William Hamilton, invent\\xf2 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\\xe0.

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\\xe8, in primo luogo, si tratta di un \\xe8 problema che non pu\\xf2 essere risolto in modo efficiente; e, oltre a ci\\xf2, ha la caratteristica che qualsiasi altro problema NP pu\\xf2 essere pu\\xf2 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\\xf2, ad oggi il TSP \\xe8 ancora un problema privo di una soluzione efficiente: l\'unico modo per ottenere la soluzione esatta, infatti, \\xe8 tracciare tutti i possibili percorsi e valutarne il migliore, ma \\xe8 chiaro che se parliamo di 3 o 4 citt\\xe0 \\xe8 un conto, mentre consideriamo, ad esempio, 150 citt\\xe0, il carico di lavoro diventa praticamente ingestibile.

Il risultato di ci\\xf2 \\xe8 che, attualmente, per la risoluzione del TSP per quantit\\xe0 importanti di nodi vengono utilizzati degli algoritmi euristici, cio\\xe8 algoritmi la cui soluzione \\xe8 solo probabilmente esatta: cio\\xe8 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\\xe0 matematica ed informatica. In particolare sono stati condotti studi su esseri viventi per determinare la loro capacit\\xe0 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\\xe0 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\\xf2 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\\xf9 breve, questo \\xe8 vero, ma ci\\xf2 \\xe8 ben lontano dall\'essere in grado di risolvere il problema del commesso viaggiatore. In pi\\xf9, 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?
'