I rompicapi di Alice: Il problema del commesso viaggiatore

Narrano le cronache della Miskatonic University che il professor Jonathan Lake nel 1867 andò in esplorazione nel Paese delle Meraviglie, tornando con una valigia piena di oggetti raccolti dall'esotico paese e ottenendo anche una mappa della regione:

In effetti il kit, di cui ha anche riferito boing boing, è stato realizzato nel 2008 da absinthetic ispirandosi ai lavori di Alex CF⁽¹⁾ e come regalo per la sua fidanzata.
Una mappa del Paese delle Meraviglie, però, è un'ottimo modo per pensare alle peregrinazioni di Alice e ci si potrebbe chiedere se la nostra eroina ha realizzato il percorso più breve per andare da un posto all'altro del Paese. Un problema di questo genere è anche noto come il problema del commesso viaggiatore: l'eroe della nostra storia deve spostarsi in una serie di città collegate tra loro da una rete stradale. Quello che ci chiediamo è se esiste un percorso che minimizza lo spostamento e soprattutto quale è.
Basati su quesiti di questo genere sono, ad esempio, un paio di puzzle di Sam Loyd: I giochi del re del Siam⁽²⁾

In particolare date un'occhiata alla parte sinistra dell'illustrazione, dove la principessa Enigma mostra al Re del Siam un foglio con le illustrazioni di alcune mele e pere chiedendogli di trovare il percorso più breve che tocchi tutti i 16 frutti terminando sul cuore.
Non molto differente è Il giro della bertuccia⁽²⁾:

In questo caso la scimmietta Jocko deve raccogliere gli oboli dagli spettatori del palazzo partendo dalle spalle del padrone, l'organista Tony, per finire nel punto di partenza. Quale è il percorso più breve che può fare?
Indipendentemente dalle risposte, che potete divertirvi a cercare (non su Google!), il problema del nostro commesso viaggiatore trova varie applicazioni in molte sottobranche della matematica, dalla teoria dei grafi, all'informatica, alla teoria della complessità.
Le sue origini, però, non sono ben chiare: probabilmente risale ai primi del 1800, anche se la sua prima formulazione certa è dovuta ai matematici Hamilton e Kirkman. Il gioco era basato sull'icosian game di Hamilton e sui cammini hamiltoniani.
Un'altra definizione, dove più che a un commesso viaggiatore si fa riferimento a un messaggero, è data da Karl Menger, matematico austriaco:

We denote by messenger problem (since in practice this question should be solved by each postman, anyway also by many travelers) the task to find, for finitely many points whose pairwise distances are known, the shortest route connecting the points. Of course, this problem is solvable by finitely many trials. Rules which would push the number of trials below the number of permutations of the given points, are not known. The rule that one first should go from the starting point to the closest point, then to the point closest to this, etc., in general does not yield the shortest route.⁽³⁾

Una prima versione semplice che porta subito all'attenzione le caratteristiche da teoria dei grafi del problema è la seguente: trovare il percorso più breve tra quattro città poste ai vertici di una figura geometrica, e quindi costruire la strada corrispondente al percorso minimo.

Se prendiamo come figura geometrica un quadrato ad esempio di lato 100 km, si ottiene la variazione proposta da Ian Stewart nella sua Piccola bottega delle curiosità matematiche.
Quando andiamo a trovare una soluzione computazionale del nostro problema possiamo, però, applicarlo ad ambiti quasi inaspettati, come a un formicaio! E' ad esempio il caso di Distributed optimization by ant colonies di Alberto Colorni, Marco Dorigo e Vittorio Maniezzo che è entrato a far parte della letteratura sull'argomento!
Andiamo, però, con ordine: i ricercatori del Politecnico di Milano, ispirati dagli studi sulle colonie di formiche (sistemi nei quali ogni individuo compie un'azione semplice, senza conoscere di principio le azioni compiute dagli altri), decidono di modellizzare un formicaio realizzando una serie di algoritmi per testare i quali si utilizza proprio il problema del commesso viaggiatore. Innanzitutto bisogna definire un po' di oggetti: abbiamo $n$ città e $m$ formiche, il cui valore totale è dato dalla sommatoria \[m = \sum_{i=1}^n b_i(t)\] dove $b_i (t)$ è il numero di formiche presenti nella città $i$ al tempo $t$.
Inoltre, in caso di geometria euclidea, il percorso $p_{ij}$ più breve tra due città $i$, $j$ sarà dato dalla distanza euclidea tra queste: \[d_{ij} = \left [ \left ( x^i_1-x^j_1 \right )^2 + \left ( x^i_2-x^j_2 \right )^2 \right ]^{\frac{1}{2}}\] Poiché si suppone che ogni formica nel suo camminare lascia una traccia di ferormoni dietro di se, allora si introduce anche un parametro $\tau_{ij}$ che misura l'intensità della traccia lasciata tra le città $i$ e $j$: \[\tau_{ij} (t+1) = \rho \cdot \tau_{ij} (t) + \Delta \tau_{ij} (t, t+1)\] dove $\rho$è un coefficiente di evaporazione, ovvero indica quanta traccia è scomparsa nell'unità di tempo, mentre $\Delta \tau_{ij} (t, t+1)$ è definita come la somma degli $m$ $\Delta \tau^k_{ij} (t, t+1)$ che rappresentano la quantità di ferormone lasciata nel percorso tra $i$ e $j$ dalla $k$-sima formica tra l'istante $t$ e l'istante $t+1$.
A questo punto, detta visibilità la quantità $\eta_{ij} = 1/d_{ij}$, si definisce la probabilità di transizione o di passaggio dalla città $i$ alla città $j$ come \[P_{ij} (t) = \frac{\left [ \tau_{ij}(t) \right ]^\alpha \cdot \left [ \eta_{ij} \right ]^\beta}{\sum_{j=1}^n \left [ \tau_{ij}(t) \right ]^\alpha \cdot \left [ \eta_{ij} \right ]^\beta}\] dove $\alpha$ e $\beta$ sono due parametri che permettono il controllo dell'importanza relativa della traccia rispetto alla visibilità.
All'interno dell'algoritmo, infine, si definisce una lista detta tabu, caratteristica di ogni formica, dove viene registrata ogni città visitata. In questo modo i movimenti della formica verranno via via influenzati dalle città già visitate e da visitare.
Gli algoritmi sviluppati sono stati 3, ANT-quantity, ANT-density, ANT-cycle.
Dal punto di vista matematico le differenze notevoli tra i 3 modelli sono nella definizione dell'intensità della scia. Per il quantity: \[\Delta \tau^k_{ij} (t, t+1) = \left\{\begin{matrix} \frac{Q_1}{d_{ij}} & \text{se la } k-\text{sima formica va da } i \text{ a } j \text{ tra } t \text{ e } t+1 \\ 0 & \text{in tutti gli altri casi} \end{matrix}\right.\] Per il density: \[\Delta \tau^k_{ij} (t, t+1) = \left\{\begin{matrix} Q_2 & \text{se la } k-\text{sima formica va da } i \text{ a } j \text{ tra } t \text{ e } t+1 \\ 0 & \text{in tutti gli altri casi} \end{matrix}\right.\] dove $Q_1$ e $Q_2$ sono delle costanti che misurano rispettivamente la quantità di ferormone lasciata sul percorso $p_{ij}$ ad ogni passaggio e la quantità di ferormone lasciata per unità di lunghezza sempre lungo $p_{ij}$.
Mentre i primi due sono sostanzialmente identici, il cycle è invece leggermente differente: \[\Delta \tau^k_{ij} (t, t+n) = \left\{\begin{matrix} \frac{Q_3}{L_k} & \text{se la } k-\text{sima formica usa il percorso } p_{ij} \\ 0 & \text{in tutti gli altri casi} \end{matrix}\right.\] dove $Q_3$ è una costante, mentre $L_k$ è la lunghezza del giro compiuto dalla $k$-sima formica. Inoltre l'intensità della scia è calcolata non più in $t$ ma in $t+n$.
Le migliori prestazioni sono ottenute dal cycle, ha quindi senso presentare i risultati grafici legati a questo modello.
Una delle cose che è necessario verificare con le simulazioni è se queste arrivano a stabilità per lunghi tempi:

Questo, però, non può accontentarci: bisogna anche verificare che le condizioni iniziali non influenzino troppo le simulazioni stesse

Si può anche notare come con un parametro $\alpha$ non nullo, la termalizzazione e quindi i risultati dell'algoritmo sono migliori.
Interessante dare un'occhiata alle fluttuazioni sulla deviazione standard:

Nell'immagine qui sotto, invece, si possono apprezzare i percorsi con le loro differenze di intensità all'inizio della simulazione (a sinistra) e dopo 100 cicli (a destra).

Se poi prendiamo una situazione più complessa (una trentina di città), dopo circa 340 cicli cycle ottiene un risultato tipo quello mostrato qui sotto:

Le immagini sono tratte da The Ant System: Optimization by a colony of cooperating agents del 1996 dove la probabilità è definita in maniera coerente con il modello utilizzato, il cycle: \[P_{ij}^k (t) = \left\{\begin{matrix} \frac{\left [ \tau_{ij}(t) \right ]^\alpha \cdot \left [ \eta_{ij} \right ]^\beta}{\sum_{k \in \text{allowed}_k} \left [ \tau_{ij}(t) \right ]^\alpha \cdot \left [ \eta_{ij} \right ]^\beta}\ & \text{se } j \in \text{ allowed}_k \\ 0 & \text{in tutti gli altri casi} \end{matrix}\right.\] dove per $\text{allowed}_k$ si intendono tutte le città che non sono ancora state raggiunte dalla $k$-sima formica.
La stessa formula, poi, viene esplicitamente utilizzata per il nostro commesso viaggiatore in Ant colonies for the travelling salesman problem di Dorigo e Maria Lucia Gambardella.
Gli studi sull'ottimizzazione dei formicai, o più tecnicamente sull'ottimizzazione delle colonie di formiche trovano varie applicazioni. Ad esempio per la risoluzione dei problemi di tipo-NP, ovvero problemi che richiedono tempi lunghi per riuscire a identificare la soluzione ottimale (per una spiegazione dettagliata su questo genere di problemi e su altre cose del genere, leggete questo splendido post di .mau.: è un po' lungo, quindi dovrete perdervi il tempo necessario anche per questo!).
Altre applicazioni anche nel campo delle telecomunicazioni, ad esempio nella risoluzione di problemi legati alle reti, come può essere ad esempio internet. Nel campo industriale, invece, l'applicazione di questi metodi può portare all'ottimizzazione nella gestione dei mezzi di trasporto a disposizione, o a una migliore distribuzione delle merci, o nella ricerca della gestione ottimale dei siti di stoccaggio.
In conclusione un modello interessante, che dalle sue origini a oggi ha subito pochissimi raffinamenti (l'ultimo nel 2006 con Ant Colony Optimization di Dorigo, Mauro Birattari e Thomas Stützle), che, ormai entrato nella letteratura del settore (vedi, ad esempio, la bibliografia di A memetic ant colony optimization algorithm for the dynamic travelling salesman problem di Michalis Mavrovouniotis e Shengxiang Yang) trova applicazioni non solo nella matematica o nell'informatica, ma anche nel mondo reale.

Alberto Colorni, Marco Dorigo, & Vittorio Maniezzo (1992). Distributed Optimization by Ant Colonies Proceedings of the First European Conference on Artificial Life, 134-142 Other: citeulike:5791708

Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics), 26 (1), 29-41 DOI: 10.1109/3477.484436

Dorigo, M., Birattari, M., & Stutzle, T. (2006). Ant colony optimization IEEE Computational Intelligence Magazine, 1 (4), 28-39 DOI: 10.1109/MCI.2006.329691

(1) Per strano che possa sembrare, all'inizio di marzo Alex CF ha realizzato una sorta di kit ispirato proprio a Charles Dodgson

(2) I problemi di Loyd indicati sopra sono rispettivamente il 99 e il 108 di Passatempi matematici, libro che raccoglie 163 puzzle dell'enigmista statunitense e curato da Martin Gardner. E' in mio possesso l'edizione del 1980 della Sansoni.
(3) Originale tedesco: Wir bezeichnen als Botenproblem (weil diese Frage in der Praxis von jedem Postboten, übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlich viele Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden. Dieses Problem ist natürlich stets durch endlich viele Versuche lösbar. Regeln, welche die Anzahl der Versuche unter die Anzahl der Permutationen der gegebenen Punkte herunterdrücken würden, sind nicht bekannt. Die Regel, man solle vom Ausgangspunkt erst zum nächstgelegenen Punkt, dann zu dem diesem nächstgelegenen Punkt gehen usw., liefert im allgemeinen nicht den kürzesten Weg.