Home    About me    Publications    Blog    Photo gallery
Some other old good stuff

Fabio Ruini’s blog

Because Italians do it better! What the f**k? Ehm… the blogs, I mean… obviously! :-/

Archivio per Giugno, 2006

Quarti di finale

Stavo cercando una foto della Nazionale da pubblicare in apertura di articolo e, con una veloce ricerca su Google Immagini, guardate un po’ cosa mi è apparso tra i primi risultati:

Nazionale italiana di Sumo

Nientepopodimeno che… la Nazionale italiana di Sumo! :-D

Pure piuttosto carina una delle tipine che ci sono (mi riferisco alla seconda seduta a partire dalla destra). Per quanto il sottoscritto sia un pochino scettico, per natura e per corporatura fisica, a cercare l’approccio con una lottatrice di sumo.

Sto studiando, ma è inutile che cerchi di parlare d’altro. La mia mente è già completamente proiettata alla partita di stasera. Sto contemporaneamente guardando (o meglio “ascoltando”, visto che sono di spalle) Germania – Argentina, su ESPN, con il sempre mittttico TVUPlayer. E’ curioso notare come abbiano dedicato l’intervallo tra primo e secondo tempo a parlare degli “Italian off-field problems”. E una volta tanto non si discuteva di Moggiopoli, ma della tragedia di Pessotto e delle possibili ripercussioni che questa potrebbe avere sulla concentrazione dei nostri Azzurri.

Comunque sia, ha appena fatto gol Ayala. E mi preme sottolineare il fatto che sto godendo come un riccio, memore del bel paginone che il Der Spiegel ha dedicato a noi italiani un paio di giorni fa. Con tutto il cuore, miei cari crucchi, andate a fare in culo.

Stasera appuntamento a Roteglia, col maxischermo appositamente allestito nel piazzale del Ristorante Super 2000, in occasione della seconda “Sagra dello sportivo“. Siete tutti invitati, nessuno escluso. E se come motivazione non vi basta la partita, sappiate che si mangia, si beve e… e basta, credo. Ah no, c’è anche della musica, ma non ho idea di chi ci sia a suonare. Suppongo un qualche gruppo rock con marcate tendenze metallare. Piccola parentesi: Piccio (che sarebbe l’organizzatore della festa in questione) lo capirà mai che gli basterebbe chiamare la più scadente orchestrina di liscio della provincia per decuplicare gli incassi? I bookmakers dicono di no…

Al di là di tutte le considerazioni del precedente paragrafo, il volantino con il programma della festa lo trovate a questo link. Se decidete di venire, abbiate soltanto l’accortezza di non passare davanti al maxischermo durante la partita. A Roteglia diventiamo violenti per queste cose…

Sulla funzione di crescita logistica

Segnalazione veloce veloce anche oggi.

Nell’elaborazione di un piccolo “paper” (parola un po’ grossa, ma “riassunto” non mi suona troppo bene) dedicato alla mappa logistica non poteva ovviamente mancare un accenno alla funzione di crescita logistica.

Esempi di curve logistiche

Il libro al quale sto facendo principalmente riferimento é l’ottimo “Non linearità, caos, complessità. Le dinamiche dei sistemi naturali e sociali“, di Cristoforo Sergio Bertuglia e Franco Vaio.

Quella che ho incluso nel mio lavoro é una trattazione non eccessivamente rigorosa da un punto di vista matematico (il libro di cui sopra è un Bollati Boringhieri e, come sempre mi accade con i volumi di questa casa editrice, la matematica che vi è inclusa all’interno la riesco a masticare per non più del 20% del volume complessivo), ma comunque completa (almeno spero) e, soprattutto, ricca di spunti di varia natura. L’equazione della curva logistica, d’altronde, comportò all’epoca della sua scoperta una vera e propria rivoluzione, poichè si riuscì a ricondurre ad essa una quantità pressochè infinita di fenomeni del mondo naturale ed anche di quello sociale.

Se avete voglia di dare un’occhiata alle quattro paginette che ho scritto finora (in un linguaggio che spero essere piuttosto “terra-terra”), potete scaricare il PDF a questo link.

Buona (eventuale) lettura.

Qualche accenno alla mappa logistica

In questi ultimi giorni sono un po’ preso da mille cose diverse. E così, ieri è saltato l’appuntamento quotidiano con il blog. Anche oggi non ho modo di scrivere più di tanto, quindi mi limito ad un accenno veloce dell’argomento che sto studiando al momento: la mappa logistica.

L’equazione che descrive la mappa logistica (chiamata “mappa” proprio perchè discretizzazione della sua versione continua) è di una semplicità disarmante. Si tratta semplicemente di una successione di valori reali, descritta dalla formula:

Equazione della mappa logistica (versione discreta)

Per quanto sia facile ricavare manualmente il valore della mappa logistica, il ricorso ad un calcolatore permette di ottenere in pochissimi istanti una successione composta da migliaia di valori della x.

Allo scopo, ho preparato un semplicissimo script di MATLAB che, ricevuti in input il valore di λ (compreso tra 1 e 4), il numero di iterazioni ed un valore di partenza compreso nel range [0,1], esegue tutti i calcoli necessari per poi rappresentare graficamente il risultato.

Può sembrare una cosa priva di interesse questa mappa logistica. Ma provate a giocare un po’ con il valore di λ, a parità degli altri parametri. Se ne vedono delle belle.

Vi rimando a domani per una spiegazione più approfondita del comportamento emergente del sistema… :-)

Le coronarie

E’ vero. Fondamentalmente il calcio è un gioco. E’ uno sport, uno svago, un divertimento. Capace però di calamitare gli sguardi di un’intera nazione. Capace di far palpitare i cuori delle persone, di farle gioire, arrabbiare, inveire. Di farle soffrire, nell’accezione più ampia che è possibile attribuire a tale termine.

Il calcio è un qualcosa per uomini veri, per uomini che provano sentimenti forti e sono pronti a lottare per questi“, ebbe a dire il grandissimo Bruno Giordano, commentando una scazzottata avvenuta in tribuna durante un Reggiana – Avellino di un paio di anni fa.

Come si può pensare che il calcio sia solo un gioco? Forse lo è quando si gioca a livello di club. Ma non lo è quando in ballo c’è la tua Nazionale. Quando accendi la televisione e nel sentire i giocatori che cantano l’inno ti vengono le lacrime agli occhi. Quando, a centinaia di chilometri di distanza dal terreno di gioco, urli come se l’arbitro ti potesse sentire. Quando non riesci neppure ad afferrare il telecomando, tale è l’adrenalina che ti scorre nelle vene. Quando il tuo cuore batte all’unisono con le azioni di gioco.

Dunque onore a loro. Alle mie coronarie ed a quelle di tutti gli sportivi italiani.

Coronarie

[Immagine rubata da: http://www.panvascular.com/pagine/info/pazienti/common/coronarie.html]

Perchè non è normale soffrire come abbiamo sofferto oggi pomeriggio. Non è possibile che una squadra di professionisti debba fare tutta questa fatica per sconfiggere una formazione in cui un giocatore, fino a pochi anni fa, di mestiere faceva l’autista di pullman. Non è ammissibile che per 90 minuti il nostro cuore sia a rischio infarto.

Io la odio questa Nazionale di fotomodelli, di analfabeti pluri-miliardari, di burini finiti da un giorno all’altro sulle pagine di tutti i quotidiani, soltanto perchè capaci di dare due calci ad un pallone.

Ma io la amo anche questa Nazionale. Perché è la MIA Nazionale. E perché oggi ci ha fatto vedere di avere due palle grandi così. Capace di stare barricata per 45 minuti nella propria area di rigore. E di venirsene fuori con un guizzo. Con l’irriverente dribbling e l’astuzia da veterano di un terzino qualsiasi, quando tutto sembrava essersi messo per il peggio. Con la freddezza e la strafottenza di un attaccante, che per qualche istante ha pensato di battere il rigore con uno dei suoi “cucchiai”.

Adesso sotto a chi tocca.

Frattali su Mac OS X

Studiare la teoria è sempre cosa buona e giusta. Talvolta, però, si può anche avvertire l’esigenza di dover toccare con mano le cose che si stanno studiando. Con i frattali questo è possibile.

Landscape Fractal

[Immagine rubata da: http://www.imagico.de/pov/gallery1.html]

Se in ambiente Windows sono centinaia i software per la creazione di frattali disponibili in varie forme (freeware, shareware, postcardware e quant’altro), la situazione su Mac OS (specie nell’incarnazione X) è, come spesso accade, un po’ più problematica. Dopo un po’ di ricerche su Google, questo è l’elenco che sono riuscito a elaborare di applicazioni per la creazione di frattali disponibili per il sistema di Cupertino:

Un’altra rassegna di software simile, sempre per Mac OS, è presente a questo link.

Ho scoperto inoltre che, dentro a GIMP, esiste un generatore di frattali IFS. Una brevissima guida al suo utilizzo è presente a questo link. Sempre nei meandri di questo programma open-source, così come accennato nella guida che ho appena linkato, è presente una galleria di frattali, che possono non soltanto essere visualizzati, ma anche modificati a piacimento.

Per ultimo segnalo un ottimo documento di Davide Bucci, intitolato “Introduzione ai frattali di Mandelbrot e Julia“. All’interno della pagina in questione è presente anche il link ad alcune applet Java relative ai frattali, utilizzabili direttamente on line.

Questo è quanto. Dovremmo avere abbastanza materiale da passarci le notti per un bel po’ di tempo…

UPDATE 18/09/2008: date un’occhiata anche a Pocket Fractals.

La geometria della natura: i frattali

Goethe e i romantici sapevano che sono soltanto le leggi della forma a governare la crescita delle piane e il dispiegarsi delle gemme fino allo sviluppo delle foglie in configurazioni specie-specifiche. In questo secolo, il biologo e classicista D’Arcy Wentworth Thompson tentò di fondere l’intuizione romantica con una descrizione matematica dei principi architettonici alla base della cerscita degli animali e delle piane. Ai tempi in cui Thompson elaborava il suo più importante trattato sull’argomento, “On Growth and Form”, la biologia era tuttavia ancora agli inizi e la scienza dei calcolatori non esisteva affatto. Thompson dovette quindi limitarsi all’esame di semplici configurazioni satiche: formulò equazioni che descrivono le linee involute del cavolfiore, le curve meravigliose delle conchiglie di lumache e molluschi e le strutture a forma di ponte del tessuto osseo. Le trasformazioni delle forme che Thompson studiò erano raffigurazioni geometriche di forme esistenti in varie specie di pesci e di mammiferi.

Altra fu la situazione di Aristid Lindenmayer: il biologo olandese era interessato a una descrizione matematica, formale, della crescita delle piante, come Thompson, ma si trovò a lavorare qualche decina di anni dopo e quindi ebbe il vantaggio di poter utilizzare le nuove conoscenze sulla funzione dei geni (il “programma genetico”), oltra alla capacità dei calcolatori di trattare le grammatiche formali, che erano state sviluppate per analizzare la struttura del linguaggio. Alla fine degli anni sessanta, Lindenmayer elaborò un formalismo che oggi è noto come “sistemi-L”. Mentre la cosiddetta grammatica chomskyana è utilizzabile per simulare la creazione di espressioni lunghe e annidate di un linguaggio formale (come una frase, per esempio una frase tra parentesi come questa, che viene resa più lunga [e ancor più lunga]), Lindenmayer riuscì a creare un sistema capace non soltanto di generare sequenze unidimensionali sempre più lunghe, ma anche di applicare contemporaneamente le regole in molti punti delle sequenze. I testi sono sequenze lineari di parole, invece gli organismi si sviluppano in parallelo: le corpo si creano molte cellule allo stesso tempo, l’albero genera i rami contemporaneamente in posti diversi. Anche gli automi cellulari eseguono calcoli in parallelo, ma le configurazioni che creano si estendono soltanto alla fila di cellule in prima posizione. Gli alberi e i cespugli creano nuovi germogli di ramificazioni in tutte le direzioni contemporaneamente.

I modi sono i più svariati: la fauna terreste sembra crescere secondo un numero infinito di modi. Ciò malgrado, esistono alcuni rapporti costanti che caratterizzano la topologia vegetale: ogni pianta ha una base dalla qaule si propagano, verso il basso, le radici e un asse centrale che cresce verso l’alto (il tronco di un albero e lo stelo di un’erba). Sull’asse principale (l’asse di ordine zero) si trovano, su alcuni punti di ramificazione, foglie oppure assi del primo ordine, su questi ultimi si trovano assi del secondo ordine e così via. Ogni asse ha una base e una sommità. Le foglie sono sempre terminali: assi e fusti non partono mai dal bordo di una foglia o dalla sua sommità. Queste condizioni costanti costituiscono le relazioni fondamentali del sistema formale sviluppato da Lindenmayer per descrivere le regole di crescita dei singoli elementi. Il sistema si può considerare come una serie di ricette, o algoritmi, per la creazione delle diverse parti della pianta.

[...] Qual è il motivo per trasformare una struttura ramificata in una formula? I sistemi-L si basano su un principio che potremmo chiamare di “riscrittura”: si tratta di una tecnica con la quale si definiscono oggetti complessi sostituendo le parti di un oggetto di partenza semplice con altri oggetti, in base a regole specifiche, e ripetendo poi il procedimento con l’oggetto che si è formato. Per citare un esempio, la curva a forma di cristallo di ghiaccio, detta curva di Koch, si costruisce con un triangolo equilatero detto oggetto di partenze, un generatore costituito dalla linea spezzata _^_ (di quattro piccoli frammenti uguali) e una regola di riscrittura che rimpiazza ogni tratto dell’oggetto (all’inizio ogni lato del triangolo) con la linea spezzata; ogni volta che si riapplica la regola (in modo ricorsivo), il numero di segmenti che compongono il nuovo oggetto quadruplica. Nella programmazione ricorsiva si utilizza il medesimo principio. Le parti dentellate della curva diventano sempre più numerose e di dimensioni sempre più ridotte, in modo che ben presto è necessaria la lente di ingrandimento per osservare i dettagli. Quando le si ingrandisce, assomigliano a se stesse a ogni livello: sono “autosimili”.

Molte piante hanno forme decisamente autosimili, come le ramificazioni di un albero sempreverde o le foglie di una felce: ingrandendo una sezione di queste piante, si trova la stessa configurazione ripetuta più volte. Si può sfruttare questa caratteristica quando il sistema-L deve specificare una pianta mediante la riscrittura. Si sostituisce un pezzo semplice dell’asse con un pezzo formato da tre segmenti con due rami laterali; si può poi ripetere il processo più volte, lasciando crescere ogni volta la pianta per un periodo opportuno.

Se gli angoli possono variare di ampiezza, questa tecnica produce un numero infinito di forme di ramificazione molto realistiche che si possono generare al calcolatore. Insieme all’esperto di computer graphic Przemyslav Prusinkiewicz, Lindenmayer ha creato sul calcolatore un paradiso di giardini fioriti, con meravigliosi lillà, garofani, girasoli e altre piante ornamentali disegnate in modo iperrealistico.

Foglia di felce frattale

Non è sorprendente che queste immagini di squisita perfezione ricordino in qualche modo i cartoni animati: sembrano troppo puri e perfetti, mentre gli abbozzi in bianco e nero generati al calcolatore paiono più schiette. Col tempo e con una maggiore efficienza computazionale, comunque, si riusciranno a ottenere piante più “autentiche”. I colleghi di Prusinkiewicz e Lindenmayer hanno sperimentato che cosa rende più naturali le piante, facendo sì che siano meno perfette e un poco asimmetriche: si possono dare istruzioni al calcolatore di “tirare a sorte” il genere di ramificazione o di foglia che apparirà al successivo passo computazionale di crescita (un algoritmo di generazione di numeri casuali determina lo sviluppo delle singole parti della pianta algoritmica).

I vortici della computer graphic catturano la dinamica autentica delle piante? Al livello generale, esistono alcune caratteristiche comuni: le strutture create dalle piante naturali si evolvono in parallelo, seguendo una logica operativa realmente locale, tanto quanto i rami, le foglie e i fiori artificiali dei sistemi-L. In entrambi i casi, le regole applicate, genetiche e algoritmiche, sono semplici: l’applicazione ripetura delle regole genera una bellezza spesso imprevedibile, che si presenta in quelle che potremmo chiamare configurazioni di grande profondità logica. Le piante generate al calcolatore assomigliano spesso in maniera fedele ai loro antenati originali. Nell’ambito di questo filone realistico del tutto singolare l’imitazione scientifica sembra avere un discreto successo.

Se non altro, questa tecnica si può utilizzare per realizzare imitazioni realistiche di scenari naturali ein film d’animazione. E’ una realtà artificiale seducente, che non è arte, ma che potrebbe essere un mezzo per un’arte possibile, sebbene l’arte possa difficilmente progredire identificandosi totalmente con il suo oggetto.

Tutto ciò ricorda la storiella dell’uomo che chiede a Picasso: “Perchè non dipinge le persone così come appaiono veramente?”. “Che cosa intende?”, chiede Picasso. “Così come appare mia moglie qui, per esempio”, dice l’uomo tirando fuori una fotografia. Picasso replica: “E’ piuttosto piccina, sa. E molto piatta!”.

Come osserva Peter Oppenhemer, ricercatore della vita artificiale, il fatto che una pianta generata al calcolatore assomigli a suoi antenati originali non è affatto una garanzia che l’algoritmo che ha creato l’immagine corrisponda al meccanismo che ha generato la pianta. Ciò significa che l’immagine potrebbe sembrare giusta per motivi che non sono corretti. Le immagini frattali di montagne, generate mediante suddivisioni ricorsive di superfici di partenza piane oppure dal profilo regolare, appaiono a volte molto convincenti, ma noi sappiamo benissimo che le superfici irregolari delle montagne non si sono formate in questo modo. Le immagini rivelano il nostro modo di percepire le montagne, più che essere l’espressione di un dato di fatto di carattere geologico. La nostra ossessione riguardo alle piante generate al calcolatore è centrata tanto sull’osservatore quanto su ciò che si osserva. E’ fuor di dubbio che la struttura apparentemente complessa di una pianta può essere il risultato dell’applicazione reiterata (ricorsiva) di un numero di regole genetiche relativamente piccolo. L’anatomista austriaco Rupert Riedl sottolinea la necessità di risparmiare informazione nella codifica di un organismo: se si può affermare che il codice per la creazione del lobo di una foglia di felce o di un singolo ago di pino è rappresentato (indirettamente) nel DNA – vale a dire scritto in forma di un codice epigenetico, che corrisponde a un algoritmo per l’ago di pino – allora è sufficiente che tale codice sia presente in un unico posto dell’intero genoma (il materiale genetico completo che si trova in ogni singola cellula del pino). L’algortimo “per l’ago di pino” può essere quindi applicato dall’albero più e più volte, ogni volta che deve essere creato un ago. In questo contesto, “algoritmo” non è altro che una metafora, poichè nella vita reale la creazione della forma non è necesasriamente specificata nello stesso modo esplicito in cui un algoritmo per il calcolatore specifica la forma di un fiore artificiale.

Non si dimentichi, inoltre, il livello o l’aspetto del sistema biologico che si desidera rappresentare. Ci si sta occupando della creazione della forma generale della struttura di ramificazione in un pino, o della distribuzione degli aghi su un nuovo ramo, oppure della struttura interna e della forma esteriore dei singoli aghi di pino? I sistemi di Lindenmayer funzionano spesso per la macrostruttura, per l’insieme. Un ago di pino, tuttavia, è esso stesso un minuscolo e complicato insieme, costituito da diverse parti e richiede quindi altri tipi di modelli.

[tratto da: Claus Emmeche, "Il giardino nella macchina. Della vita artificiale"]

Perché tutto questo, vi starete chiedendo. E io rispondo che, al di là del fatto che queste sono state le uniche pagine che ho finora trovato interessanti nel libro di Emmeche, questa è un’ottima scusa per introdurre l’argomento dei frattali, che ho intenzione di iniziare a studiare nel pomeriggio di oggi.

Nel caso in cui abbiate voglia di seguirmi in questo allegro viaggio, come punto di partenza non posso che suggerirvi l’ottimo lavoro del buon Franco Federici (che devo un po’ adulare, siccome mi ha dato il permesso di pubblicare il suo materiale…):

Se poi non ne aveste ancora abbastanza e vorreste saperne di più, il buon Franco ci suggerisce di dare un’occhiata alle seguenti risorse disponibili sulla rete:

E se ancora non vi dovesse bastare, credo che come opzione rimanga soltanto la seduta da una psicologa. Tra l’altro posso consigliarvene una straordinaria…

Tutto quello che avreste sempre voluto sapere sui percettroni, ma che non avete mai osato chiedere

A dir la verità, ritengo decisamente più plausibile l’idea secondo la quale dei percettroni non ve ne sia mai fregato niente (dico male, Fungo?). Ma siccome non posso scartare aprioristicamente alcuna ipotesi (si vede che vengo da un pomeriggio di derivate, vero?), con questo post segnalo che ho finito di risistemare i miei appunti che trattano l’argomento.

Esempio di percettrone

Sono una decina di pagine, in comodo formato PDF, che potete scaricare a questo link.

Se poi avete voglia di approfondire un pochino la questione da un punto di vista più matematico (che sapete benissimo non essere il mio forte) vi rimando alla presentazione del buon Paxel: “Reti Neurali con apprendimento supervisionato – dal neurone all’apprendimento con rinforzo, passando per i percettroni“. Che così non si può più lamentare del fatto che non linko mai il suo sito. Anche se in realtà non si è mai lamentato. Ma so che lo avrebbe fatto, se solo ne avesse avuto il tempo.

Scappo. Stasera pizza, partita in tv, patatine e qualche litro di birra.

E che nessuno parli di neuroni! :-D

Blog momentaneamente chiuso per mal di testa…

… che purtroppo non é un mal di testa post-festeggiamenti per la vittoria della Nazionale.

Mal di testa

[Foto rubacchiata da: http://www.associazionechiropratici.it/chiropratica/utile_per/Mal_di_Testa.html]

Anche perchè dopo aver visto la partita di oggi pomeriggio non è che ci sia proprio quella gran voglia di festeggiare. Lippi, quand’è che lo mettiamo in panchina quello zombie di Totti? Vogliamo continuare a giocare in 10 per tutto il Mondiale? Tra l’altro, ho come l’impressione che l’improvvisa esigenza di privacy che hanno avvertito questa sera in FIGC sia dovuta al fatto che tu ci sei in mezzo fino al collo, caro il mio CT.

Arridatece Vittorio Pozzo! E i servizi segreti che provocano le intossicazioni alimentari ai giocatori delle squadre avversarie…

Ricerca A*

La ricerca golosa minimizza il costo stimato dell’obiettivo, h(n), e pertanto riduce considerevolmente il costo della ricerca. Come contraltare, essa non è una strategia né ottimale, né completa. La ricerca a costo uniforme, da canto suo, minimizza il costo del cammino corrente g(n) ed è sia ottimale che completa, ma spesso anche molto inefficiente.

E’ possibile combinare queste due strategie per ottenere i vantaggi di entrambe, mettendo insieme le due funzioni di valutazione attraverso una semplice somma:

f(n)=g(n)+h(n)

Dal momento che g(n) è una misura del costo del cammino dal nodo iniziale al nodo n e che h(n) è il costo stimato del cammino da n all’obiettivo più conveniente, f(n) risulta essere il costo stimato della soluzione più conveniente attraverso n.

Una strategia che espande prima il nodo con il più basso valore di f può risultare completa ed ottimale, a patto di applicare una semplice restrizione sulla funzione h. Tale restrizione consiste nella scelta di una funzione h che non sopravvaluti mai il costo per raggiungere l’obiettivo (come nel caso dell’utilizzo, quale funzione h, della distanza in linea d’aria dall’obiettivo). Questo “ottimismo” si trasferisce anche sulla funzione f: se h è ammissibile, f(n) non sopravvaluta mai il costo reale della soluzione migliore attraverso n.

La ricerca best-first che utilizza f come funzione di valutazione ed una funzione ammissibile h è nota come ricerca A*.

Comportamento della ricerca A*

Osserviamo la figura seguente:

Figura 4.4

Lo sviluppo in sequenza dei nodi è: Arad-Sibiu-Rimnicu. Al di là del caso specifico, però, è interessante notare come, lungo qualsiasi cammino che parte dalla radice, il costo f non decresce mai. Tale caratteristica è presente per quasi tutte le euristiche ammissibili, che nella maggior parte dei casi risultano infatti godere della proprietà di monotonia.

Nel raro caso in cui si stia utilizzando una funzione euristica non-monotona, è possibile apportare una semplice correzione in grado di ristabilire la monotonia. E’ infatti sufficiente controllare, ogni volta che viene generato un nuovo nodo n’ a partire da un nodo-genitore n, se il suo costo f sia minore del costo f del suo genitore: se lo è, usiamo al suo posto il costo f del genitore. Da un punto di vista formale:

f(n’)=max(f(n),g(n’)+h(n’))

Tale equazione è detta di pathmax. Utilizzandola, f risulterà sempre essere non-decrescente lungo qualunque cammino che parte dalla radice, a condizione che h sia ammissibile.

Siccome f non decresce mai lungo qualsiasi cammino dalla radice, possiamo disegnare concettualmente delle frontiere nello spazio degli stati. Nella figura che segue, la frontiera contrassegnata dall’etichetta “400” contiene al suo interno tutti i nodi con f(n) minore o uguale a 400.

Figura 4.5

Poiché A* espande il nodo foglia in cui f ha valore più basso, possiamo vedere che una ricerca di questo tipo si apre a ventaglio a partire dal nodo iniziale, aggiungendo nodi in fasce concentriche con costo f crescente. Una ricerca a costo uniforme (che possiamo vedere come una ricerca A* con h=0) farà sì che le fasce saranno circolari intorno allo stato iniziale. Con un’euristica più accurata le fasce si allungheranno invece verso lo stato obiettivo e tenderanno ad assottigliarsi in modo più preciso intorno al cammino ottimale.

Tra gli algoritmi ottimali di questo tipo (algoritmi che estendono i cammini di ricerca a partire dalla radice), A* è ottimamente efficiente per qualsiasi funzione euristica considerata. In sostanza, non esiste nessun altro algoritmo ottimale che garantisce di espandere un minor numero di nodi rispetto ad A*.

Dimostrazione dell’ottimalità di A*

Supponiamo di avere:

  • G: stato obiettivo ottimale, con costo di cammino f*;
  • G2: stato obiettivo non ottimale, con costo di cammino g(G2)>f*.

Immaginiamo di essere nella situazione in cui A* ha selezionato G2 dalla coda. Siccome G2 è uno stato obiettivo, avremmo in questo caso terminato la ricerca con una soluzione non-ottimale. Vediamo perché una situazione di questo genere non è possibile.

Si consideri un nodo n che sia correntemente un nodo foglia su un cammino ottimale verso G. Siccome h è un’euristica ammissibile, sappiamo che:

f* >= f(n)


Se G2 è stato scelto al posto del nodo n per l’espansione, allora deve valere:

f(n) >= f(G2)


Combinando queste due espressioni, otteniamo:

f* >= f(G2)


Abbiamo però detto che G2 è uno stato obiettivo e pertanto:

h(G2) = 0


Avendo definito f(n)=g(n)+h(n), risulta dunque:

f(G2) = g(G2)


Ciò che risulta deducibile a questo punto è che:

f* >= g(G2)

Ma questo non può essere vero, in quanto contraddice l’assunzione che G2 sia non ottimale. Deve pertanto accadere che A* non selezioni mai per l’espansione un obiettivo non ottimale. Quindi, poiché restituisce una soluzione soltanto dopo averla selezionata per l’espansione, A* è un algoritmo ottimale.

Dimostrazione della completezza di A*

La strategia A* espande i nodi in ordine di f crescente e deve pertanto fare, prima o poi, un’espansione per raggiungere uno stato obiettivo. Ciò è vero, naturalmente, a meno che non ci siano infiniti nodi f(n).

Si possono avere infiniti nodi soltanto in due casi:

  • esiste un nodo con fattore di ramificazione infinito;
  • esiste un cammino con costo del percorso finito, ma con un numero infinito di nodi (come nel caso del paradosso di Zenone).

L’affermazione corretta è dunque che A* è completa su grafi localmente finiti (grafi con un fattore di ramificazione finito), a condizione che vi sia qualche costante positiva k, tale che ogni operatore costi almeno k.

Complessità di A*

Abbiamo visto come A* sia completa, ottimale ed ottimamente efficiente tra tutti questi algoritmi. Sfortunatamente, per la maggior parte dei problemi, il numero di nodi nello spazio di ricerca della frontiera dell’obiettivo è però ancora esponenziale nella lunghezza del risultato. Non approfondiremo qui la prova del risultato: si tenga comunque presente che si verifica una crescita esponenziale a meno che l’errore nella funzione euristica non cresca più velocemente rispetto al logaritmo del costo reale del cammino. Per quasi tutte le euristiche utilizzate nella pratica, l’errore è almeno proporzionale al costo del cammino e la crescita esponenziale risultante prima o poi supera la capacità di qualsiasi computer. Memorizzando tutti i nodi generati, ad ogni modo, A* finisce solitamente per esaurire lo spazio in memoria prima del tempo.

[tratto da: Russel, Norving - “Artificial Intelligence: a modern approach”]

Metodi di ricerca informata

Nella maggior parte dei casi, sfortunatamente, le strategie di ricerca non informata che abbiamo descritto nel paragrafo precedente risultano essere incredibilmente inefficienti. Vediamo dunque come una strategia di ricerca informata, ossia che usi conoscenza specifica sul problema, possa trovare soluzioni in maniera più efficace.

Ricerca best-first

Se pianifichiamo di utilizzare l’algoritmo RICERCA-GENERALE visto in precedenza, l’unico posto in cui si può applicare la conoscenza dell’ambiente è nella funzione di inserimento in coda, la quale determina il prossimo nodo da espandere. Solitamente, la conoscenza per determinare tale nodo viene fornita da una funzione di valutazione che restituisce un numero che descrive la desiderabilità (o la non desiderabilità) relativa all’espansione del nodo.

Quando i nodi sono ordinati in maniera tale che venga espanso per primo quello con valutazione migliore, la strategia risultante è detta ricerca best-first. Si noti tuttavia che il nome “best-first” ha motivazioni storiche, ma è impreciso: se potessimo realmente espandere il nodo migliore “prima”, non sarebbe affatto una ricerca, ma piuttosto una marcia diretta verso l’obiettivo. La sola cosa che possiamo fare è quella di scegliere il nodo che “sembra” essere il migliore secondo la funzione di valutazione utilizzata.

Così come esiste un’intera famiglia di algoritmi RICERCA-GENERALE con differenti funzioni di ordinamento, c’è anche un’intera famiglia di algoritmi RICERCA-BEST-FIRTS con differenti funzioni di valutazione. Poiché mirano a trovare soluzioni con basso costo, questi algoritmi utilizzano tipicamente una qualche misura di stima del costo della soluzione, cercando di minimizzarla. E’ qualcosa di concettualmente simile all’uso del costo del cammino g per decidere quale cammino estendere, il quale però non è in grado di dirigere la ricerca verso l’obiettivo. Per poter focalizzare la ricerca, la misura deve incorporare qualche stima del costo del cammino da uno stato al più vicino stato obiettivo.

Minimizzare il costo stimato per raggiungere un obiettivo: ricerca golosa

Una delle strategie più semplici di ricerca best-first è quella di minimizzare il costo stimato per raggiungere l’obiettivo: il nodo il cui stato è giudicato il più vicino allo stato obiettivo viene sempre espanso prima.

Nella maggior parte dei problemi, il costo per raggiungere l’obiettivo a partire da uno stato particolare non può essere determinato con esattezza, ma semplicemente stimato. Una funzione il cui compito è quello di calcolare tali stime di costo è detta una funzione euristica ed è di solito indicata dalla lettera h:


h(n)
= costo stimato del cammino più conveniente dallo stato del nodo n ad uno stato obiettivo

Fondamentalmente, h può essere una funzione qualsiasi: si richiede solo che h(n)=0 se n è un nodo obiettivo. Una ricerca best-first che utilizza h per selezionare il nodo successivo da espandere è detta ricerca golosa.

Per farsi un’idea di come si presenti una funzione euristica, dobbiamo scegliere un particolare problema: ritorniamo a quello della ricerca di itinerario da Arad a Bucarest. Per un problema di questo tipo, una buona funzione euristica è la distanza in linea d’aria dall’obiettivo:

h(n) = distanza in linea d’aria tra n e la posizione dell’obiettivo

Naturalmente possiamo calcolare i valori di questa funzione h soltanto se conosciamo le coordinate sulla mappa delle città in Romania. Supponiamo pertanto di essere in questa condizione, sintetizzata nella figura che segue:

Figura 4.3

La ricerca golosa è chiamata con questo nome un po’ particolare, poiché preferisce prendere il boccone più grosso possibile dal costo rimanente per raggiungere l’obiettivo, senza preoccuparsi se questa sarà la cosa migliore da fare a lungo termine. Ciò è evidente se guardiamo l’esempio di ricerca golosa riportata qui sotto:

Figura 4.2

Espandendo sempre il nodo con il minor valore di h, la ricerca arriva ad individuare come soluzione il percorso Arad-Sibiu-Fagaras-Bucarest. Tuttavia tale soluzione non è ottimale: questo cammino è infatti di 32km più lungo rispetto a quello che passa attraverso Rimnicu Vilcea e Pitesti.

La ricerca golosa presenta sostanzialmente gli stessi pregi e difetti della ricerca in profondità, in quanto può dare luogo a “false partenze” (ad esempio, se immaginiamo di andare da Iasi a Fagaras, l’euristica suggerisce di espandere prima Neamt, città che costituisce però un vicolo cieco), preferisce seguire un singolo cammino fino al raggiungimento dell’obiettivo, non è una strategia ottimale ed è incompleta.

[tratto da: Russel, Norving - “Artificial Intelligence: a modern approach”]

Pagina Successiva »