domenica 24 luglio 2011

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!

3 commenti:

  1. Un minimo locale è un laghetto o un pantano in cui l'acqua pluviale si accumula e poi evapora (si può capire anche dalla vegetazione), un minimo globale è un lago più grande o un corso d'acqua (risposta da geologo). Naturalists do it better!

    RispondiElimina
  2. Anche se non mi permetterei mai di dissentire dai geologi oggi ogni persona civile porta con se un social coso che potrebbe anche servire, al limite, a telefonare ma immediatamente usabile per googlare. Fine.
    No, io no, ma non conto.

    RispondiElimina
  3. grande esempio.
    stavo proprio cercando qualcuno che mi parlasse così della tabu search

    RispondiElimina

La top ten dei miei video su YouTube (1° posto)

Rullo di tamburi! Eccoci finalmente in vetta! E, devo dire, la vetta della classifica dei miei video su YouTube appare per il momento davver...