Ci sono voluti 44 anni, ma finalmente ce l’hanno fatta. In un articolo illuminante tre matematici dell’Università di Washington (Nathan Klein, Anna Karlin e Shayan Oveis Gharan) mostrano come trovare una migliore approssimazione per il problema del commesso viaggiatore.
Il problema
Il problema del commesso viaggiatore fu formulato per la prima volta nel 1930, ma è senza dubbio un problema che l’uomo affronta dall’alba dei tempi. Infatti, ci troviamo di fronte ad un quesito assai naturale: data una serie di città, qual è il modo più veloce (ovvero la strada più corta) per un commesso viaggiatore di visitare tutte le città una e una sola volta, e ritornare da dov’è partito? Il problema appartiene alla branca della matematica che chiamiamo ottimizzazione discreta: vogliamo ottimizzare (massimizzare o minimizzare) una quantità, e vogliamo che la soluzione ci arrivi sotto forma di numeri interi. In questo caso specifico, possiamo immaginare che per ogni tratto di strada disponibile il viaggiatore abbia due possibili scelte: percorrerlo o meno. Questo viene matematicamente tradotto tramite una variabile binaria (avente due valori possibili, 0 e 1) che è uguale a 1 se la strada è utilizzata, a 0 se non lo è.
Moltissimi ricercatori hanno studiato, studiano e continueranno a studiare questo problema. Una parte dell’interesse nasce dal fatto che esso può essere utilizzato come banco di prova per lo sviluppo di metodi più generali, da applicare ad una più ampia gamma di problemi di ottimizzazione discreta. Ma già autonomamente, il problema ha innumerevoli applicazioni. Nasce naturalmente come sotto problema nell’ambito di logistica e trasporti, ma il modello è così semplice da poter essere facilmente adattato a molte altre discipline. È stato ad esempio usato per risolvere problemi di sequenziamento del genoma, cablaggio in fibra ottica, foratura dei PCB (circuiti stampati) e, perché no, qualcuno l’ha usato per calcolare il modo più veloce per visitare tutti i pub della Gran Bretagna.
A primo impatto il problema potrebbe sembrare facile, e un metodo per risolverlo appare subito chiaro: provare tutte le possibili combinazioni di percorsi, e prendere infine il più corto. Questo metodo, purtroppo, funziona solamente quando abbiamo a che fare con un insieme assai piccolo di città, diciamo, i capoluoghi di provincia della Sardegna. Ma già considerando i capoluoghi di provincia della Lombardia questo metodo diventa lento e inefficiente: dovremmo infatti controllare milioni di combinazioni diverse!
Il numero di possibili combinazioni è facile da calcolare. Immaginiamo di avere n città in totale e di trovarci nella prima, ovvero la casa del commesso viaggiatore. Abbiamo n-1 scelte su quale sarà la nostra prima città visitata, n-2 per la seconda, n-3 per la terza, e così via, fino ad esaurire l’elenco. L’ordine in cui percorriamo il percorso non influisce sulla lunghezza totale, quindi alla fine dovremo dimezzare il numero di combinazioni ottenuto. Questo significa che con n città a disposizione, abbiamo (n-1)!/2 possibili percorsi.
La difficoltà di risoluzione che cresce di pari passo con il numero di città è conseguenza di un concetto molto più ampio e complicato: il problema è quel che, in teoria della complessità, si definisce NP-hard. Ciò significa, semplificando un po’, che è opinione diffusa che non sia possibile trovare una soluzione esatta, se non con un algoritmo troppo lento perché possa essere utilizzato per casi realisticamente utili. Di fronte all’impossibilità di risolvere un problema efficacemente, i matematici (e in particolare computer scientists e ottimizzatori) si tuffano nella ricerca di una soluzione approssimata, con un nuovo obiettivo: trovare un algoritmo che funzioni per tutte le possibili disposizioni di città e che dia la migliore approssimazione possibile in un tempo ragionevole.
La soluzione di Christofides (1976)
Per il problema del commesso viaggiatore nemmeno questo si rivelò così tanto facile. Si dovette aspettare fino al 1976, quando Christofides, un matematico di Cipro allora professore all’Imperial College di Londra, sviluppò un algoritmo in grado di attaccare il problema.
Per trovare una soluzione, Christofides dapprima costruì l’albero più corto che connette tutte le città, dove un albero è un network che connette tutte le città ma senza creare cicli. Trovare questo network è infatti “facile”, nel senso che esistono algoritmi efficienti in grado di costruirlo. A partire da questo albero, l’algoritmo di Christofides aggiunge archi, ovvero strade tra città, finché non esiste un grande loop che parte da una città, passa una e una sola volta per tutte le altre, e torna alla città di partenza. Vale a dire, finché la strada che il nostro commesso viaggiatore deve percorrere non è delineata.
L’idea fondamentale è che se un tale percorso esiste, ogni città deve avere un numero pari di strade che la raggiungono. Ogni volta che il commesso viaggiatore arriva in una città, vuole poterne partire prendendo una strada differente da quella da cui è arrivato. In altre parole, per ogni città, ogni arrivo è seguito da una partenza, il che significa che ci serve un numero pari di archi che tocchino la città nel network che costruiamo. La buona notizia è che anche l’inverso è vero: in un network in cui ogni città ha un numero pari di strade che la toccano, esiste un percorso che passa per ogni città una e una sola volta e torna alla città di partenza.
L’algoritmo, partendo dal network senza cicli, va ad aggiungere archi alle città con un numero dispari di strade, fintanto che ne esistono. Il percorso che ne esce alla fine non sarà necessariamente il migliore che il nostro commesso viaggiatore possa scegliere, ma non si allontana troppo dalla migliore scelta. Infatti, Christofides dimostrò che il suo metodo crea nel peggiore dei casi un percorso che è al massimo il 50% più lungo del percorso ottimo.
L’algoritmo di Christofides è molto semplice, così semplice che sembrava naturale poter fare di meglio. Tuttavia, per anni i ricercatori hanno cercato di batterlo, e per anni hanno fallito, al punto che in molti hanno iniziato a dubitare della possibilità di poter effettivamente surclassarlo. Dopo 44 anni, finalmente qualcuno è riuscito in questa impresa.
Un nuovo risultato, una nuova speranza
Il nuovo algoritmo è molto simile a quello di Christofides. La differenza fondamentale consiste nel fatto che l’albero da cui si parte non è più il più corto possibile, ma è creato per via di un processo probabilistico e facendo in modo che le città con un numero dispari di strade siano vicine tra loro. Dopodiché l’algoritmo riprende l’originale e aggiunge strade a queste città fino ad ottenere un loop completo.
L’idea è ancora semplice, ma per essere certi del fatto che questo algoritmo ottenesse una migliore approssimazione ci sono voluti anni, strumenti matematici sofisticati (geometria dei polinomi) e 80 pagine di dimostrazione. Il miglioramento consiste in un fattore piccolissimo, qualcosa dell’ordine di un miliardesimo di trilionesimo di trilionesimo. Tuttavia, seppur microscopico, questo progresso abbatte un muro psicologico massiccio: ora tutti sappiamo che un avanzamento è possibile. Questa buona novella ha risvegliato l’interesse di svariati ricercatori che ormai si erano dati per vinti e che ora si dicono determinati a migliorare ancora la soluzione. Chissà cosa riserverà il futuro al nostro viaggiatore: forse riuscirà a tornare a casa ancora prima del previsto.
Bibliografia:
Articolo di Christofides: https://apps.dtic.mil/dtic/tr/fulltext/u2/a025602.pdf
Articolo di Karlin, Klein e Gharan: https://arxiv.org/abs/2007.01409
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Ancora nessun commento