Il problema del commesso viaggiatore interessa da anni la comunità matematica. La semplice formulazione nasconde delle enormi difficoltà computazionali. Ce ne parla Marco Menale.

La ricerca matematica procede attraverso la formulazione di problemi, come quello del commesso viaggiatore. Alcuni trovano soluzione in un tempo breve, per altri non bastano decenni. L’8 agosto 1900 si tiene a Parigi il Congresso internazionale dei matematici ed il matematico tedesco David Hilbert propone una lista di 23 problemi. Alcuni di questi, come l’ipotesi di Riemann, sono tuttora irrisolti. E sono solo alcuni tra i casi più noti.

Alcuni problemi potrebbero essere all’apparenza meno noti ma molto più frequenti di quanto si immagina, come il problema del commesso viaggiatore, noto con la sigla TSP dall’inglese Travelling Salesman Problem. La prima formulazione matematica si deve al matematico irlandese Sir William Rowan Hamilton, padre della meccanica analitica e della teoria dei quaternoni, inventore del gioco icosiano.  Negli anni trenta del XX secolo vari ricercatori, tra cui Karl Menger, Merrill Flood e Hassler Whitney ne cominciano uno studio sistematico. Nel 1949 appare per prima volta l’espressione traveling salesman problem in un articolo della matematica americana Julia Robinson. Da quel momento il TSP è uno dei problemi più studiati in Ricerca Operativa, riformulato come problema di programmazione lineare da George Dantzig, Delbert Ray Fulkerson e Selmer Johnson. Trovarne l’origine esatta è un’impresa ardua; questo problema è vecchio come il mondo.

Una possibile formulazione è la seguente. C’è un rappresentante di pellame che deve muoversi tra \(n\) città per vendere la sua merce. Partendo da una delle città, il commesso viaggiatore deve visitarle tutte una ed una sola volta per poi tornare al punto di partenza. Note le distanze tra le città, qual è la strada che minimizza i chilometri percorsi dal commesso? In apparenza il problema sembra semplice se confrontato alla formulazione di uno dei problemi del millennio, come l’esistenza e la regolarità delle soluzioni delle equazioni di Navier-Stokes.

Siamo portati ingenuamente a risolverlo elencando tutti i possibili percorsi. A questo punto confrontiamo le distanze ed otteniamo la più breve. Ma facciamo due conti. Partiamo da n città. Quindi la città di partenza può essere scelta tra tutte le \(n\) da visitare. Fissata questa prima, la seconda città può essere scelta tra le \(n-1\) restanti, la terza tra le \(n-2\) restanti. Così procedendo, abbiamo un’unica città per l’ultima scelta. In definitiva, il numero di percorsi è dato da

\[n\cdot (n-1)\cdot (n-2)\cdot (n-3)\cdot…\cdot 3\cdot 2\cdot 1=n!,\]

ossia il fattoriale di \(n\).

Tutto risolto? In apparenza sì. Purtroppo la funzione fattoriale cresce più velocemente di qualsiasi esponenziale. Quindi un algoritmo che risolve il problema del commesso viaggiatore seguendo questa strategia avrebbe una durata più che esponenziale. Si tratta di tempi lunghissimi. In sostanza non otterremo mai la risposta. Supponiamo che ogni tentativo duri \(1\) millesimo di secondo. Per \(7\) città abbiamo bisogno di \(5\) secondi per verificare tutti i possibili percorsi. Già con \(10\) abbiamo bisogno di più di un’ora. E se le città sono \(20\) servono \(77\) milioni di anni. E se consideriamo un supercomputer che valuta ogni percorso in \(10^-{12}\) secondi? Con \(28\) città quasi non basterebbe tutta la storia dell’universo.

L’algoritmo di Held-Karp (1962) descrive il percorso più breve in un tempo esponenziale compreso tra \(2^n\) e \(3^n\). Da quel momento non sono più stati fatti significativi passi in avanti, almeno dal punto di vista teorico. A livello computazionale sono stati risolti anche problemi più grandi utilizzando, tra gli altri, l’algoritmo di Christofides. Di tanto in tanto arriva qualche articolo che propone con strumenti diversi qualche piccolo miglioramento. Ci sono classi di algoritmi che scartano alcuni percorsi apriori a causa della loro non-ottimalità. È il caso degli algoritmi di branch and bound e degli algoritmi di branch and cut. In un lavoro del 2014 è risolto il problema TSP con \(100.000\) città. Tuttavia ci sarà sempre un’applicazione del TSP ad un numero maggiore di città, come recentemente fatto su scala galattica da David Applegate, Robert Bixby, Vašek Chvátal , William Cook, Marcos Goycoolea e Keld Helsgaun (qui per approfondire).

Il problema del commesso viaggiatore continua ad impegnare i matematici ed informatici. Non possiamo sapere se ci sarà mai un algoritmo efficienti o se questo algoritmo semplicemente non esiste. La risoluzione del problema avrebbe grosse ricadute, basta pensare ai problemi di logistica dei nostri tempi. Addirittura potrebbe aiutarci a trovare il birra tour perfetto tra i pub inglesi.

 

[Illustrazione di Luca Manzo]