TSP: di commessi viaggiatori e ottimizzazione

Supponiamo che venga assegnato il seguente problema. Viene mostrato un insieme di n punti sul piano, che chiameremo città. Viene chiesto di iniziare da una qualsiasi delle città e tracciare una linea ininterrotta che attraversi ciascuna delle altre città esattamente una volta e torni al punto di partenza. Tale linea è chiamata circuito e un esempio di soluzione per 20 città è mostrato nella figura. Tutto quello che bisogna fare è trovare il circuito più breve possibile.

Questo è un esempio del problema del commesso viaggiatore, o TSP (Traveling Salesman Problem). Le origini del problema non sono chiare. Un manuale per venditori ambulanti del 1832 lo menziona e include esempi di tour attraverso la Germania e la Svizzera, ma non contiene alcuna trattazione matematica. Una prima trattazione relativa a problemi simili a questo si deve all’irlandese William R. Hamilton (sì, quello dei quaternioni, il vandalo del ponte di Dublino) e al britannico Thomas P. Kirkman.

L’Icosian Game di Hamilton è un rompicapo ricreativo basato sulla ricerca di un circuito hamiltoniano lungo gli spigoli di un dodecaedro, cioè un percorso tale che ogni vertice venga visitato una sola volta, nessuno spigolo sia percorso due volte e il punto finale sia lo stesso del punto iniziale (ma ovviamente senza il vincolo del percorso più breve). Il puzzle fu distribuito commercialmente come un pannello di legno con fori ai 20 nodi di un grafo dodecaedrico e pedine numerate. Hamilton lo vendette a un produttore di giochi londinese nel 1859 per 25 sterline (circa 3.220 sterline di oggi). Fu un affare per Hamilton, perché il gioco, giudicato troppo facile, fu un insuccesso in tutte le versioni in cui venne proposto.

 

Il problema combinatorio di Kirkman, il quale passò alla storia più per questo rompicapo del 1850 che per i suoi grandi contributi alla teoria dei gruppi, è noto come Fifteen Schoolgirls Problem:

"Quindici fanciulle di una scuola escono affiancate tre alla volta per sette giorni di seguito: è necessario sistemarle ogni giorno in modo che due non camminino mai fianco a fianco più di una volta”.

 

Il problema del commesso viaggiatore vero e proprio fu formulato per la prima volta in forma generale nel 1930 dal geometra e topologo austriaco Karl Menger in un articolo in cui proponeva una nuova definizione della lunghezza di un arco:

 

“La lunghezza di un arco può essere definita come il minimo limite superiore dell'insieme di tutti i numeri che si potrebbero ottenere prendendo ogni insieme finito di punti della curva e determinando la lunghezza del grafo poligonale più corto che unisce tutti i punti. (…) Lo chiamiamo problema del messaggero (poiché in pratica questa questione dovrebbe essere risolta da ogni postino, comunque anche da molti viaggiatori): il compito è trovare, per un numero finito di punti di cui si conoscono le distanze a coppie, il percorso più breve che collega i punti. Naturalmente, questo problema è risolvibile con un numero finito di prove. Non sono note regole che spingerebbero il numero di prove al di sotto del numero di permutazioni dei punti dati. La regola che si debba andare prima dal punto di partenza al punto più vicino, poi al punto più vicino a questo, ecc., in genere non comporta il percorso più breve”.

Il TSP appartiene alla branca della matematica che chiamiamo ottimizzazione: vogliamo ottimizzare (massimizzare o minimizzare) una quantità, e vogliamo che la soluzione ci arrivi sotto forma di numeri interi. Il modo apparentemente facile per risolvere questo problema è guardare ogni possibile circuito e calcolarne la lunghezza, con un metodo chiamato ricerca esaustiva: 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à. Il numero di circuiti distinti quando ci sono n città è (n − 1)! / 2. Il divisore due nel denominatore significa che un singolo circuito può essere percorso in entrambe le direzioni. Si noti nella tabella quanto velocemente il numero di circuiti aumenta con n:

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-difficile. Ciò significa che non è possibile trovare una soluzione esatta, se non con un algoritmo troppo lento perché possa essere utilizzato per casi realisticamente utili. Se un moderno computer ad alta velocità calcola, siamo generosi, un miliardo di circuiti al secondo, ci vorrebbero 10⁴⁶ anni per trovare la risposta sicura per un circuito di 50 città. (Per fare un confronto, l'età attuale dell'universo è stimata a circa 1,3×10¹⁰  anni.) Passare al supercomputer più veloce esistente non aiuterebbe molto.

Di fronte all’impossibilità di risolvere un problema efficacemente, i matematici vanno alla 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, ma nemmeno questo è così tanto facile. La complessità del TSP sembra rimanere elevata anche se si cerca di modificare il problema, ad esempio dividendo le città in sottoinsiemi da studiare separatamente.

Un esempio noto di algoritmi per problemi di ottimizzazione discreta e combinatoria è dato dalla famiglia Branch and Bound (BB, B&B): non è la sola strategia, ma casomai parlerò delle altre un’altra volta. Gli algoritmi Branch and Bound sono detti di enumerazione implicita perché si comportano esattamente come un algoritmo di enumerazione, cioè "provano" tutte le soluzioni possibili fino a trovare quella ottima (o quella corretta), ma ne scartano alcune dimostrando a priori la loro non ottimalità. Un algoritmo BB (“dirama e collega”) consiste in un'enumerazione delle soluzioni candidate mediante ricerca nell'insieme di tutte le possibili configurazioni del sistema: l'insieme delle soluzioni candidate è considerato come un albero con l'insieme completo alla radice.

L'algoritmo esplora i rami di questo albero, che rappresentano sottoinsiemi dell'insieme delle soluzioni. Prima di enumerare le soluzioni candidate di un ramo, il ramo viene verificato rispetto ai limiti stimati superiore e inferiore sulla soluzione ottima z* e viene scartato se non può produrre una soluzione migliore di quella trovata fino a quel momento dall'algoritmo. L'algoritmo dipende dalla stima efficiente dei limiti inferiore e superiore di regioni/rami dello spazio di ricerca. Se non sono disponibili limiti, l'algoritmo degenera in una ricerca esaustiva.

Il metodo è stato proposto per la prima volta da Ailsa Land e Alison Doig nel 1960 per la programmazione discreta, ed è diventato lo strumento più comunemente usato per risolvere problemi di ottimizzazione NP-difficili. Il nome "branch and bound" è apparso per la prima volta nel 1963 in un lavoro proprio sul problema del commesso viaggiatore.

Un algoritmo in grado di attaccare il problema, derivato dalla famiglia BB, fu sviluppato nel 1976 da Nicos Christofides, un matematico di Cipro allora professore all’Imperial College di Londra, Christofides dimostrò che il suo metodo crea, nel peggiore dei casi, un percorso che è al massimo il 50% più lungo del percorso ottimo. 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 migliorarlo.

Solo recentemente (maggio 2021) tre matematici dell’Università di Washington (Nathan Klein, Anna Karlin e Shayan Oveis Gharan) hanno mostrano come trovare una migliore approssimazione. Il miglioramento? 10⁻³⁶, un fattore piccolissimo, un miliardesimo di quadriliardesimo. Tuttavia, seppur quasi impercettibile, questo progresso abbatte un muro psicologico: ora si sa che un avanzamento è possibile. Questa notizia ha risvegliato l’interesse di molti ricercatori, che ora si dicono determinati a migliorare ancora la soluzione.

Questo problema è solo di interesse accademico? Direi di no, perché le stesse difficoltà (molte possibili soluzioni da testare e una moltitudine di vincoli contrastanti che rendono difficile trovare la migliore) sorgono in molti importanti problemi del mondo reale. Questi includono la pianificazione del traffico aereo, il riconoscimento di schemi, il cablaggio di circuiti, lo studio delle reti neuronali, l'impacchettamento di oggetti di varie dimensioni e forme in uno spazio fisico o (matematicamente in modo simile) di messaggi codificati in un canale di comunicazione e una vasta moltitudine di altri.

Questi sono tutti esempi di quelli che vengono chiamati problemi di ottimizzazione combinatoria (OC), che tipicamente, anche se non sempre, derivano dalla teoria dei grafi. L'ottimizzazione si occupa di problemi formalizzabili come minimizzazione o massimizzazione di una funzione (detta funzione obiettivo, z) sottoposta a dei vincoli. Un problema di minimizzazione è sempre riconducibile ad un problema di massimizzazione, e viceversa. Non è qui il caso di discutere questo tipo di problemi, ma ciò che dovrebbe essere chiaro è che essi hanno la proprietà che il numero di possibili soluzioni (ad esempio, il numero di possibili circuiti nel TSP) cresce in modo esplosivo man mano che il numero n di variabili di input (il numero di città nel TSP) aumenta. La caratteristica fondamentale di tali problemi è quella di avere insiemi ammissibili discreti, a differenza ad esempio della Programmazione Lineare, in cui l’insieme ammissibile è continuo. Ciò comporta che le metodologie necessarie per affrontare problemi di Ottimizzazione Combinatoria sono spesso diverse da quelle utilizzate per risolvere problemi nel continuo. In generale, il processo di soluzione di un qualsiasi problema di ottimizzazione può essere considerato come composto di due parti distinte:

- produrre una soluzione ottima z*;

- produrre una valutazione che dimostri l’ottimalità di z*.

Trovare la soluzione migliore quando n diventa grande può o non può essere possibile in un tempo ragionevole, e spesso ci si deve accontentare di trovare una delle tante soluzioni "quasi ottimali" o molto buone, se è impossibile trovare le migliori. In molti algoritmi enumerativi per problemi “difficili” capita sovente che l’algoritmo determini la soluzione ottima in tempo relativamente breve, ma sia poi ancora necessario un grandissimo sforzo computazionale per dimostrare che tale soluzione è davvero ottima. In altri termini, la difficoltà del problema risiede non tanto nel costruire una soluzione ottima, quando nel verificarne l’ottimalità, ossia nel determinare il valore ottimo della funzione obiettivo. Alle tecniche utili a determinare questo valore, o una sua approssimazione accurata, è dedicata una parte rilevante della ricerca attuale, volta a sviluppare algoritmi “efficienti” per problemi di OC. Per ragioni sia algoritmiche che teoriche, questo tipo di problemi è diventato di enorme interesse per gli scienziati di quasi tutte le discipline.