Il problema del commesso viaggiatore spiegato
Dai a un commesso viaggiatore un elenco di città e chiedigli il viaggio più breve che le visiti tutte una volta e torni a casa. Chiunque può verificare un percorso proposto, e chiunque può migliorarne uno cattivo a occhio, eppure nessuno conosce un metodo veloce che trovi sempre il migliore. Il problema del commesso viaggiatore è diventato l'esempio tipico di problema difficile, e i metodi inventati per affrontarlo oggi pianificano consegne, forano circuiti stampati e assemblano genomi.
Il problema
Un giro visita ogni città esattamente una volta e termina dove è iniziato; la sua lunghezza è la somma delle distanze lungo il percorso. Il compito è trovare il giro più breve. Nella versione qui proposta le distanze sono linee rette su una mappa, quindi andare da A a C non è mai più lungo che passare per B: è il problema del commesso viaggiatore metrico. Il rompicapo fu discusso dal matematico Karl Menger intorno al 1930, e il nome si diffuse nei decenni successivi, quando se ne occuparono i matematici della RAND Corporation.
L'esplosione dei percorsi
Fissa la città di partenza. Ci sono n − 1 scelte per la città successiva, n − 2 per quella dopo e così via, e ogni giro può essere percorso in due versi, quindi i giri sono (n − 1)! / 2. Per 10 città sono 181.440, un gioco da ragazzi per un computer. Per 20 sono circa 6 × 10¹⁶, e per 70 superano il numero di atomi dell'universo osservabile. Computer più veloci aiutano poco: ogni città in più moltiplica il lavoro di circa n volte.
NP-difficile
Nel 1972 Richard Karp dimostrò che la domanda se un grafo abbia un giro che passa per tutti i vertici, un ciclo hamiltoniano, appartiene a una famiglia di problemi NP-completi tutti ugualmente difficili. Il problema del commesso viaggiatore la contiene, quindi è NP-difficile. Un metodo veloce per risolverlo darebbe metodi veloci per migliaia di altri problemi di pianificazione, logistica e crittografia. Se un tale metodo esista è la questione P contro NP, uno dei problemi del millennio.
Un metodo esatto: Held–Karp
Nel 1962 Michael Held e Richard Karp, e indipendentemente Richard Bellman, usarono la programmazione dinamica. Per ogni insieme S di città e ogni città j in S, si calcola il cammino più breve che parte dalla città di casa, visita esattamente le città di S e termina in j. Ogni valore si ricava dai valori per S senza j, così la tabella si riempie dagli insiemi piccoli a quelli grandi e alla fine ne esce il giro più breve. Servono circa n² · 2ⁿ passi invece di n!, che per 30 città è la differenza tra pochi minuti e l'età dell'universo, ma la crescita resta esponenziale.
Regole di costruzione rapide
Il vicino più prossimo va sempre alla città più vicina non ancora visitata. È semplice e veloce, ma tende a lasciare indietro alcune città che alla fine vanno raccolte con lunghe deviazioni, per cui i suoi giri sono di solito circa il 25% più lunghi del migliore. I metodi di inserimento invece mantengono un anello chiuso e vi aggiungono le città rimanenti una alla volta dove costano meno. Nel 1976 Nicos Christofides trovò una costruzione che garantisce al massimo 1,5 volte l'ottimo su qualsiasi mappa metrica, un limite rimasto quasi imbattuto per oltre quarant'anni.
Migliorare un giro: 2-opt
La ricerca locale parte da un giro qualsiasi e continua ad apportare piccole modifiche che lo accorciano. La mossa classica, 2-opt, toglie due archi e ricollega i due pezzi nell'altro modo, invertendo il tratto compreso tra loro. Ogni volta che due archi si incrociano, questa mossa li scioglie e fa risparmiare lunghezza, quindi un giro che 2-opt non riesce a migliorare non si incrocia mai. Su mappe casuali i giri 2-opt sono di solito circa il 5% sopra l'ottimo. Mosse più potenti che scambiano tre archi, o il metodo a profondità variabile di Lin e Kernighan del 1973, si avvicinano ancora di più.
Ricottura simulata
La ricerca locale può bloccarsi in un giro in cui ogni singola mossa lo peggiora, anche se esiste un giro molto migliore. La ricottura simulata, applicata a questo problema da Scott Kirkpatrick, Daniel Gelatt e Mario Vecchi nel 1983, prende spunto dalla metallurgia: accetta una mossa peggiore con una probabilità che dipende da una temperatura, alta all'inizio e abbassata lentamente. All'inizio il giro vaga liberamente; alla fine vengono accettati solo i miglioramenti. Con un raffreddamento abbastanza lento trova in modo affidabile giri molto buoni.
Esploralo
Apri la demo del commesso viaggiatore per posizionare fino a 200 città a caso, su un cerchio, a gruppi, su una griglia o dove fai clic. Guarda il vicino più prossimo lasciare indietro le sue ultime città, osserva 2-opt sciogliere ogni incrocio, segui la temperatura della ricottura simulata mentre si raffredda e lascia che Held–Karp dimostri il giro più breve fino a 12 città. Confronta tutti esegue ogni metodo sulla stessa mappa e mostra di quanto ciascun giro supera il più breve trovato.
Domande frequenti
Dove si usa il problema del commesso viaggiatore?
Ovunque qualcosa debba visitare molti luoghi in un ordine efficiente: percorsi di consegna e di raccolta, il tragitto di un trapano o di un laser su un circuito stampato, l'ordine in cui un telescopio osserva le stelle, l'ordine di prelievo in un magazzino e, con distanze diverse, l'ordine dei frammenti nell'assemblaggio di una sequenza di DNA.
Qual è il problema più grande mai risolto esattamente?
Nel 1954 George Dantzig, Ray Fulkerson e Selmer Johnson dimostrarono il giro più breve attraverso 49 città degli Stati Uniti. Nel 2006 il risolutore Concorde di David Applegate, Robert Bixby, Vašek Chvátal e William Cook dimostrò il giro ottimale attraverso 85.900 punti tratti dal progetto di un chip, dopo anni di tempo di calcolo.
Il giro più breve è sempre privo di incroci?
Sì, su una mappa piana con distanze in linea retta. Se due archi si incrociassero, sostituirli con due lati del quadrilatero che formano accorcerebbe il giro, quindi un giro con incroci non può essere il più breve.
Le euristiche danno sempre lo stesso giro?
Il vicino più prossimo, l'inserimento più economico e 2-opt, come sono usati qui, sono deterministici: sulle stesse città danno lo stesso giro. La ricottura simulata parte da un giro casuale e fa mosse casuali, quindi due esecuzioni possono finire con giri diversi, di solito di lunghezza quasi uguale.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Apri la demo del commesso viaggiatore