Natale su Ganimede – approfondimenti sul quesito e soluzione

Commessi viaggiatori

Prendete un foglio di carta. Disegnate a caso alcuni punti, e colorate di rosso uno di loro. Immaginate ora che il punto rosso rappresenti il punto di partenza e di arrivo di un tragitto che deve necessariamente toccare anche tutti gli altri punti, ciascuno una e una sola volta.

Ora, se esaminate il vostro foglio, vi accorgerete che, molto probabilmente, esistono numerosi tragitti che soddisfano i requisiti: tutti partono dal punto rosso, passano attraverso tutti gli altri (ciascuno esattamente una volta), e finiscono di nuovo sul punto rosso. Il bello è che i percorsi possono avere lunghezze diverse. Il vostro compito è trovare il tragitto più breve tra tutti quelli ammissibili.

Ogni percorso possibile è formato da una sequenza di segmenti consecutivi, ciascuno dei quali congiunge tra di loro due punti. Per stabilire qual è il percorso più breve, dovete armarvi di righello (e di pazienza), prendere in esame tutte le soluzioni possibili e di ciascuna misurare la lunghezza totale (equivalente alla somma delle lunghezze dei singoli segmenti che congiungono i punti): in questo modo il problema si riduce alla fine a un confronto tra tutte le soluzioni trovate.

Una formulazione più rigorosamente matematica richiede che vengano specificate in partenza le distanze esistenti tra tutte le possibili coppie di punti. Ciò è necessario perché le coppie di punti connesse da segmenti in una certa soluzione sono in generale diverse dalle coppie congiunte in un’altra soluzione. I matematici chiamano grafo completo una rete di punti corredata di queste informazioni sulle distanze tra punti.

Il problema che ho descritto è noto come “problema del commesso viaggiatore”. È uno dei problemi classici della teoria dei grafi, e trae il suo nome dall’interpretazione tipica che viene data: un commesso viaggiatore deve visitare una serie di città (ciascuna esattamente una volta) partendo da una di esse e terminando il suo giro nella stessa città di partenza, scegliendo però il viaggio più breve possibile.

Ad esempio, consideriamo il grafo completo della figura qui sotto. Supponiamo che ognuno dei 4 nodi corrisponda a una città, e che gli archi che congiungono i nodi tra di loro rappresentino le strade che collegano una città all’altra.

Su ogni strada viene indicata la sua lunghezza (ad esempio in km). Consideriamo la città 1 come punto di partenza e di arrivo dei tragitti.

Un possibile percorso è quello che attraversa, nell’ordine, le città 1 – 4 – 2 – 3 -1. Se fate la somma dei numeri indicati sugli archi interessati, scoprite che la lunghezza complessiva di questo percorso è 95 km. Un altro percorso possibile è 1 – 3 – 4 – 2 – 1, la cui lunghezza è 80 km. Il secondo percorso, quindi, è migliore del primo.

Quanti sono i possibili percorsi che dobbiamo considerare? Il loro numero equivale al numero di possibili permutazioni dei nodi del grafo completo privato del nodo di partenza e di arrivo (che sicuramente deve trovarsi all’inizio e alla fine della sequenza), cioè al numero di modi di mettere in fila questi 3 nodi. Ebbene, non è difficile dimostrare che il numero di permutazioni di un insieme di N elementi è dato dal fattoriale di N, che si indica con il simbolo N! e che corrisponde al prodotto di tutti i numeri interi compresi tra 1 e N. Nel nostro esempio di grafo con 4 città, i nodi in questione sono N = 3, e quindi le possibili soluzioni sono pari a N! = 3! = 3 × 2 × 1 = 6.

Per risolvere il problema, dovremmo misurare la lunghezza di ciascuno dei possibili 6 percorsi, e alla fine potremmo stabilire qual è il più breve in assoluto.

Finché i nodi del grafo (cioè le città) sono soltanto 4, o comunque molto poche, il numero di soluzioni possibili è abbastanza limitato, ed è quindi possibile esaminarle tutte, magari conl’ausilio di un programma informatico. Purtroppo, però, il fattoriale è una funzione che cresce molto rapidamente (vedi tabella): già con 8 città le alternative sarebbero 40.320, con 10 città salirebbero a 3.628.800, e con 20 città si arriverebbe a più di 2 miliardi di miliardi!

Anche impiegando computer potentissimi, il problema diventa ben presto intrattabile, e sono necessarie tecniche di approssimazione (o euristiche) per la ricerca delle soluzioni.

Un po’ di storia

Qualche lettore affezionato ricorderà che nel primo articolo della rubrica Moebius, uscito nel numero 172 di luglio-agosto 2013, avevo parlato di due celebri rompicapi matematici: le torri di Hanoi e il gioco icosiano. L’inventore di quest’ultimo fu Sir William Rowan Hamilton, che nel 1857 descrisse il gioco durante una riunione della British Association for the Advancement of Science.

Il rompicapo consisteva nel trovare un cammino che toccasse tutti i vertici di un dodecaedro (uno dei solidi platonici, da me trattati nel numero 184 di settembre 2014), percorrendo ciascuno degli spigoli esattamente una volta. Nelle due figure sono mostrati la confezione originale del gioco e una soluzione.

Il gioco icosiano è, evidentemente, una particolare variante del problema del commesso viaggiatore, in cui il grafo di partenza non è completo, cioè è possibile utilizzare solo alcuni archi (quelli che corrispondono a spigoli del dodecaedro) e non altri.

Il problema generale del commesso viaggiatore, invece, fu analizzato negli anni Trenta del XX secolo dopo dal matematico austriaco Karl Menger, famoso soprattutto per aver descritto un particolare frattale tridimensionale noto come “spugna di Menger”.

L’ormai popolare riferimento alla figura del “commesso viaggiatore” nel nome classico del problema fu un’intuizione del matematico americano Hassler Whitney.

Per cercare di risolvere il problema del commesso viaggiatore (o “travelling salesman problem”, TSP, all’inglese), fino agli anni ‘50 del secolo scorso si utilizzò sempre il cosiddetto metodo di “forza bruta”, cioè l’enumerazione esaustiva di tutti i percorsi possibili e la comparazione delle rispettive lunghezze: ciò rendeva del tutto impensabile la risoluzione del problema con un numero di nodi appena superiore a una decina.

Nel 1954 i matematici americani George Dantzig, Ray Fulkerson e Selmer Johnson proposero un metodo alternativo, basato sulla tecnica dei piani di taglio, per risolvere il problema in modo più efficiente: così facendo riuscirono a trovare un percorso ottimale attraverso le 48 capitali degli Stati Uniti (Alaska e Hawaii non erano ancora diventati Stati a tutti gli effetti) più Washington, capitale federale.

La soluzione migliore, come scoprirono i tre matematici, era quella illustrata in figura.

Nel 1962, la Procter & Gamble lanciò un concorso tra i suoi clienti: per aggiudicarsi il premio in palio, si doveva risolvere il problema del commesso viaggiatore su una rete con 33 città.

Ulteriori progressi vennero ottenuti nei decenni successivi, sfruttando la crescente potenza dei computer ma soprattutto le tecniche via via più raffinate che i ricercatori riuscirono a sviluppare. Si cominciò così a risolvere il problema anche con molte migliaia di nodi.

Il problema di dicembre

Nel numero 187 di Coelum la rubrica Moebius ha rivestito il classico problema del commesso viaggiatore di un’ambientazione al tempo stesso interplanetaria e natalizia: la sfida consisteva nell’aiutare Babbo Natale a trovare un percorso ottimale per portare regali a tutti i bambini buoni del Sistema Solare.

Più precisamente, il contesto fantascientifico da me ipotizzato prevedeva cinque mondi abitati: la Terra, la Luna, Marte, Cerere e Ganimede. I mondi sono tra di loro connessi da speciali collegamenti, e ogni rotta che congiunge due mondi può essere percorsa dall’astroslitta di Babbo Natale in un certo numero di ore, il medesimo nelle due direzioni. In questo particolare problema del commesso viaggiatore (o meglio, del Babbo Natale interplanetario), al posto delle città abbiamo quindi i cinque pianeti, e ogni arco del grafo è etichettato non da una lunghezza in chilometri, ma da un tempo di percorrenza in ore. Cito dall’articolo:

Precisamente, Marte dista due ore e mezza dalla Terra, ma la stessa distanza lo separa anche dalla Luna e da Ganimede. Tra la Terra e la Luna c’è un’ora di volo, mentre il nostro satellite dista tre ore e mezza da Ganimede. Terra e Cerere sono lontani quattro ore, e due ore separano il pianeta nano da Ganimede e anche da Marte.

Il compito del lettore consisteva pertanto nel trovare il tragitto più veloce, non il più breve. Ma non solo. Il percorso ottimale doveva soddisfare anche un ulteriore, fondamentale vincolo: ogni bambino del Sistema Solare doveva ricevere un regalo. Si ipotizza infatti che ciascuno dei pianeti abitati ospiti un certo numero di bambini e un magazzino con una data quantità di giocattoli. All’arrivo su ogni pianeta, Babbo Natale può caricare sul suo fantastico veicolo volante i giocattoli presenti nel magazzino. Nella tabella seguente sono indicati il numero di bimbi e di giochi presenti su ogni mondo.

In conclusione, il percorso ottimale deve permettere a Babbo Natale di partire dalla Terra, visitare ognuno degli altri quattro pianeti, ciascuno esattamente una volta, e ritornare al punto di partenza, utilizzando i collegamenti indicati e riuscendo a portare un regalo a ogni bambino. Semplice, no?

Natale con Asimov

Qualche lettore appassionato di fantascienza si sarà forse ricordato che il titolo dell’articolo di dicembre, “Natale su Ganimede”, è lo stesso di un racconto dell’amatissimo (sicuramente da me, ma non solo) scrittore e divulgatore scientifico Isaac Asimov.

Il racconto fu pubblicato nel 1942 sulla rivista Startling Stories. In una sua autobiografia, Asimov rivelò che si era sforzato di scrivere una storia soprattutto divertente, cosa che, a suo parere, è una delle più difficili in assoluto per uno scrittore. Curiosamente, anche il racconto di Asimov tira in ballo Babbo Natale. La storia, com’è facile immaginare, è ambientata sul satellite gioviano Ganimede, per l’occasione popolato da strane creature simili a struzzi, chiamati ossies e utilizzate dalla Ganymedan Products Corporation come forza lavoro. Un giorno qualcuno racconta agli ossies di Babbo Natale, e loro decidono di scioperare finché il barbuto portatore di doni non si recherà in visita su Ganimede. L’azienda entra in una grave crisi, e ciò costringe gli abitanti umani di Ganimede a inscenare una finta visita di Babbo Natale. Tutto sembra risolto, quando gli ossies richiedono che Babbo Natale vada a trovarli ogni anno. Peccato che l’anno ganimediano, cioè il periodo di rivoluzione di Ganimede attorno a Giove, dura soltanto sette giorni terrestri…

La soluzione e i vincitori

La risoluzione del problema richiedeva un po’ di attenzione. Partendo dalla Terra, Babbo Natale può caricare sulla sua astroslitta 1,1 miliardi di regali, ma dovrà consegnarne 1 miliardo prima di lasciare il pianeta. Decollerà quindi con un carico di “soli” 100 milioni di giocattoli, cosa che gli impedirà di atterrare su Marte, visto che sul pianeta rosso ci sono 400 milioni di bambini ma soltanto 200 milioni di giocattoli. La sua seconda tappa potrà quindi essere Cerere oppure la Luna.

Nel primo caso, dopo il pianeta nano sarà sicuramente la volta di Ganimede, perché Marte risulta ancora off limits per motivi di eccedenza di bambini rispetto ai doni disponibili. Dopo Ganimede Babbo Natale deve raggiungere la Luna e Marte, in uno dei due ordini possibili, per poi fare ritorno sulla Terra.

Anche nel secondo caso, la successiva tappa dopo la Luna deve essere per forza di cose Ganimede, seguito da Marte e Cerere, in entrambe le sequenze possibili, e infine la Terra.

I quattro percorsi ammessi sono di conseguenza:

• Terra Cerere Ganimede Luna Marte Terra
• Terra Cerere Ganimede Marte Luna Terra
• Terra Luna Ganimede Marte Cerere Terra
• Terra Luna Ganimede Cerere Marte Terra

I tempi di percorrenza dei quattro tragitti sono, rispettivamente: 14,5 ore, 12 ore, 13 ore, 11 ore.

Il percorso ottimale, quindi, risulta il seguente:

Terra Luna Ganimede Cerere Marte Terra

A trovarlo per primo è stato Andrea Alessandrini (che non è parente dell’autore), che quindi ha vinto l’abbonamento semestrale. Hanno inviato risposte esatte anche Stefano Zella, Cristian Agostini, Ivano Domenico Mai, Dario Broggi (pur con una imprecisione) e Daniele Tosalli.

I più sentiti complimenti a tutti loro!