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!