Pitagora

Mosse tabù

Mr. Palomar e il suo amico Mr. Wilson si trovano a passeggiare sulle colline, in una zona molto vasta, caratterizzata da ondulazioni continue, irregolari e disuguali.
I due si inerpicano su ripidi sentieri attraverso i boschi, seguiti da discese erbose e da nuove salite.
- Dovevamo studiare meglio la cartina prima di partire. Qui è tutto un saliscendi! - esclama Mr. Palomar col fiatone.
- Te l'ho detto, la cartina l'ho dimenticata a casa. Ma suvvia, non è piacevole un po' di saliscendi? La verità è che non hai più il fisico.
- Sarà. Ma spero che manchi poco all'arrivo.
- Il punto dove dovremmo arrivare è il punto più basso dell'intera area collinare.
- Me lo hai già detto. Chissà se siamo sulla strada giusta - brontola Mr. Palomar.
- Tranquillo, prima o poi arriveremo!
- Già, prima o poi...
- Piuttosto, visto che il percorso è così ondulato, sarebbe stato interessante portare un altimetro.
- Un altimetro? Sarebbe stata più utile la tua cartina, dove sono indicate le linee altimetriche!
- Ma anche un altimetro potrebbe aiutare. Come ti dicevo, il punto dove dobbiamo arrivare è il punto alla quota più bassa di tutta questa zona.
- Va bene, ma l'altimetro ti dice la quota del punto in cui siamo, non di tutti i punti del territorio!
- Hai ragione, però conoscendo l'altitudine del punto in cui siamo e quella dei punti immediatamente vicini, si può avere un'idea di quale strada intraprendere!
- Mi stai dicendo che non sei più sicuro se stiamo seguendo il sentiero giusto?
- No, tranquillo, sono sicuro. O... quasi.
- Speriamo. Ma l'idea che ti può dare l'altimetro è sicuramente imperfetta. Supponiamo che qui la quota sia di 300 metri, e che sia invece di 350 metri se ci spostiamo di mezzo chilometro a nord, 300 metri se andiamo a ovest, 250 metri a sud e 290 a est. Tu ti incammineresti verso sud, immagino. Però chi ti dice che imboccando quella direzione, mezzo chilometro dopo non si cominci a salire tornando a 300 metri e più? Magari è meglio piegare verso nord, perché dopo l'altura può esserci una discesa verso il punto basso che vogliamo raggiungere! E poi, lasciamelo dire, il tuo altimetro è perfettamente inutile: possiamo vedere a occhio se nelle varie direzioni ci siano salite o discese! Il fatto è che questa informazione potrebbe essere ingannevole.
- Hai perfettamente ragione! Ti concedo che l'altimetro serva a poco. Ed è vero che quell'informazione la puoi ricavare anche semplicemente guardandoti attorno. Ma questa informazione rimane molto utile per trovare la strada giusta.
- Forse. Ma seguendo pedissequamente questo metodo rischi di prendere direzioni del tutte sbagliate.
- Sì, ma non ho finito di spiegarti il mio metodo.
- Sentiamo. Sono tutto orecchi.
- In pratica la regola fondamentale è spostarsi seguendo la direzione che comporta il maggiore abbassamento possibile della quota. Tuttavia, questo può portare ad un problema.
- Quale problema?
- Il problema che tu stesso hai intuito. Seguendo il tuo esempio, se io mi incammino verso sud per scendere ad una altitudine di 250 metri, potrei scoprire, una volta spostatomi nella nuova posizione, che tutte le direzioni attorno a me condurrebbero verso punti più in alto.
- Appunto, è proprio ciò che obiettavo.
- In pratica mi troverei in una specie di buca, dalla quale non posso spostarmi perché qualunque direzione mi farebbe "peggiorare" la situazione, cioè non mi consentirebbe di abbassare la quota corrente.
- Però, pensaci un attimo. Questo potrebbe essere un buon segno: potresti infatti essere arrivato nel punto di destinazione, quello più basso di tutti.
- Certo, ma potrebbe anche essere un falso punto di destinazione. In altre parole, anziché il punto in assoluto più basso della zona, potrebbe essere semplicemente un punto circondato da punti più alti, e tuttavia meno basso del punto che desideriamo raggiungere: insomma, come dicono i matematici, invece del minimo globale, un minimo locale.
- E come si fa allora?
- Rischiamo di rimanere intrappolati in questi "falsi" minimi. Occorre che il nostro metodo consenta di uscire da queste buche.
- Non possiamo farlo finché la regola prescrive di scegliere la direzione che porta verso il maggiore abbassamento della quota. Se siamo finiti in una buca, la quota la possiamo soltanto alzare, non abbassare. Però un aumento "temporaneo" sarebbe l'unico modo per uscire dalla buca: poi potremmo essere premiati trovando una nuova promettente discesa.
- Hai colto perfettamente il nocciolo della questione. Infatti il metodo di cui voglio parlarti ammette, soltanto quando non si può fare di meglio, anche "mosse peggioranti", cioè spostamenti verso quote maggiori, proprio per evitare di restare intrappolati nelle buche.
- Bene, è tutto qui?
- No. C'è un altro problema. Immagina di essere finito in una buca. Come abbiamo detto, potremmo essere già arrivati al nostro traguardo; ma potremmo anche essere finiti in un minimo locale dal quale dovremmo allontanarci per esplorare altre zone. Ammettendo gli spostamenti peggioranti, il nostro metodo ci consente di risalire per un po' uno dei versanti del burrone. Cosa succede subito dopo?
- Dato che il metodo prescrive comunque di seguire la direzione migliore, dovremmo girare sui tacchi e tornare indietro, finendo di nuovo nella voragine. Poi torneremmo a risalire il pendio, e quindi scenderemmo di nuovo, all'infinito.
- Brutta cosa. Il metodo non funziona.
- E' proprio qui che interviene la trovata geniale. Il metodo proibisce di ripetere la stessa "mossa" per un certo tempo. Quindi, quando abbiamo risalito il versante, non possiamo finire nella gola di nuovo perché così facendo ripercorreremmo uno spostamento già effettuato, cosa proibita dal nostro metodo. In questo modo, visto che la mossa rimane "tabù" per un certo numero di spostamenti, abbiamo tutto il tempo di risalire completamente il pendio e metterci "in salvo", allontanandoci dal pericoloso canyon.
- Interessante. Hai inventato tu questo procedimento?
- No. Il metodo che ti ho descritto è noto come "tabu search", o "ricerca tabu", ed è stato ideato dall'informatico americano Fred Glover, verso la fine degli anni Ottanta.
- Viene davvero utilizzato in qualche applicazione?
- Come no. E' una delle tecniche più note e più apprezzate per affrontare difficili problemi di ottimizzazione. Spesso i ricercatori hanno bisogno di risolvere problemi che corrispondono alla ricerca di minimi di funzioni complicate dall'andamento non ben conosciuto: qualcosa di simile al nostro problema di cercare il punto più basso di un territorio del quale non conosciamo l'altimetria.
- E utilizzando questa tecnica, si riesce sempre a trovare il minimo globale?
- Assolutamente no. Il più delle volte il "tabu search", così come altre tecniche simili, permette di avvicinarsi molto alla soluzione migliore; altre volte consente di individuarla con precisione; altre volte ancora non fornisce soluzioni di alta qualità, ma si tratta di casi meno frequenti. In ogni caso, le tecniche come il "tabu search" vengono chiamate "euristiche": la loro caratteristica principale è che utilizzando queste tecniche non è detto che venga trovata sempre la soluzione migliore di tutte.
- E allora, perché queste tecniche vengono utilizzate?
- Perché in molti casi non possiamo fare di meglio. Se abbiamo dimenticato a casa la cartina e non ricordiamo più il sentiero da seguire, l'unica possibilità è affidarsi a metodologie approssimate di questo tipo.
- E' anche il nostro caso? - chiede preoccupato Mr. Palomar
- Temo di sì - risponde Mr. Wilson - Non ricordo più il percorso giusto. Dovremo affidarci alla ricerca tabu per riuscire a tornare a casa!

Carnevale della matematica #39: goto .mau.

Il Carnevale della Matematica di luglio, che coincide con la Presa della Bastiglia, è ospitato dal Fondatore, Maurizio Codogno, alias .mau., in particolare dal suo ormai celebre blog delle "Notiziole"
Il tema del mese riguarda i "giochi matematici" (o "la matematica e i giochi", o "il gioco della matematica"...). Come sempre, il tema non è vincolante: e infatti alcuni blogger si sono attenuti e altri no.
Mr. Palomar ha contribuito con sei articoli (mese abbastanza prolifico...), quattro dei quali riguardano il tema proposto.
Ma la novità più rilevante è la presenza di una nuova partecipante agli eventi carnascialeschi: Cristina Sperlari, insegnante di scuola primaria, con il suo blog "Il piccolo Friedrich".
Buon Carnevale a tutti!

Il gioco della fine del mondo

Hanoi è la capitale dello stato di Vietnam dal 1976, anno della riunificazione tra Vietnam del Nord e Vietnam del Sud. Lo scorso 10 ottobre (un giorno matematicamente molto particolare secondo il calendario gregoriano: 10/10/10) gli abitanti di Hanoi e tutti i vietnamiti hanno festeggiato il millesimo anniversario della costruzione della città, voluta dall'imperatore Lý Thái Tổ che la chiamò Thăng Long, cioè "dragone che si alza in volo".
La città di Hanoi è ben nota, oltre che ai geografi, agli storici e ai viaggiatori, anche agli informatici. Perché mai? Semplicemente perché nel 1883 il matematico francese Edouard Lucas, per attribuire un tocco di esotismo ad un rompicapo di sua invenzione, si inventò una leggenda collegata all'antica città di Hanoi. Secondo la leggenda di Lucas, in un tempio di Hanoi alcuni monaci sono intenti, da tempo immemore, a poggiare dischi d'oro su colonne di diamante, consapevoli che nel momento in cui avranno terminato il loro compito il mondo avrà fine.
Più precisamente, ci sono 3 colonne e 64 dischi di dimensioni diverse. All'inizio dei tempi i dischi erano incolonnati sulla prima colonna in ordine di grandezza, cioè in modo tale che ogni disco poggiasse su un disco più grande (i dischi formavano quindi un cono). Da allora i monaci hanno cominciato a spostare dischi, uno alla volta, rispettando la regola fondamentale secondo la quale è vietato poggiare un disco su un disco più piccolo, e con l'obiettivo supremo di spostare tutti i dischi sulla terza colonna.
Come si risolve il rompicapo? La soluzione che si impara nei corsi di programmazione è un tipico esempio di algoritmo ricorsivo, e anche un eccellente esempio di ragionamento per induzione.
Supponiamo di essere in grado di risolvere il gioco per n dischi, e cimentiamoci nella versione con n+1 dischi. Sulla prima colonna avremo quindi n+1 dischi, che dobbiamo spostare sulla terza colonna. Sapendo risolvere il rompicapo con n dischi, non avremo difficoltà a spostare i primi n dischi dalla prima alla seconda colonna; potremo agevolmente spostare il disco (n+1)-esimo dalla prima alla terza colonna, e infine ripeteremo il procedimento degli n dischi spostando tutti i dischi dalla seconda alla terza colonna.
Siccome il gioco è banalmente risolvibile se n=1 (si tratta semplicemente di spostare un disco dalla prima alla terza colonna), per induzione possiamo concludere che è possibile risolvere il rompicapo per qualsiasi numero n.
Si può dimostrare che il numero minimo di mosse necessarie per risolvere il rompicapo con n dischi è pari a 2ⁿ-1. Se i dischi fossero soltanto 3, basterebbero quindi 2³ - 1 = 7 mosse; con 64 dischi, il numero diventa enorme: i monaci dovrebbero effettuare più di 18 miliardi di miliardi di spostamenti!
Possiamo quindi stare tranquilli: se immaginiamo che per spostare un disco i monaci impieghino un secondo, il mondo finirà tra circa 584 miliardi di anni, un tempo ben superiore a quello necessario a trasformare il Sole nella gigante rossa che inghiottirà anche il nostro pianeta.

Il numero di Dio

Immaginate di dover raggiungere un luogo della vostra città dove non siete mai stati, assolutamente entro una certa ora. Potete aiutarvi con il navigatore, o affidarvi alla vostra conoscenza della città, o ancora chiedere indicazioni a qualche passante. In ogni caso non vi basta semplicemente arrivare, ma avete bisogno di trovare un tragitto ottimale, possibilmente il più breve possibile.
Esistono infatti moltissimi, addirittura infiniti percorsi per arrivare in un certo luogo, e uno di essi è quello che permette di giungere a destinazione nel minor tempo possibile.
Se invece di raggiungere un luogo dovete cimentarvi con un rompicapo, ad esempio il celeberrimo cubo magico di Rubik, o il gioco del quindici, di cui ho parlato in un mio precedente post, la situazione non è molto diversa. Potreste accontentarvi di risolvere “semplicemente” il gioco, cioè portare il cubo, probabilmente disordinato, nella configurazione ordinata con tutte le facce colorate di un solo colore, oppure spostare le tessere del gioco del quindici in modo che i numeri siano tutti in sequenza. Ma se siete giocatori provetti, questo non vi basta: volete trovare la via più breve, che conduce sempre alla disposizione finale ordinata nel minor numero di mosse. Se la trovaste davvero, probabilmente sareste talmente orgogliosi di voi stessi da sentirvi “come un dio”: e ne avreste ben donde! Non a caso un algoritmo, cioè un procedimento ben definito, che consenta di risolvere un rompicapo come il cubo di Rubik o il gioco del quindici con il numero minimo possibile di mosse e riducendo al minimo la quantità di memoria utilizzata viene chiamato “algoritmo di Dio”.
Se il riferimento all’essere supremo può sembrarvi esagerato, sappiate che escogitare una procedura di questo tipo, in genere, non è compito facile. La clausola sull'utilizzo della memoria è a questo proposito importante: riferendoci per esempio al cubo di Rubik, sarebbe facile, in linea di principio, pensare ad una enorme tabella precompilata in cui ad ogni configurazione possibile del cubo viene fatta corrispondere la sequenza ottimale per risolvere il rompicapo. Ma si dà il caso che il giocattolo di Rubik può assumere 43 miliardi di miliardi di possibili configurazioni: produrre e utilizzare una simile tabellona sarebbe poco maneggevole perfino per i computer più potenti.
Albert Einstein disse "Quando la soluzione è semplice, Dio sta rispondendo". Potremmo anche immaginare Dio come un risparmiatore, che predilige le vie che consentono di sprecare meno risorse possibili: non solo il tempo, ma anche lo spazio, cioè la memoria.
Un degno algoritmo di Dio per il cubo di Rubik, quindi, dovrebbe essere sempre capace di determinare la sequenza di mosse più breve per riordinare il diabolico marchingegno, senza ricorrere a giganteschi indici. La ricerca di una procedura di questo tipo è strettamente collegata ad una domanda che molti di noi, giocherellando con il famoso rompicapo, ci siamo posti: quante mosse sono necessarie per risolvere questo puzzle? Equivalentemente: qual è il numero minimo di mosse con cui possiamo certamente risolvere il cubo partendo da una configurazione qualsiasi? Sono certo che avrete già immaginato come i matematici hanno chiamato questo numero. Proprio così: il numero di Dio.
Già nel 1981, quando il cubo magico era all'apice del suo successo in tutto il mondo, il matematico Morwen Thistlethwaite dimostrò che 52 mosse sono sempre sufficienti per risolvere il cubo, partendo da qualsiasi configurazione. Questo significava che il numero di Dio non poteva essere maggiore di 52: ma probabilmente era più basso. Dal 1981 in poi, molti altri matematici cercarono di abbassare quel numero, e ci riuscirono. Nel 1990 si era già arrivati a 42, nel 1992 si scese a 37, e nel 1995 si arrivò a quota 29.
In questo stesso anno Michael Reid si cimentò nel compito opposto: trovare un limite inferiore al numero di Dio, cioè un numero di mosse sotto il quale non si può andare per configurazioni particolarmente "rognose". Reid fissò questo limite a 20.
Il numero di Dio era quindi compreso tra 20 e 29. Il limite superiore non scese per dieci anni, ma nel 2005 scoprì che 28 mosse sono sempre sufficienti. Tra il 2006 e il 2008 il gioco si fece duro, e l'asticella si abbassò per cinque volte, toccando quota 22 nell'agosto 2008.
La ricerca del numero di Dio era ormai giunta alla sua fase decisiva. La risposta definitiva arrivò esattamente un anno fa, nel luglio 2010, quando Morley Davidson, Tomas Rokicki, Herbert Kociemba e John Dethridge dimostrarono che bastano sempre 20 mosse per riordinare i colori del cubo.
Il numero di Dio è quindi 20. Ma come hanno fatto questi matematici a determinarlo? Utilizzando calcolatori potentissimi e software molto sofisticati che hanno esplorato in modo intelligente l'enorme numero di possibili configurazioni. Gli studi di Davidson e colleghi hanno determinato che su un totale di 43 miliardi di miliardi di possibili configurazioni, circa 300 milioni necessitano di esattamente 20 mosse, mentre la stragrande maggioranza delle configurazioni possono essere risolte in un numero di mosse compreso tra 15 e 19.
Per chi volesse saperne di più:
http://www.cube20.org/
http://www.bbc.co.uk/news/technology-10929159