Cinquantamila.it La storia raccontata da Giorgio Dell'Arti

Il commesso viaggiatore e il dilemma del percorso più breve. Nova Il Sole 24 Ore 9 febbraio 2006. Socrate sa di non sapere come rendere più corti i suoi viaggi. Quando infatti progetta un itinerario turistico e desidera visitare diverse località, riesce solo con fatica a determinare il tragitto più breve che collega tutte le tappe di suo interesse. Il problema ha in matematica un nome preciso, ossia quello del commesso viaggiatore. Ogni rappresentante di commercio, ogni volta che visita i suoi clienti in posti diversi, deve progettare un percorso che sia il più breve possibile, per ottimizzare i suoi spostamenti e risparmiare tempo e benzina. Il metodo più semplice per definire l’itinerario migliore è quello di disegnare tutti i percorsi possibili, misurarli, e quindi scegliere il più corto. Il problema però è che il numero degli itinerari cresce enormemente con l’aumentare delle tappe. Se a 4 diversi luoghi corrispondono infatti 24 differenti percorsi ( provare per credere!), gli itinerari possibili salgono a 120 se i clienti sono cinque, superano i 3,6 milioni se sono dieci, e diventanomiliardi di miliardi se sono 20. Da un punto di vista matematico, la quantità di itinerari possibili corrisponde al fattoriale del numero delle tappe, un valore che si calcola moltiplicando quest’ultimo numero per tutti i valori interi più piccoli. Così, ad esempio, il fattoriale di 4 è uguale a 4 x 3 x 2 x 1, ossia 24. L’operazione fattoriale genera numeri enormi: nel caso di cento città, per esempio, la quantità di percorsi possibili si rappresenta con un numero che contiene 157 cifre. Se poi si prendono in esame percorsi costituiti da migliaia o centinaia di migliaia di città, anche i calcolatori più potenti non riescono ad esaminare tutti i tragitti possibili, ed è quindi necessario utilizzare tecniche matematiche più raffinate. Non esiste quindi un’unica formula semplice che permetta di risolvere il problema del commesso viaggiatore, e per la sua risoluzione si utilizzano procedure di calcolo sia esatte che approssimate. Le prime forniscono sicuramente il tragitto migliore, ma non possono essere utilizzate per problemi troppo complessi; le seconde danno in tempi sufficientemente brevi soluzioni che " probabilmente" sono tra le migliori. Di anno in anno, però, migliora il record del percorso migliore che collega il maggior numero possibile di città. Nel 2001 fu risolto ad esempio il problema per 15.112 cittadine tedesche; nel 2004 quello relativo a 24.978 località svedesi, dove " risolvere il problema" significa dimostrare che il percorso trovato è il più breve. Un progetto internazionale sta anche tentando di calcolare il tragitto ottimale per collegare tutte le località del mondo, ossia per programmare un viaggio con 1.904.711 tappe. Socrate sa di non sapere come rendere più corti i suoi viaggi, ma la loro durata diminuisce di anno in anno. Andrea Carobene

NOVA IL SOLE 24 ORE 09/02/2006