1 1 CERCARE SOLUZIONI CERCARE SOLUZIONI Generare sequenze di azioni. • • Espansione: Espansione: si parte da uno stato e applicando gli si parte da uno stato e applicando gli operatori (o la funzione successore) si generano nuovi operatori (o la funzione successore) si generano nuovi stati. stati. • • Strategia di ricerca: Strategia di ricerca: ad ogni passo scegliere quale stato ad ogni passo scegliere quale stato espandere. espandere. • • Albero di ricerca: Albero di ricerca: rappresenta l’espansione degli stati a rappresenta l’espansione degli stati a partire dallo stato iniziale (la radice dell’albero). partire dallo stato iniziale (la radice dell’albero). • • Le foglie dell’albero rappresentano gli stati da espandere. Le foglie dell’albero rappresentano gli stati da espandere. 2 2 STRATEGIE DI RICERCA STRATEGIE DI RICERCA • • La scelta di quale stato espandere nell’albero di ricerca La scelta di quale stato espandere nell’albero di ricerca prende il nome di prende il nome di strategia strategia . . • • Abbiamo strategie informate (o euristiche) e non Abbiamo strategie informate (o euristiche) e non informate ( informate ( blind blind ). ). • • Le Le stategie stategie si valutano in base a quattro criteri: si valutano in base a quattro criteri: – – Completezza: la strategia garantisce di trovare una soluzione Completezza: la strategia garantisce di trovare una soluzione quando ne esiste una? quando ne esiste una? – – Complessità temporale: quanto tempo occorre per trovare una Complessità temporale: quanto tempo occorre per trovare una soluzione? soluzione? – – Complessità spaziale: Quanta memoria occorre per effettuare la Complessità spaziale: Quanta memoria occorre per effettuare la ricerca? ricerca? – – Ottimalità Ottimalità : la strategia trova la soluzione di “qualità massima” : la strategia trova la soluzione di “qualità massima” quando ci sono più soluzioni? quando ci sono più soluzioni?
Transcript
11
CERCARE SOLUZIONICERCARE SOLUZIONI
Generare sequenze di azioni.
•• Espansione:Espansione: si parte da uno stato e applicando gli si parte da uno stato e applicando gli operatori (o la funzione successore) si generano nuovi operatori (o la funzione successore) si generano nuovi stati. stati.
•• Strategia di ricerca: Strategia di ricerca: ad ogni passo scegliere quale stato ad ogni passo scegliere quale stato espandere.espandere.
•• Albero di ricerca:Albero di ricerca: rappresenta l’espansione degli stati a rappresenta l’espansione degli stati a partire dallo stato iniziale (la radice dell’albero).partire dallo stato iniziale (la radice dell’albero).
•• Le foglie dell’albero rappresentano gli stati da espandere.Le foglie dell’albero rappresentano gli stati da espandere.
22
STRATEGIE DI RICERCASTRATEGIE DI RICERCA
•• La scelta di quale stato espandere nell’albero di ricerca La scelta di quale stato espandere nell’albero di ricerca prende il nome di prende il nome di strategiastrategia..
•• Abbiamo strategie informate (o euristiche) e non Abbiamo strategie informate (o euristiche) e non informate (informate (blindblind).).
•• Le Le stategiestategie si valutano in base a quattro criteri:si valutano in base a quattro criteri:–– Completezza: la strategia garantisce di trovare una soluzione Completezza: la strategia garantisce di trovare una soluzione
quando ne esiste una?quando ne esiste una?–– Complessità temporale: quanto tempo occorre per trovare una Complessità temporale: quanto tempo occorre per trovare una
soluzione?soluzione?–– Complessità spaziale: Quanta memoria occorre per effettuare la Complessità spaziale: Quanta memoria occorre per effettuare la
ricerca?ricerca?–– OttimalitàOttimalità: la strategia trova la soluzione di “qualità massima” : la strategia trova la soluzione di “qualità massima”
quando ci sono più soluzioni?quando ci sono più soluzioni?
33
STRATEGIE DI RICERCASTRATEGIE DI RICERCA
•• STRATEGIE DI RICERCASTRATEGIE DI RICERCA NONNON--INFORMATE:INFORMATE:
–– breadthbreadth--first (a first (a costocosto uniformeuniforme););
–– depthdepth--first; first;
–– depthdepth--firstfirst a profondità limitata;a profondità limitata;
–– ad approfondimento iterativo.ad approfondimento iterativo.
44
Strutture dati per l’ albero di ricerca (struttura di un nodo)
•Lo stato nello spazio degli stati a cui il nodo corrisponde.
•Il nodo genitore.
•L’operatore che è stato applicato per ottenere il nodo.
•La profondità del nodo.
•Il costo del cammino dallo stato iniziale al nodo
55
L’algoritmo generale di ricerca
66
L’algoritmo generale di ricerca
Tramite l’argomento Queuing-Fn viene passata unafunzione per accodare i nodi ottenuti dall’espansione
77
BREADTHBREADTH--FIRST FIRST
•• Definizione di profondità:Definizione di profondità:–– La PROFONDITÀ del nodo da cui si parte è uguale a 0; la profondiLa PROFONDITÀ del nodo da cui si parte è uguale a 0; la profondità di un tà di un
qualunque altro nodo è la profondità del genitore più 1. qualunque altro nodo è la profondità del genitore più 1.
•• ESPANDE sempre i nodi MENO PROFONDI dell'albero. ESPANDE sempre i nodi MENO PROFONDI dell'albero.
•• Nel caso peggiore, se abbiamo profondità d e fattore di ramificaNel caso peggiore, se abbiamo profondità d e fattore di ramificazione b zione b il numero massimo di nodi espansi nel caso peggiore sarà il numero massimo di nodi espansi nel caso peggiore sarà bbdd. . (complessità temporale).(complessità temporale).
–– 1 + b + b1 + b + b22 + b+ b33 +…+(+…+(bbdd –– 1) 1) ----> b> bdd
88
BREADTHBREADTH--FIRST FIRST
•• All’ultimo livello sottraiamo 1 perché il goal non viene ulterioAll’ultimo livello sottraiamo 1 perché il goal non viene ulteriormente rmente espanso.espanso.
•• Questo valore coincide anche con la complessità spaziale (numeroQuesto valore coincide anche con la complessità spaziale (numero di di nodi che manteniamo contemporaneamente in memoria).nodi che manteniamo contemporaneamente in memoria).
•• L'esplorazione dell'albero avviene tenendo L'esplorazione dell'albero avviene tenendo CONTEMPORANEAMENTE aperte più strade.CONTEMPORANEAMENTE aperte più strade.
•• Tale strategia garantisce la COMPLETEZZA, ma NON permette una Tale strategia garantisce la COMPLETEZZA, ma NON permette una EFFICIENTE IMPLEMENTAZIONE su sistemi EFFICIENTE IMPLEMENTAZIONE su sistemi monomono--processoreprocessore(architetture multi(architetture multi--processore).processore).
99
BREADTHBREADTH--FIRSTFIRST•• In particolare, con profondità 10 e fattore di ramificazione 10 In particolare, con profondità 10 e fattore di ramificazione 10 dovremmo dovremmo
espandere 10espandere 101010 nodi, (tempo 128 giorni e 1 nodi, (tempo 128 giorni e 1 terabyteterabyte di memoria di memoria immaginando che un nodo richieda 100 byte di memoria e vengano eimmaginando che un nodo richieda 100 byte di memoria e vengano espansi spansi 1000 nodi al secondo).1000 nodi al secondo).
•• Il problema della memoria sembra essere il più grave.Il problema della memoria sembra essere il più grave.
•• Trova sempre il cammino a costo minimo se il costo coincide con Trova sempre il cammino a costo minimo se il costo coincide con la profondità la profondità (altrimenti dovremmo utilizzare un’altra strategia che espande s(altrimenti dovremmo utilizzare un’altra strategia che espande sempre il nodo empre il nodo a costo minimo a costo minimo strategia a costo uniforme). strategia a costo uniforme).
•• La strategia a costo uniforme è completa e, a differenza della rLa strategia a costo uniforme è completa e, a differenza della ricerca in icerca in ampiezza, ottimale anche quando gli operatori non hanno costi unampiezza, ottimale anche quando gli operatori non hanno costi uniformi. iformi. (complessità temporale e spaziale uguale a quella in ampiezza).(complessità temporale e spaziale uguale a quella in ampiezza).
1010
n0
n1 n2 n3 n4
n11 n12 n13 n21n22 n31 n32 n33 n41 n42
BREADTHBREADTH--FIRSTFIRST
0
1 2 3 4
5 6 7 8 9 10 11 12 13 14
1111
Ricerca in ampiezza
QueueingFn = metti i successori alla fine dellacoda
1212
b - massimo fattore di diramazione dell’alberodi ricerca
d - profondità della soluzione a costo minimo
m - massima profondità dello spazio degli stati(può essere infinita)
1313
Ricerca in ampiezza
Lo svantaggio principale è l’eccessiva occupazione di memoria. Nell’esempio si suppone che il fattore di ramificazione sia b=10. Si espandono 1000 nodi/secondo. Ogni nodo occupa 100 byte di memoria.
1414
Ricerca a costo uniformeciascun nodo è etichettato con il costo g(n)
QueueingFn = inserisci i successori in ordine di costo di cammino crescente
1515
STRATEGIE DI RICERCA:STRATEGIE DI RICERCA:DEPTH FIRSTDEPTH FIRST
•• ESPANDE per primi nodi PIÙ PROFONDI;ESPANDE per primi nodi PIÙ PROFONDI;
•• I nodi di UGUALE PROFONDITÀ vengono selezionati I nodi di UGUALE PROFONDITÀ vengono selezionati ARBITRARIAMENTE (quelli più a sinistra).ARBITRARIAMENTE (quelli più a sinistra).
•• La ricerca in profondità richiede un’occupazione di memoria moltLa ricerca in profondità richiede un’occupazione di memoria molto o modesta.modesta.
•• Per uno spazio degli stati con fattore di ramificazione b e profPer uno spazio degli stati con fattore di ramificazione b e profondità ondità massima d la ricerca richiede la memorizzazione di b*d nodi.massima d la ricerca richiede la memorizzazione di b*d nodi.
•• La complessità temporale è invece analoga a quella in ampiezza.La complessità temporale è invece analoga a quella in ampiezza.
•• Nel caso peggiore, se abbiamo profondità d e fattore di ramificaNel caso peggiore, se abbiamo profondità d e fattore di ramificazione zione b il numero massimo di nodi espansi nel caso peggiore sarà b il numero massimo di nodi espansi nel caso peggiore sarà bbdd. . (complessità temporale).(complessità temporale).
1616
Strategia Strategia DepthDepth--firstfirst•• EFFICIENTE dal punto di vista EFFICIENTE dal punto di vista realizzativorealizzativo: può essere memorizzata : può essere memorizzata
una sola strada alla volta (un unico una sola strada alla volta (un unico stackstack))
•• Può essere NONPuò essere NON--COMPLETA con possibili loop in presenza di rami COMPLETA con possibili loop in presenza di rami infiniti.(INTERPRETE PROLOG).infiniti.(INTERPRETE PROLOG).
••
1717
Strategia Strategia DepthDepth--firstfirstn0
n1 n2 n3 n4
n11 n12 n13 n21n22 n31 n32 n33 n41 n42
0
1 5 8 12
2 3 4 6 7 9 10 11 13 14
1818
Ricerca in profondità
QueueingFn = inserisci i successori all’inizio della coda.si assume che i nodi di profondità 3 non abbiano successori
1919
b - massimo fattore di diramazione dell’albero di ricerca
d - profondità della soluzione a costo minimo
m - massima profondità dello spazio degli stati (puòessere infinita)
2020
SEMPLICE ALGORITMO DI RICERCA:SEMPLICE ALGORITMO DI RICERCA:
–– Un nodo di (un albero di) ricerca e’ una strada da uno stato X aUn nodo di (un albero di) ricerca e’ una strada da uno stato X allo llo stato iniziale (ad esempio [X,B,A,S])stato iniziale (ad esempio [X,B,A,S])
–– Lo stato di un nodo di ricerca e’ lo stato Lo stato di un nodo di ricerca e’ lo stato piu’piu’ recente della stradarecente della strada–– Sia L una lista di nodi (ad esempio [[X,B,A,S], [C,B,A,S])Sia L una lista di nodi (ad esempio [[X,B,A,S], [C,B,A,S])–– Sia S lo stato iniziale.Sia S lo stato iniziale.
1.1. InizializzaInizializza L con S (L con S (VisitedVisited = [S])= [S])2.2. Estrai un nodo n da LEstrai un nodo n da L. Se L è vuota fallisci;. Se L è vuota fallisci;3.3. Se lo stato di n è il goal fermati e ritorna esso più la strada Se lo stato di n è il goal fermati e ritorna esso più la strada
percorsa per raggiungerlo (n).percorsa per raggiungerlo (n).4.4. Altrimenti rimuovi n da L e Altrimenti rimuovi n da L e aggiungi a Laggiungi a L tutti i nodi figli di n non in tutti i nodi figli di n non in
VisitedVisited, con la strada percorsa partendo dal nodo iniziale. , con la strada percorsa partendo dal nodo iniziale. 5.5. AggiungiAggiungi talitali figlifigli a Visiteda Visited6.6. Ritorna al passo 2Ritorna al passo 2
•• DepthDepth--first:first:–– EstraiEstrai ilil primo primo elementoelemento didi Q;Q;
–– AggiungiAggiungi I I nodinodi figlifigli in in testatesta a Qa Q
•• BreadthBreadth--firstfirst–– EstraiEstrai ilil primo primo elementoelemento didi Q;Q;
–– AggiungiAggiungi I I nodinodi figlifigli in coda a Qin coda a Q
•• BestBest--firstfirst–– EstraiEstrai ilil ““miglioremigliore” ” elementoelemento didi Q (Q (misuratomisurato come come valorevalore euristicoeuristico
dellodello statostato).).
–– AggiungiAggiungi I I nodinodi figlifigli in in unauna ((qualunquequalunque) ) posizioneposizione didi Q.Q.
2222
ESEMPIO: DEPTHESEMPIO: DEPTH--FIRST FIRST
•• DepthDepth--firstfirst: figli espansi aggiunti in testa a L.: figli espansi aggiunti in testa a L.::–– n0n0–– n1,n2,n3,n4n1,n2,n3,n4–– n11,n12,n13,n2,n3,n4n11,n12,n13,n2,n3,n4–– n11,n12,n13,n2,n3,n4n11,n12,n13,n2,n3,n4–– n12,n13,n2,n3,n4n12,n13,n2,n3,n4–– n13,n2,n3,n4n13,n2,n3,n4–– n2,n3,n4n2,n3,n4–– n21n21,n22,n3,n4 ,n22,n3,n4 SuccessoSuccesso
n1 n2 n3 n4
n11 n12 n13 n21goal
n22 n31 n32 n33 n41 n42
n0
2323
ESEMPIO: BREADTHESEMPIO: BREADTH--FIRSTFIRST
BreadthBreadth--first:first: figli espansi aggiunti in coda a L.figli espansi aggiunti in coda a L.–– n0n0–– n1,n2,n3,n4n1,n2,n3,n4–– n2,n3,n4,n11,n12,n13n2,n3,n4,n11,n12,n13–– n3,n4,n11,n12,n13,n21,n22n3,n4,n11,n12,n13,n21,n22–– n4,n11,n12,n13,n21,n22,n31,n32,n33n4,n11,n12,n13,n21,n22,n31,n32,n33–– n11,n12,n13,n21,n22,n31,n32,n33,n41,n42n11,n12,n13,n21,n22,n31,n32,n33,n41,n42–– n12,n13,n21,n22,n31,n32,n33,n41,n42n12,n13,n21,n22,n31,n32,n33,n41,n42–– n13,n21,n22,n31,n32,n33,n41,n42n13,n21,n22,n31,n32,n33,n41,n42–– n21n21,n22,n31,n32,n33,n41,n42 Successo,n22,n31,n32,n33,n41,n42 Successo
n1 n2 n3 n4
n11 n12 n13 n21goal
n22 n31 n32 n33 n41 n42
n0
2424
RICERCA A PROFONDITÀ LIMITATARICERCA A PROFONDITÀ LIMITATA
•• Si prevede una PROFONDITÀ MASSIMA di ricerca. Si prevede una PROFONDITÀ MASSIMA di ricerca.
•• Quando si raggiunge il MASSIMO di profondità o un FALLIMENTO Quando si raggiunge il MASSIMO di profondità o un FALLIMENTO si considerano STRADE ALTERNATIVE della stessa profondità (se si considerano STRADE ALTERNATIVE della stessa profondità (se esistono), poi minori di una unità e così via (BACKTRACKING).esistono), poi minori di una unità e così via (BACKTRACKING).
•• Si possono stabilire limiti massimi di profondità (non Si possono stabilire limiti massimi di profondità (non necessariamente risolvono il problema della completezza).necessariamente risolvono il problema della completezza).
RICERCA AD APPROFONDIMENTO RICERCA AD APPROFONDIMENTO ITERATIVOITERATIVO•• La ricerca ad approfondimento iterativo evita il problema di sceLa ricerca ad approfondimento iterativo evita il problema di scegliere il gliere il
limite di profondità massimo provando tutti i possibili limiti dlimite di profondità massimo provando tutti i possibili limiti di i profondità.profondità.–– Prima 0, poi 1, poi 2 Prima 0, poi 1, poi 2 ecc…ecc…
•• Combina i vantaggi delle due strategie. È completa e sviluppa unCombina i vantaggi delle due strategie. È completa e sviluppa un solo solo ramo alla volta.ramo alla volta.
•• In realtà tanti stati vengono espansi più volte, ma questo non pIn realtà tanti stati vengono espansi più volte, ma questo non peggiora eggiora sensibilmente i tempi di esecuzione.sensibilmente i tempi di esecuzione.
•• In particolare, il numero totale di espansioni è: In particolare, il numero totale di espansioni è: (d+1)1 + ((d+1)1 + (d)bd)b + (d+ (d--1)b1)b22
+…+ 3b+…+ 3bdd--2 2 + 2b+ 2bdd--1 1 +b+bdd..
•• In generale è il preferito quando lo spazio di ricerca è molto aIn generale è il preferito quando lo spazio di ricerca è molto ampio.mpio.
2626
RicercaRicerca ad ad approfondimentoapprofondimento iterativoiterativo ––Iterative deepening search (IDS)Iterative deepening search (IDS)
•• PuoPuo’ ’ emulareemulare la breadth first la breadth first mediantemediante ripetuteripetute applicazioniapplicazioni delladelladepth first con depth first con unauna profonditaprofondita` ` limitelimite crescentecrescente..
1.1. C=1C=1
2.2. ApplicaApplica depth first con depth first con limitelimite C, se C, se trovitrovi unauna soluzionesoluzione terminatermina
3.3. AltrimentiAltrimenti incrementaincrementa C e C e vaivai al al passopasso 22
2727
Ricerca con approfondimento iterativo
2828
Ricerca con approfondimento iterativo
2929
b - massimo fattore di diramazione dell’albero di ricerca
d - profondità della soluzione a costo minimo
m - massima profondità dello spazio degli stati (puòessere infinita)
3030
Ricerca bidirezionale
3131
Confronto fra le strategie di ricerca
b = fattore di ramificazione; d = profondià della soluzione; m=profonditàmassima dell’albero di ricerca; l=limite di profondità.
3232
STRATEGIE INFORMATESTRATEGIE INFORMATE
•• L'intelligenza di un sistema non è misurabile in termini di capaL'intelligenza di un sistema non è misurabile in termini di capacità di cità di ricerca, ma nella capacità di utilizzare conoscenza sul problemaricerca, ma nella capacità di utilizzare conoscenza sul problema per per eliminare il pericolo dell'esplosione combinatoria. eliminare il pericolo dell'esplosione combinatoria.
•• Se il sistema avesse un qualche controllo sull'ordine nel quale Se il sistema avesse un qualche controllo sull'ordine nel quale vengono generate le possibili soluzioni, sarebbe allora utile divengono generate le possibili soluzioni, sarebbe allora utile disporre sporre questo ordine in modo che le soluzioni vere e proprie abbiano unquesto ordine in modo che le soluzioni vere e proprie abbiano un'alta 'alta possibilità di comparire prima. possibilità di comparire prima.
•• L'intelligenza, per un sistema con capacità di elaborazione limiL'intelligenza, per un sistema con capacità di elaborazione limitata tata consiste nella saggia scelta di cosa fare dopo.....".consiste nella saggia scelta di cosa fare dopo.....".
3333
STRATEGIE INFORMATESTRATEGIE INFORMATE
•• NewellNewell--SimonSimon::–– I metodi di ricerca precedenti in uno spazio di profondità d e I metodi di ricerca precedenti in uno spazio di profondità d e
fattore di ramificazione b risultano di complessità proporzionalfattore di ramificazione b risultano di complessità proporzionale a e a bbdd per trovare un goal in una delle foglie.per trovare un goal in una delle foglie.
–– Questo è inaccettabile per problemi di una certa complessità. Questo è inaccettabile per problemi di una certa complessità. Invece di espandere i nodi in modoInvece di espandere i nodi in modo qualunque utilizziamo qualunque utilizziamo conoscenza euristica sul dominio (funzioni di valutazione) per conoscenza euristica sul dominio (funzioni di valutazione) per decidere quale nodo espandere per primo.decidere quale nodo espandere per primo.
3434
STRATEGIE INFORMATESTRATEGIE INFORMATE•• Le funzioni di valutazione Le funzioni di valutazione danno una stima computazionale dello danno una stima computazionale dello
sforzo sforzo per raggiungere lo stato finale.per raggiungere lo stato finale.•• In particolare: In particolare:
–– Il tempo speso per valutare mediante una funzione euristica il nIl tempo speso per valutare mediante una funzione euristica il nodo da odo da espandere deve corrispondere a una riduzione nella dimensione deespandere deve corrispondere a una riduzione nella dimensione dello llo spazio esplorato.spazio esplorato.
–– TradeTrade--offoff fra tempo necessario nel risolvere il problema (livello base) efra tempo necessario nel risolvere il problema (livello base) etempo speso nel decidere come risolvere il problema (metatempo speso nel decidere come risolvere il problema (meta--livello).livello).
–– Le ricerche non informate non hanno attività di metaLe ricerche non informate non hanno attività di meta--livello.livello.
•• PROBLEMI:PROBLEMI:–– Come trovare le funzioni di valutazione corrette, cioè come si Come trovare le funzioni di valutazione corrette, cioè come si fa a fa a
valutare bene quale è il nodo più "promettente"?valutare bene quale è il nodo più "promettente"?–– È difficile caratterizzare numericamente la conoscenza empirica È difficile caratterizzare numericamente la conoscenza empirica sul sul
problema.problema.–– Non sempre la scelta più ovvia è la migliore.Non sempre la scelta più ovvia è la migliore.
3535
ESEMPIOESEMPIO
•• Scelta euristica: muoversi sempre per ridurre la distanza dall'uScelta euristica: muoversi sempre per ridurre la distanza dall'uscita.scita.
•• Nel caso di questo labirinto sceglieremmo la strada più lunga.Nel caso di questo labirinto sceglieremmo la strada più lunga.
3636
ESEMPIO: GIOCO DEL FILETTOESEMPIO: GIOCO DEL FILETTO•• La distanza dal goal è stimata in base al numero di caselle fuorLa distanza dal goal è stimata in base al numero di caselle fuori i
•• Non è detto che la distanza stimi esattamente il numero di mosseNon è detto che la distanza stimi esattamente il numero di mossenecessarienecessarie
1 2 37 8 46 5
1 2 38 47 6 5
stato goal
1 2 37 46 8 5
Distanza=3 ma in realtà sono necessarie 4 mosse per arrivare alla soluzione.
3737
Ricerca Best First
Usa una funzione di valutazione che calcola un numero che rappresenta la desiderabilità relativaall’espansione di nodo.
Best-first significa scegliere come nodo da espanderequello che sembra più desiderabile.
QueuingFn = inserisce I successori in ordinedecrescente di desiderabilità.
Casi particolari:
•ricerca greedy (golosa)
•ricerca A*
3838
STRATEGIE INFORMATESTRATEGIE INFORMATE
•• BESTBEST--FIRST: Cerca di muoversi verso il massimo (minimo) di una FIRST: Cerca di muoversi verso il massimo (minimo) di una funzione che “stima” il costo per raggiungere il goal.funzione che “stima” il costo per raggiungere il goal.
•• GreedyGreedy::–– Sia L una lista dei nodi iniziali del problema, ordinati secondSia L una lista dei nodi iniziali del problema, ordinati secondo la loro o la loro
distanza dal goal (nodi più vicini al goal precedono quelli più distanza dal goal (nodi più vicini al goal precedono quelli più lontani);lontani);
–– Sia n il primo nodo di L. Se L è vuota fallisci;Sia n il primo nodo di L. Se L è vuota fallisci;
–– Se n è il goal fermati e ritorna esso più la strada percorsa perSe n è il goal fermati e ritorna esso più la strada percorsa per raggiugerloraggiugerlo
–– Altrimenti rimuovi n da L e aggiungi a L tutti i nodi figli di nAltrimenti rimuovi n da L e aggiungi a L tutti i nodi figli di n con con labellabel la la strada percorsa partendo dal nodo iniziale. Poi ordina tutta la strada percorsa partendo dal nodo iniziale. Poi ordina tutta la lista L in lista L in base alla stima della distanza relativa dal goal. Ritorna al pasbase alla stima della distanza relativa dal goal. Ritorna al passo 2so 2
3939
Una realizzazione della ricerca best-first
usa l’algoritmo di ricerca generale e la funzione di valutazione EvalFn
4040
RICERCA LUNGO IL CAMMINO MIGLIORERICERCA LUNGO IL CAMMINO MIGLIORE
•• La ricerca in salita non è detto che trovi la soluzione miglioreLa ricerca in salita non è detto che trovi la soluzione migliore, ovvero , ovvero il il cammino migliorecammino migliore per arrivare alla soluzione (si pensi all'esempio del per arrivare alla soluzione (si pensi all'esempio del labirinto).labirinto).
•• Questo perché la tecnica Questo perché la tecnica bestbest--firstfirst cerca di trovare il più presto cerca di trovare il più presto possibile un nodo con distanza 0 dal goal senza curarsi di trovapossibile un nodo con distanza 0 dal goal senza curarsi di trovare quel re quel nodo che ha profondità più bassa.nodo che ha profondità più bassa.
3 (1)
4
1
goal
(2) 2
(3) 1
(4) 1
(5) 1
(6) 1
(7) goal
4141
STRATEGIE INFORMATE: problemi di STRATEGIE INFORMATE: problemi di questo approccioquesto approccio
–– La ricerca di questo tipo non è ottimale e può essere La ricerca di questo tipo non è ottimale e può essere incompleta (presenta gli stessi difetti della ricerca in incompleta (presenta gli stessi difetti della ricerca in profondità).profondità).
–– Nel caso peggiore, se abbiamo profondità d e fattore di Nel caso peggiore, se abbiamo profondità d e fattore di ramificazione b il numero massimo di nodi espansi sarà ramificazione b il numero massimo di nodi espansi sarà bbdd. (complessità temporale).. (complessità temporale).
–– Poiché, inoltre, tiene in memoria tutti i nodi la Poiché, inoltre, tiene in memoria tutti i nodi la complessità spaziale coincide con quella temporale.complessità spaziale coincide con quella temporale.
–– Con una buona funzione euristica, la complessità Con una buona funzione euristica, la complessità spaziale e temporale possono essere ridotte spaziale e temporale possono essere ridotte sostanzialmente.sostanzialmente.
4242
•• Invece di considerare solo la distanza dal goal, considera Invece di considerare solo la distanza dal goal, considera anche il "costo" nel raggiungere il nodo N dalla radice.anche il "costo" nel raggiungere il nodo N dalla radice.
•• Espandiamo quindi i nodi in ordine crescente di Espandiamo quindi i nodi in ordine crescente di f(n) = g(n) + h'(n)f(n) = g(n) + h'(n)
•• Dove g(n) è la profondità del nodo e h'(n) la distanza dal Dove g(n) è la profondità del nodo e h'(n) la distanza dal goal.goal.
•• Scegliamo come nodo da espandere quello per cui Scegliamo come nodo da espandere quello per cui questa somma è più piccola.questa somma è più piccola.
Algoritmo Algoritmo A*A*
4343
•• In pratica cerchiamo di combinare i vantaggi della ricerca in saIn pratica cerchiamo di combinare i vantaggi della ricerca in salita lita (efficienza) e della ricerca a costo uniforme ((efficienza) e della ricerca a costo uniforme (ottimalitàottimalità e completezza). e completezza).
0 + 3 (1)
1+4 (6)
2+1 (7)
3+0 goal
(2) 1+ 2
(3) 2+1
(4) 3+1
(5) 4+1
5+1
(7) goal
Algoritmo Algoritmo A*A*
4444
Algoritmo A*Algoritmo A*
•• Sia L una lista dei nodi iniziali del problema.Sia L una lista dei nodi iniziali del problema.
•• Sia n il nodo di L per cui g(n) + h'(n) è minima. Se L è vuota Sia n il nodo di L per cui g(n) + h'(n) è minima. Se L è vuota fallisci;fallisci;
•• Se n è il goal fermati e ritorna esso più la strada percorsa perSe n è il goal fermati e ritorna esso più la strada percorsa perraggiungerloraggiungerlo
•• Altrimenti rimuovi n da L e aggiungi a L tutti i nodi figli di nAltrimenti rimuovi n da L e aggiungi a L tutti i nodi figli di n con con labellabel la la strada percorsa partendo dal nodo iniziale. Ritorna al passo 2strada percorsa partendo dal nodo iniziale. Ritorna al passo 2
•• Nota:Nota:–– ancora una volta l'algoritmo non garantisce di trovare la stradancora una volta l'algoritmo non garantisce di trovare la strada ottima. a ottima.
Nell'esempio, se il nodo con Nell'esempio, se il nodo con labellabel 5 fosse stato il goal sarebbe stato 5 fosse stato il goal sarebbe stato trovato prima di quello sulla strada destra (ottimale).trovato prima di quello sulla strada destra (ottimale).
4545
ESEMPIOESEMPIO
Il gioco del filetto Il gioco del filetto f(n)=g(n)+h'(n) dove:f(n)=g(n)+h'(n) dove:
–– g(n) = profondità del g(n) = profondità del nodo n;nodo n;
–– h'(n) = numero di h'(n) = numero di numeri nel posto numeri nel posto scorrettoscorretto
2 8 31 6 47 5
2 8 31 6 47 5
2 8 31 47 6 5
2 8 31 6 4
7 5
(1) f=0+4
f=6 f=6f=4(2)
2 8 31 4
7 6 5
2 31 8 47 6 5
2 8 31 47 6 5
f=5(3) f=5(4)
8 32 1 47 6 5
f=7
2 8 37 1 4
6 5
f=6
2 31 8 47 6 5
2 31 8 47 6 5
f=5(5)f=7
1 2 38 4
7 6 51 2 38 47 6 5
f=5(6)
f=5+0
4646
ALGORITMO A*ALGORITMO A*•• A* non garantisce di trovare la soluzione ottima (dipende dallaA* non garantisce di trovare la soluzione ottima (dipende dalla
funzione euristica).funzione euristica).•• Si supponga di indicare con h(n) la vera distanza fra il nodo coSi supponga di indicare con h(n) la vera distanza fra il nodo corrente e rrente e
il goal.il goal.•• La funzione euristica h'(n) è ottimistica se abbiamo sempre che La funzione euristica h'(n) è ottimistica se abbiamo sempre che
h'(n) <= h(n).h'(n) <= h(n).•• Tale funzione euristica è chiamata ammissibile.Tale funzione euristica è chiamata ammissibile.
•• Teorema:Teorema:–– Se h'(n) <= h(n) per ogni nodo, allora l'algoritmo A* troverà seSe h'(n) <= h(n) per ogni nodo, allora l'algoritmo A* troverà sempre il nodo mpre il nodo
goal ottimale.goal ottimale.
–– Ovviamente l'euristica perfetta h' = h è sempre ammissibile.Ovviamente l'euristica perfetta h' = h è sempre ammissibile.
–– Se h' = 0 otteniamo sempre una funzione euristica ammissibile Se h' = 0 otteniamo sempre una funzione euristica ammissibile ⇒⇒ ricerca ricerca breadthbreadth--firstfirst (ovviamente la (ovviamente la depthdepth--firstfirst non lo sarà mai).non lo sarà mai).
4747
ESEMPIO: RICERCA CON FUNZIONE ESEMPIO: RICERCA CON FUNZIONE EURISTICA AMMISSIBILEEURISTICA AMMISSIBILE
•• La scelta precedente per il gioco del filetto (contare le tesserLa scelta precedente per il gioco del filetto (contare le tessere fuori e fuori posto h') è sempre ammissibile perché ogni mossa può ridurlo al posto h') è sempre ammissibile perché ogni mossa può ridurlo al più di più di 1.1.
0 + 3 (1)
1+4 (6)
2+1 (7)
3+0 goal
(2) 1+ 2
(3) 2+1
(4) 3+1
(5) 4+1
5+1
(7) goal
4848
FUNZIONI EURISTICHE AMMISSIBILI
E’possibile definire differenti funzioni euristiche. Ad esempio:
h1= numero di tessere che sono fuori posto (h1= 7)
h2= la somma delle distanze dalle posizioni che le tessere devonoassumere nella configurazione obiettivo. La distanza è una sommadelle distanze orizzontali e verticali (distanza di Manhattan). Le tessere da 1 a 8 nello stato iniziale danno una distanza h2= 2+3+3+2+4+2+0+2 = 18
Sono entrambe ammissibili
4949
FUNZIONI EURISTICHE AMMISSIBILIFUNZIONI EURISTICHE AMMISSIBILI•• Poiché h'<=h'*<=h la migliore è h'*.Poiché h'<=h'*<=h la migliore è h'*.
•• È meglio usare una funzione euristica con valori più alti, a patÈ meglio usare una funzione euristica con valori più alti, a patto che to che sia ottimista.sia ottimista.
•• Come inventare funzioni euristiche?Come inventare funzioni euristiche?
•• Spesso il costo di una soluzione esatta per un problema rilassatSpesso il costo di una soluzione esatta per un problema rilassato è o è una buona euristica per il problema originale.una buona euristica per il problema originale.
•• Se la definizione del problema è descritta in un linguaggio formSe la definizione del problema è descritta in un linguaggio formale è ale è possibile costruire problemi rilassati automaticamente.possibile costruire problemi rilassati automaticamente.
5050
ESEMPIO: GIOCO DEL FILETTOESEMPIO: GIOCO DEL FILETTO
•• Descrizione: una tessera può muoversi dal quadrato A al quadratoDescrizione: una tessera può muoversi dal quadrato A al quadrato B B se A è adiacente a B e B è vuoto.se A è adiacente a B e B è vuoto.
•• Problemi rilassati che rimuovono alcune condizioni:Problemi rilassati che rimuovono alcune condizioni:
•• Una tessera può muoversi dal quadrato A al quadrato B se A è Una tessera può muoversi dal quadrato A al quadrato B se A è adiacente a B.adiacente a B.
•• Una tessera può muoversi dal quadrato A al quadrato B se B è vuoUna tessera può muoversi dal quadrato A al quadrato B se B è vuoto.to.
5151
•• Da alberi a grafi:Da alberi a grafi:
–– Abbiamo assunto fin qui che lo spazio di ricerca sia un albero eAbbiamo assunto fin qui che lo spazio di ricerca sia un albero e non un non un grafo. Non è quindi possibile raggiungere lo stesso nodo da stragrafo. Non è quindi possibile raggiungere lo stesso nodo da strade de diverse.diverse.
–– L'assunzione è ovviamente semplicistica: si pensi al gioco del fL'assunzione è ovviamente semplicistica: si pensi al gioco del filetto, ai iletto, ai missionari e cannibali ecc.missionari e cannibali ecc.
–– Come si estendono gli algoritmi precedenti per trattare con i grCome si estendono gli algoritmi precedenti per trattare con i grafi?afi?
DA ALBERI A GRAFIDA ALBERI A GRAFI
5252
•• Due liste:Due liste:–– Nodi espansi e rimossi dalla lista per evitare di esaminarli nuoNodi espansi e rimossi dalla lista per evitare di esaminarli nuovamente vamente
(nodi chiusi);(nodi chiusi);
–– Nodi ancora da esaminare (nodi aperti).Nodi ancora da esaminare (nodi aperti).
•• A* che cerca in un grafo invece che in un albero.A* che cerca in un grafo invece che in un albero.
•• Modifiche:Modifiche:–– Il Il grafografo puopuo’ ’ diventarediventare un un alberoalbero con con statistati ripetutiripetuti..
–– Aggiunta della lista dei nodi chiusi e assunzione che g(n) valutAggiunta della lista dei nodi chiusi e assunzione che g(n) valuta la a la distanza minima del nodo n dal nodo di partenza.distanza minima del nodo n dal nodo di partenza.
ESEMPIO: GIOCO DEL FILETTOESEMPIO: GIOCO DEL FILETTO
5353
ALGORITMO A* PER GRAFIALGORITMO A* PER GRAFI
•• Sia La una lista aperta dei nodi iniziali del problema.Sia La una lista aperta dei nodi iniziali del problema.
•• Sia n il nodo di La per cui g(n) + h'(n) è minima. Se La è vuotSia n il nodo di La per cui g(n) + h'(n) è minima. Se La è vuota fallisci;a fallisci;
•• Se n è il goal fermati e ritorna esso più la strada percorsa perSe n è il goal fermati e ritorna esso più la strada percorsa per raggiungerloraggiungerlo
•• Altrimenti rimuovi n da La, inseriscilo nella lista dei nodi chiAltrimenti rimuovi n da La, inseriscilo nella lista dei nodi chiusi usi LcLc e aggiungi a e aggiungi a La tutti i nodi figli di n con La tutti i nodi figli di n con labellabel la strada percorsa partendo dal nodo iniziale. la strada percorsa partendo dal nodo iniziale. Se un nodo figlio è già in La, non Se un nodo figlio è già in La, non riaggiungerloriaggiungerlo, ma aggiornalo con la strada , ma aggiornalo con la strada migliore che lo connette al nodo iniziale. Se un nodo figlio è gmigliore che lo connette al nodo iniziale. Se un nodo figlio è già in ià in LcLc, non , non aggiungerlo a La, ma, se il suo costo è migliore, aggiorna il suaggiungerlo a La, ma, se il suo costo è migliore, aggiorna il suo costo e i costi o costo e i costi dei nodi già espansi che da lui dipendevano.dei nodi già espansi che da lui dipendevano.
•• E se non E se non controllassimocontrollassimo la la listalista deidei nodinodi chiusichiusi? Se in ? Se in essaessaconservassimoconservassimo solo solo gligli statistati e la e la utilizzassimoutilizzassimo solo per solo per evitareevitarel’espansionel’espansione deidei nodinodi in in essaessa conteuticonteuti??
•• In In questoquesto casocaso troveremmotroveremmo la la stradastrada cheche passapassa per B (non e’ per B (non e’ quellaquellaottimaottima))
•• Il Il motivomotivo e’ e’ cheche a a causacausa delladella stimastima troppotroppo ottimistaottimista didi B, C e’ B, C e’ espansoespansoprima prima didi trovaretrovare la la stradastrada alternativaalternativa cheche passapassa per A.per A.
•• UlterioreUlteriore condizionecondizione susu h: h: consistenzaconsistenza (o (o monotonicitamonotonicita`)`)
•• DefinizioneDefinizione::
•• h(nh(n) = 0 se lo ) = 0 se lo statostato corrispondentecorrispondente coincide con coincide con ilil goalgoal
•• h(ni)h(ni)--h(njh(nj)<=)<=c(ni,njc(ni,nj) per ) per ogniogni njnj figliofiglio didi nini
5757
ALGORITMI COSTRUTTIVI e ALGORITMI ALGORITMI COSTRUTTIVI e ALGORITMI DI RICERCA LOCALEDI RICERCA LOCALE•• Gli algoritmi costruttiviGli algoritmi costruttivi (visti fino ad ora) (visti fino ad ora) generanogenerano una soluzione una soluzione
exex--novo aggiungendo ad una situazione di partenza (vuota o inizialenovo aggiungendo ad una situazione di partenza (vuota o iniziale) ) delle componenti in un particolare ordine fino a “costruire” la delle componenti in un particolare ordine fino a “costruire” la soluzione completa.soluzione completa.
•• Gli algoritmi di ricerca localeGli algoritmi di ricerca locale partono da una soluzione iniziale e partono da una soluzione iniziale e iterativamente cercano di rimpiazzare la soluzione corrente con iterativamente cercano di rimpiazzare la soluzione corrente con una una “migliore” in un intorno della soluzione corrente. In questi cas“migliore” in un intorno della soluzione corrente. In questi casi non i non interessa la “strada” per raggiungere l’obiettivo.interessa la “strada” per raggiungere l’obiettivo.
•• Diversi problemi (ad esempio, il problema delle 8 regine) hanno Diversi problemi (ad esempio, il problema delle 8 regine) hanno la la proprietà che la descrizione stessa dello stato contiene tutte lproprietà che la descrizione stessa dello stato contiene tutte le e informazioni necessarie per la soluzione (il cammino è irrilevaninformazioni necessarie per la soluzione (il cammino è irrilevante).te).
•• In questo caso gli algoritmi con miglioramenti iterativi spesso In questo caso gli algoritmi con miglioramenti iterativi spesso forniscono l’approccio più pratico.forniscono l’approccio più pratico.
•• Ad esempio, possiamo cominciare con tutte le regine sulla scacchAd esempio, possiamo cominciare con tutte le regine sulla scacchiera iera e poi spostarle per ridurre il numero di attacchi.e poi spostarle per ridurre il numero di attacchi.
5858
RICERCA LOCALERICERCA LOCALE•• La ricerca locale è basata sull’esplorazione iterativa di “soluzLa ricerca locale è basata sull’esplorazione iterativa di “soluzioni ioni
vicine”, che possono migliorare la soluzione corrente mediante vicine”, che possono migliorare la soluzione corrente mediante modifiche locali.modifiche locali.
•• Struttura dei “vicini” (Struttura dei “vicini” (neighborhoodneighborhood).). Una struttura dei “vicini” è una Una struttura dei “vicini” è una funzione funzione FF che assegna a ogni soluzione che assegna a ogni soluzione ss dell’insieme di soluzioni dell’insieme di soluzioni SS un insieme di soluzioni un insieme di soluzioni N(s)N(s) sottoinsieme di S.sottoinsieme di S.
•• La scelta della funzione La scelta della funzione FF è fondamentale per l’efficienza del sistema è fondamentale per l’efficienza del sistema e definisce l’insieme delle soluzioni che possono essere raggiune definisce l’insieme delle soluzioni che possono essere raggiunte te da s in un singolo passo di ricerca dell’algoritmo.da s in un singolo passo di ricerca dell’algoritmo.
•• Tipicamente è definita implicitamente attraverso le possibili moTipicamente è definita implicitamente attraverso le possibili mosse.sse.
•• La soluzione trovata da un algoritmo di ricerca locale non è detLa soluzione trovata da un algoritmo di ricerca locale non è detto sia to sia ottima globalmente, ma può essere ottima rispetto ai cambiamentiottima globalmente, ma può essere ottima rispetto ai cambiamentilocali.locali.
5959
RICERCA LOCALE (continua)RICERCA LOCALE (continua)•• Massimo (minimo) localeMassimo (minimo) locale
–– Un massimo locale è una soluzione s tale che per qualunque s’ Un massimo locale è una soluzione s tale che per qualunque s’ appartenente a N(s), data una funzione di valutazione f, f(s) appartenente a N(s), data una funzione di valutazione f, f(s) ≥≥ f(s’).f(s’).
–– Quando risolviamo un problema di massimizzazione (minimizzazioneQuando risolviamo un problema di massimizzazione (minimizzazione) ) cerchiamo un massimo (minimo) globale cerchiamo un massimo (minimo) globale ssoptopt cioè tale che per qualunque cioè tale che per qualunque s, f(s, f(ssoptopt) > f(s).) > f(s).
–– Più è largo il Più è largo il neighborhoodneighborhood più è probabile che un massimo locale sia più è probabile che un massimo locale sia anche un massimo globale (ma ovviamente esiste un problema di anche un massimo globale (ma ovviamente esiste un problema di complessità computazionale). Quindi, più è largo un complessità computazionale). Quindi, più è largo un neighborhoodneighborhood più più aumenta la qualità della soluzioneaumenta la qualità della soluzione
•• L’algoritmo base a cui ci si riferisce è detto “iterative L’algoritmo base a cui ci si riferisce è detto “iterative improvementimprovement” ” ((miglioramentiomiglioramentio iterativo):iterativo):–– Tipicamente, tale algoritmo parte con una soluzione di tentativoTipicamente, tale algoritmo parte con una soluzione di tentativo generata generata
in modo casuale o mediante un procedimento costruttivo e cerca din modo casuale o mediante un procedimento costruttivo e cerca di i migliorare la soluzione corrente muovendosi verso i vicini. Se fmigliorare la soluzione corrente muovendosi verso i vicini. Se fra i vicini ra i vicini c’è una soluzione migliore, tale soluzione va a rimpiazzare la cc’è una soluzione migliore, tale soluzione va a rimpiazzare la corrente. orrente. Altrimenti termina in un massimo (minimo) locale. Altrimenti termina in un massimo (minimo) locale.
6060
Algoritmo più noto (Algoritmo più noto (HillHill--climbingclimbing):):functionfunction HILLHILL--CLIMBING CLIMBING (problem)(problem)
returnsreturns a solution statea solution state
inputs:inputs: problemproblem
local variableslocal variables: : currentcurrent--node, nextnode, next--nodenode
Si noti che l’algoritmo Si noti che l’algoritmo non tiene traccianon tiene traccia dell’albero di ricerca.dell’albero di ricerca.
6161
ALGORITMO PIU’ NOTO: HILL CLIMBINGALGORITMO PIU’ NOTO: HILL CLIMBING•• Un modo semplice per capire questo algoritmo è di immaginare cheUn modo semplice per capire questo algoritmo è di immaginare che
tutti gli stati facciano parte di una superficie di un territoritutti gli stati facciano parte di una superficie di un territorio. L’altezza o. L’altezza dei punti corrisponde alla loro funzione di valutazione. dei punti corrisponde alla loro funzione di valutazione.
•• Dobbiamo muoverci cercando le sommità più alte tenendo conto solDobbiamo muoverci cercando le sommità più alte tenendo conto solo o dello stato corrente e dei vicini immediati.dello stato corrente e dei vicini immediati.
•• HillHill climbing si muove verso i valori più alti (o bassi) che climbing si muove verso i valori più alti (o bassi) che corrispondono a massimi (o minimi) localicorrispondono a massimi (o minimi) locali
•• Problema: l’algoritmo può incappare in un minimo (massimo) localProblema: l’algoritmo può incappare in un minimo (massimo) locale di e di scarsa qualità:scarsa qualità:–– Ha il limite di essere un metodo locale che non valuta tutta la Ha il limite di essere un metodo locale che non valuta tutta la situazione, situazione,
ma solo gli stati abbastanza vicini a quello corrente.ma solo gli stati abbastanza vicini a quello corrente.
•• L’algoritmo non gestisce un albero di ricerca, ma solo lo stato L’algoritmo non gestisce un albero di ricerca, ma solo lo stato e la sua e la sua valutazione.valutazione.
6262
PROBLEMIPROBLEMI•• Massimi locali:Massimi locali:
–– Stati migliori di tutti i vicini, ma peggiori di altri stati cheStati migliori di tutti i vicini, ma peggiori di altri stati che non sono nelle non sono nelle vicinanze. Il metodo ci spinge verso il massimo locale, peggioravicinanze. Il metodo ci spinge verso il massimo locale, peggiorando la ndo la situazione.situazione.
•• Pianori o Altopiani:Pianori o Altopiani:–– Zone piatte dello stato di ricerca in cui gli stati vicini hannoZone piatte dello stato di ricerca in cui gli stati vicini hanno tutti lo stesso tutti lo stesso
valore. In quale direzione muoversi (scelta casuale)?valore. In quale direzione muoversi (scelta casuale)?
•• Crinali:Crinali:–– È una zona più alta di quelle adiacenti verso cui dovremmo andarÈ una zona più alta di quelle adiacenti verso cui dovremmo andare, ma e, ma
non possiamo andarci in modo diretto. Dobbiamo quindi muoverci inon possiamo andarci in modo diretto. Dobbiamo quindi muoverci in n un'altra direzione per raggiungerlo.un'altra direzione per raggiungerlo.
•• Una possibile (semplice) soluzione: ripartire con una nuova riceUna possibile (semplice) soluzione: ripartire con una nuova ricerca da rca da una soluzione di partenza una soluzione di partenza randomrandom o generata in modo costruttivo. Si o generata in modo costruttivo. Si salva poi la soluzione migliore dopo una serie di tentativi (salva poi la soluzione migliore dopo una serie di tentativi (boundbounddovuto al tempo di CPU o numero di iterazioni).dovuto al tempo di CPU o numero di iterazioni).
6363
META EURISTICHEMETA EURISTICHE
•• Si definiscono metaSi definiscono meta--euristiche l’insieme di algoritmi, tecniche e studi euristiche l’insieme di algoritmi, tecniche e studi relativi all’applicazione di criteri euristici per risolvere prorelativi all’applicazione di criteri euristici per risolvere problemi di blemi di ottimizzazione (e quindi di migliorare la ricerca locale con criottimizzazione (e quindi di migliorare la ricerca locale con criteri teri abbastanza generali).abbastanza generali).
•• Ne citiamo alcuni:Ne citiamo alcuni:•• ANT ANT colonycolony optimizationoptimization
–– ispirata al comportamento di colonie di insetti.ispirata al comportamento di colonie di insetti.–– Tali insetti mostrano capacità globali nel trovare, ad esempio, Tali insetti mostrano capacità globali nel trovare, ad esempio, il il
cammino migliore per arrivare al cibo dal formicaio (algoritmi dcammino migliore per arrivare al cibo dal formicaio (algoritmi di i ricerca cooperativi)ricerca cooperativi)
•• TabuTabu searchsearch–– La sua caratteristica principale è l’utilizzo di una memoria perLa sua caratteristica principale è l’utilizzo di una memoria per
guidare il processo di ricerca in modo da evitare la ripetizioneguidare il processo di ricerca in modo da evitare la ripetizione di di stati già esplorati. stati già esplorati.
6464
META EURISTICHE (continua)META EURISTICHE (continua)
•• Algoritmi geneticiAlgoritmi genetici
–– Sono algoritmi evolutivi ispirati ai modelli dell’evoluzione delSono algoritmi evolutivi ispirati ai modelli dell’evoluzione delle le specie in natura. Utilizzano il principio della selezione naturaspecie in natura. Utilizzano il principio della selezione naturale che le che favorisce gli individui di una popolazione che sono più adatti afavorisce gli individui di una popolazione che sono più adatti ad d uno specifico ambiente per sopravvivere e riprodursi.uno specifico ambiente per sopravvivere e riprodursi.
–– Ogni individuo rappresenta una soluzione con il corrispondente Ogni individuo rappresenta una soluzione con il corrispondente valore della funzione di valutazione (valore della funzione di valutazione (fitnessfitness). I tre principali ). I tre principali operatori sono: operatori sono: selezioneselezione, , mutazionemutazione e e ricombinazionericombinazione..
6565
META EURISTICHE (Continua)META EURISTICHE (Continua)
•• SimulatedSimulated AnnealingAnnealing
–– Cerca di evitare il problema dei massimi locali, seguendo in Cerca di evitare il problema dei massimi locali, seguendo in pratica la strategia in salita, ma ogni tanto fa un passo che nopratica la strategia in salita, ma ogni tanto fa un passo che non n porta a un incremento in salita.porta a un incremento in salita.
–– Quando rimaniamo bloccati in un massimo locale, invece di Quando rimaniamo bloccati in un massimo locale, invece di cominciare di nuovo casualmente potremmo permettere alla cominciare di nuovo casualmente potremmo permettere alla ricerca di fare alcuni passi in discesa per evitare un massimo ricerca di fare alcuni passi in discesa per evitare un massimo locale.locale.
–– Ispirato al processo di raffreddamento dei metalli.Ispirato al processo di raffreddamento dei metalli.
–– In pratica, ci suggerisce di esaminare, ogni tanto, nella ricerIn pratica, ci suggerisce di esaminare, ogni tanto, nella ricerca un ca un nodo anche se sembra lontano dalla soluzione.nodo anche se sembra lontano dalla soluzione.
6666
Ricerca in grafi AND/ORRicerca in grafi AND/OR
•• Fino a questo momento abbiamo discusso strategie di ricerca per Fino a questo momento abbiamo discusso strategie di ricerca per grafi OR nei quali vogliamo trovare un singolo cammino verso la grafi OR nei quali vogliamo trovare un singolo cammino verso la soluzione.soluzione.
•• Il grafo (o albero) AND/OR risulta appropriato quando si voglionIl grafo (o albero) AND/OR risulta appropriato quando si vogliono o rappresentare problemi che si possono risolvere scomponendoli inrappresentare problemi che si possono risolvere scomponendoli in un un insieme di problemi più piccoli che andranno poi tutti risolti.insieme di problemi più piccoli che andranno poi tutti risolti.
•• ⇒⇒ arco AND che deve puntare a un qualunque numero di nodi arco AND che deve puntare a un qualunque numero di nodi successori che si devono tutti risolvere per risolvere il nodo Asuccessori che si devono tutti risolvere per risolvere il nodo AND ND stesso.stesso.
•• Dal nodo AND possono anche partire rami OR che indicano soluzionDal nodo AND possono anche partire rami OR che indicano soluzioni i alternative.alternative.
6767
ESEMPIOESEMPIO
•• L'algoritmo di ricerca va opportunamente modificato per essere iL'algoritmo di ricerca va opportunamente modificato per essere in n grado di trattare gli archi AND.grado di trattare gli archi AND.
•• In particolare, va opportunamente trattato il cammino migliore.In particolare, va opportunamente trattato il cammino migliore.
Obiettivo: munirsi di TV
Rubare TV Ottenere DenaroComprare TV
6868
Esempio: continuaEsempio: continua
•• Infatti, ora dobbiamo considerare che un nodo AND necessita la sInfatti, ora dobbiamo considerare che un nodo AND necessita la soluzione di oluzione di tutti i nodi figli.tutti i nodi figli.
•• Supponiamo che il costo di ogni arco sia 1.Supponiamo che il costo di ogni arco sia 1.•• Il nodo più promettente se preso singolarmente è G che ha valoreIl nodo più promettente se preso singolarmente è G che ha valore 3 per f' e 3 per f' e
che è parte dell'arco più promettente Gche è parte dell'arco più promettente G--H il cui costo totale è 9.H il cui costo totale è 9.•• Ma questo arco non fa parte del cammino migliore Ma questo arco non fa parte del cammino migliore perchèperchè è accoppiato all'arco è accoppiato all'arco
II--J che ha costo 27.J che ha costo 27.•• Il cammino che va da A a i nodi E e F passando per B è migliore Il cammino che va da A a i nodi E e F passando per B è migliore avendo costo avendo costo
18.18.•• Dunque il prossimo nodo da espandere va cercato esaminando E e FDunque il prossimo nodo da espandere va cercato esaminando E e F..
A
JIHGFE
DCB
(38)(18)
(17) (9) (27)
(5) (10) (3) (4) (15) (10)
6969
Algoritmo di riduzione del problema Algoritmo di riduzione del problema (algoritmo semplificato dell'algoritmo AO*)(algoritmo semplificato dell'algoritmo AO*)
•• Introduciamo un nuovo valore: COSTOIntroduciamo un nuovo valore: COSTO--LIMITE, che se superato dal LIMITE, che se superato dal costo stimato di una soluzione ci porta ad abbandonare la ricerccosto stimato di una soluzione ci porta ad abbandonare la ricerca.a.
•• COSTOCOSTO--LIMITE: anche se trovassimo una soluzione sarebbe troppo LIMITE: anche se trovassimo una soluzione sarebbe troppo alta per essere accettata.alta per essere accettata.
•• Algoritmo:Algoritmo:
–– InizializzaInizializza il grafo al nodo iniziale;il grafo al nodo iniziale;
–– Si intraprende il seguente ciclo Si intraprende il seguente ciclo finchèfinchè o al nodo iniziale viene o al nodo iniziale viene associata l'etichetta RISOLTO o il suo costo supera COSTOassociata l'etichetta RISOLTO o il suo costo supera COSTO--LIMITELIMITE
7070
Algoritmo di riduzione del problema Algoritmo di riduzione del problema (algoritmo semplificato dell'algoritmo AO*)(algoritmo semplificato dell'algoritmo AO*)•• InizializzaInizializza il grafo al nodo iniziale;il grafo al nodo iniziale;•• Si intraprende il seguente ciclo Si intraprende il seguente ciclo finchèfinchè o al nodo iniziale viene o al nodo iniziale viene
associata l'etichetta RISOLTO o il suo costo supera COSTOassociata l'etichetta RISOLTO o il suo costo supera COSTO--LIMITE:LIMITE:–– si attraversa il grafo, partendo dal nodo iniziale e, percorrendsi attraversa il grafo, partendo dal nodo iniziale e, percorrendo il miglior o il miglior
cammino corrente, si accumula l'insieme dei nodi lungo tale cammcammino corrente, si accumula l'insieme dei nodi lungo tale cammino che ino che non sono ancora stati espansi o etichettati come risolti.non sono ancora stati espansi o etichettati come risolti.
–– si sceglie uno di questi nodi e lo si espande. Se non ci sono susi sceglie uno di questi nodi e lo si espande. Se non ci sono successori si ccessori si associa a tale nodo il valore di COSTOassocia a tale nodo il valore di COSTO--LIMITE. Altrimenti, si aggiungono LIMITE. Altrimenti, si aggiungono al grafo i suoi successori e per ognuno di essi si calcola il vaal grafo i suoi successori e per ognuno di essi si calcola il valore di f' lore di f' (utilizzando solo h' e ignorando g). Se il valore di f' per un n(utilizzando solo h' e ignorando g). Se il valore di f' per un nodo risulta 0 lo odo risulta 0 lo si marca come RISOLTO.si marca come RISOLTO.
–– Si modifica la stima f' del nodo appena espanso in modo da tenerSi modifica la stima f' del nodo appena espanso in modo da tenere conto e conto della nuova informazione fornita dai successori e si propaga alldella nuova informazione fornita dai successori e si propaga all'indietro 'indietro nel grafo tale modifica. Se da un nodo parte un arco i cui discenel grafo tale modifica. Se da un nodo parte un arco i cui discendenti sono ndenti sono tutti etichettati con RISOLTO si etichetta il nodo stesso con RItutti etichettati con RISOLTO si etichetta il nodo stesso con RISOLTO.SOLTO.
•• A ogni nodo che viene visitato risalendo nel grafo si decide quaA ogni nodo che viene visitato risalendo nel grafo si decide quale dei le dei suoi archi uscenti è più promettente e lo si marca come parte desuoi archi uscenti è più promettente e lo si marca come parte del l cammino migliore corrente: ciò può avere come effetto che il camcammino migliore corrente: ciò può avere come effetto che il cammino mino migliore corrente cambi.migliore corrente cambi.
7171
ESEMPIOESEMPIO
•• Prima del passo 1Prima del passo 1
•• Prima del passo 2Prima del passo 2
A (5)
A
B C D
(3) (4) (5)
(9)
(6)
7272
ESEMPIO CONTINUAESEMPIO CONTINUA•• Prima del passo 3Prima del passo 3
A
B C D
(3) (4)
(10)
(9)
(11)
(4)(4)
E F
7373
ESEMPIO CONTINUAESEMPIO CONTINUA•• Prima del passo 4Prima del passo 4•• Alcune osservazioni sull'algoritmoAlcune osservazioni sull'algoritmo::
–– Il cammino migliore da un nodo all'altro non è sempre quello a mIl cammino migliore da un nodo all'altro non è sempre quello a minor inor costo. Ciò è dovuto alla presenza di nodi AND per cui singoli cacosto. Ciò è dovuto alla presenza di nodi AND per cui singoli cammini da mmini da nodo a nodo non possono essere considerati indipendentemente da nodo a nodo non possono essere considerati indipendentemente da altri altri cammini che passano per nodi connessi con quelli originari attracammini che passano per nodi connessi con quelli originari attraverso verso archi AND.archi AND.
A
B C D(6) (4) (10)
(12)
(4)(4)
E FG H
(5) (7)
7474
Esempio:Esempio: Un cammino più lungo può Un cammino più lungo può essere miglioreessere migliore
•• I nodi sono espansi nell'ordine alfabetico. Il cammino verso E dI nodi sono espansi nell'ordine alfabetico. Il cammino verso E da J è a J è più lungo di quello che passa per C, ma dal momento che quest'ulpiù lungo di quello che passa per C, ma dal momento che quest'ultimo timo dipende da D che è insolubile è migliore il cammino che passa dadipende da D che è insolubile è migliore il cammino che passa da J.J.
•• Inoltre alcuni sottoproblemi possono interagire.Inoltre alcuni sottoproblemi possono interagire.
A
B C D
G H E F
I J
Insolubile
7575
Esempio:Esempio:
•• Il grafo indica che per risolvere A si devono risolvere sia C siIl grafo indica che per risolvere A si devono risolvere sia C sia D. Ma a D. Ma poi considera separatamente il problema di risolvere C e D. Se, poi considera separatamente il problema di risolvere C e D. Se, risolvendo prima D, E risulta essere il cammino migliore risolverisolvendo prima D, E risulta essere il cammino migliore risolverà E, rà E, mentre a livello globale sarebbe stato più opportuno utilizzare mentre a livello globale sarebbe stato più opportuno utilizzare C.C.
A
C
D
E
(5) (2)
7676
TRASFORMAZIONE DI ALBERI AND/OR IN TRASFORMAZIONE DI ALBERI AND/OR IN ALBERI DI RICERCA:ALBERI DI RICERCA:
•• g.g.•• e.e.•• i.i.
•• s s →→ a.a.•• c and e c and e →→ a.a.•• f f →→ c.c.•• g g →→ c.c.•• h h →→ b.b.•• i i →→ b.b.
•• Goal: a and bGoal: a and b
a and b
a b
s c and e h i
SI
c e
f g SI
SI
7777
TRASFORMAZIONE DI ALBERI AND/OR IN TRASFORMAZIONE DI ALBERI AND/OR IN ALBERI DI RICERCA:ALBERI DI RICERCA:
NotaNota::•• Non ha alcuna influenza, Non ha alcuna influenza,
al fine del al fine del raggiungimento della raggiungimento della soluzione, l’ordine di soluzione, l’ordine di espansione dei goal in espansione dei goal in AND.AND.
–– R1: R1: f(af(a) ) →→ a(Xa(X).).–– R2: R2: b(Xb(X) and ) and c(Xc(X) ) →→ a(Xa(X).).–– R3: R3: d(Yd(Y) ) →→ c(Yc(Y).).–– R4: R4: e(Xe(X) and ) and f(Xf(X) ) →→ d(Xd(X).).–– R5: R5: b(ab(a) ) →→ a(aa(a).).
•• GOAL: GOAL: a(Xa(X))
7979
ALBERO DI RICERCA BACKWARD:ALBERO DI RICERCA BACKWARD:a(X)
R1 R2 R5 {X/a} f(a) b(X),c(X) b(a)
F1 {X/a} F2 {X/b} F1 fail
c(a) c(b) SI X = a
R3 R3
d(a) d(b)
R4 R4e(a),f(a) e(b),f(b)
F4 F3
f(a) f(b)
fail SI X = b
8080
ALTRE TECNICHE EURISTICHEALTRE TECNICHE EURISTICHE
•• SCELTA IN BASE AGLI OPERATORI SCELTA IN BASE AGLI OPERATORI –– (regole, task inseriti in un'agenda):(regole, task inseriti in un'agenda):
•• A) Insita nel controllo e influenzata IMPLICITAMENTE dall'utenteA) Insita nel controllo e influenzata IMPLICITAMENTE dall'utente::–– PrologProlog: ordine testuale delle regole: ordine testuale delle regole–– OPS: strategie in base alla forma dell'antecedente (LEX MEA)OPS: strategie in base alla forma dell'antecedente (LEX MEA)
•• B)B) Influenzata ESPLICITAMENTE dall'utente:Influenzata ESPLICITAMENTE dall'utente:–– Attribuire alle regole dei valori di priorità rappresentati comeAttribuire alle regole dei valori di priorità rappresentati come numeri interi; numeri interi;
in questo modo l’interprete selezionerà sempre la regola applicain questo modo l’interprete selezionerà sempre la regola applicabile a più bile a più alta priorità.alta priorità.
8181
ESEMPIO:ESEMPIO:R1: IF <la temperatura è maggiore di 100 gradi>, R1: IF <la temperatura è maggiore di 100 gradi>, AND <la pressione ha valore p1> AND <la pressione ha valore p1> THEN <attiva la valvola .....> THEN <attiva la valvola .....> AND <segnala una situazione di allarme all'operatore> AND <segnala una situazione di allarme all'operatore> ------ priorità 10priorità 10
R2: IF <la pressione ha valore p1> R2: IF <la pressione ha valore p1> THEN <attiva la procedura di funzionamento normale PROC5> THEN <attiva la procedura di funzionamento normale PROC5> ------ priorità 5.priorità 5.
•• PRIORITÀ DINAMICHE: PRIORITÀ DINAMICHE: –– a) lo stato della memoria di lavoro;a) lo stato della memoria di lavoro;–– b) la presenza di particolari regole applicabili;b) la presenza di particolari regole applicabili;–– c) la precedente esecuzione di regole correlate; c) la precedente esecuzione di regole correlate; –– d) l'andamento dell’esecuzione per particolari scelte fatte d) l'andamento dell’esecuzione per particolari scelte fatte
precedentemente.precedentemente.
8282
•• PROBLEMI:PROBLEMI:–– 1) risulta particolarmente complesso individuare il corretto val1) risulta particolarmente complesso individuare il corretto valore di ore di
priorità;priorità;–– 2) l’attribuzione dei valori di priorità è oscura: diventa dunqu2) l’attribuzione dei valori di priorità è oscura: diventa dunque carente nel e carente nel
sistema la capacità di spiegazione.sistema la capacità di spiegazione.–– 3) la modificabilità della base di conoscenza diminuisce: contro3) la modificabilità della base di conoscenza diminuisce: controllo e llo e
conoscenza sul dominio non separati; le regole presentano dipendconoscenza sul dominio non separati; le regole presentano dipendenze enze implicite.implicite.
•• METAMETA--CONOSCENZA=CONOSCENZA SULLA CONOSCENZACONOSCENZA=CONOSCENZA SULLA CONOSCENZA•• Può risolvere i problemi precedentemente citati (vasta applicaziPuò risolvere i problemi precedentemente citati (vasta applicazione one
non solo per il controllo).non solo per il controllo).
•• metameta--regola: regola: –– MR1 "Usa regole che esprimono situazioni di allarme prima di regMR1 "Usa regole che esprimono situazioni di allarme prima di regole che ole che
esprimono situazioni di funzionamento normale".esprimono situazioni di funzionamento normale".
METAMETA--CONOSCENZA=CONOSCENZA CONOSCENZA=CONOSCENZA SULLA CONOSCENZASULLA CONOSCENZA
8383
•• ESEMPI: Sistemi Esperti: ESEMPI: Sistemi Esperti: MolgenMolgen, , NeomycinNeomycin, , TeiresiasTeiresias..
•• VANTAGGI:VANTAGGI:–– a) il sistema è maggiormente flessibile e modificabile; un cambia) il sistema è maggiormente flessibile e modificabile; un cambiamento amento
nella strategia di controllo implica semplicemente il cambiamentnella strategia di controllo implica semplicemente il cambiamento di o di alcune metaalcune meta--regole. regole.
–– b) la strategia di controllo è semplice da capire e descrivere.b) la strategia di controllo è semplice da capire e descrivere.–– c) potenti meccanismi di spiegazione del proprio comportamento.c) potenti meccanismi di spiegazione del proprio comportamento.
METAMETA--CONOSCENZA=CONOSCENZA CONOSCENZA=CONOSCENZA SULLA CONOSCENZASULLA CONOSCENZA
8484
TEREISIAS: META CONOSCENZA PER TEREISIAS: META CONOSCENZA PER INFLUENZARE IL CONTROLLOINFLUENZARE IL CONTROLLO•• Tale metaTale meta--conoscenza ha tre scopi fondamentali:conoscenza ha tre scopi fondamentali:
–– a)a) sono utilizzate metasono utilizzate meta--regole per definire strategie di controllo;regole per definire strategie di controllo;–– b)b) sono utilizzati "modelli" per descrivere regole di livello oggetsono utilizzati "modelli" per descrivere regole di livello oggetto;to;–– c) c) sono utilizzati metodi descrittivi espliciti per descrivere la sono utilizzati metodi descrittivi espliciti per descrivere la
rappresentazione utilizzata e dunque poterla modificare.rappresentazione utilizzata e dunque poterla modificare.
–– IFIF <ci sono regole che <ci sono regole che menzionanomenzionano........> ........> –– ANDAND <ci sono regole che <ci sono regole che menzionanomenzionano........>.........>.–– THENTHEN <le prime dovrebbero essere eseguite <le prime dovrebbero essere eseguite –– primaprima delle seconde> (FC=0.4).delle seconde> (FC=0.4).
•• MetaMeta--Regola 2Regola 2–– IFIF <il paziente è......> <il paziente è......> –– ANDAND <ci sono regole che <ci sono regole che menzionanomenzionano ...> ...> –– THENTHEN <è certo che nessuna di esse <è certo che nessuna di esse –– sarà utilesarà utile ulteriormente> (FC=1).ulteriormente> (FC=1).
8585
•• metameta--regola 1: ordine parziale sulle regole di livello oggetto;regola 1: ordine parziale sulle regole di livello oggetto;•• metameta--regola 2: utilità di certe regole di livello oggetto;regola 2: utilità di certe regole di livello oggetto;
–– NOTA: La sintassi delle metaNOTA: La sintassi delle meta--regole e` identica a quella di livello oggettoregole e` identica a quella di livello oggetto
•• NUOVE FUNZIONI:NUOVE FUNZIONI:–– MENTIONSMENTIONS: serve per referenziare le regole di livello oggetto;: serve per referenziare le regole di livello oggetto;
–– UTILITY e BEFOREUTILITY e BEFORE: servono per influenzare la strategia di : servono per influenzare la strategia di controllo.controllo.
TEREISIAS: META CONOSCENZA PER TEREISIAS: META CONOSCENZA PER INFLUENZARE IL CONTROLLOINFLUENZARE IL CONTROLLO
8686
FUNZIONAMENTOFUNZIONAMENTO::
•• Trova le regole di livello oggetto applicabili (L); Trova le regole di livello oggetto applicabili (L);
•• Trova le metaTrova le meta--regole associate (L');regole associate (L');
•• Valuta ogni metaValuta ogni meta--regola di L' e determina se è applicabile per alcune regole regola di L' e determina se è applicabile per alcune regole di L;di L;
•• Ordina o toglie elementi da L in accordo ai criteri delle metaOrdina o toglie elementi da L in accordo ai criteri delle meta--regole;regole;
•• Esegue ogni regola rimasta in L nell'ordine ottenuto.Esegue ogni regola rimasta in L nell'ordine ottenuto.
TEREISIAS: META CONOSCENZA PER TEREISIAS: META CONOSCENZA PER INFLUENZARE IL CONTROLLOINFLUENZARE IL CONTROLLO
8787
•• Così si espande anche l'interprete:Così si espande anche l'interprete:
META REGOLE(META OPERATORI)
METAREGOLEAPPLICABILI
INTERPRETE O CONTROLLO
MEMORIA DI LAVORO
MatchingSelezioneEsecuzione
METAMETA--CONOSCENZA PER IL CONTROLLOCONOSCENZA PER IL CONTROLLOUNA NUOVA ARCHITETTURAUNA NUOVA ARCHITETTURA
