Risoluzione di problemi
e
ricerca
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Un semplice agente risolutore di problemi
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Un esempio: vacanza in Romania.
Attualmente in Arad. L’aereo parte domani da Bucarest.
Formulare un goal:
esssere in Bucarest
Formulare un problema:
stati: varie città
operatori: guidare da una città all’altra
Trovare una soluzione:
sequenza di città, es: Arad, Sibiu, Faragas, Bucarest
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Il mondo dell’aspirapolvere
Tipi di problemi:
Stato Singolo : {5}
Stato Multiplo: {1,2,3,4,5,7,8}
destra produce {2,4,6,8}
Contingenza: {5}
Aspirare dove non c’è polvere
può produrre dello sporco
È necessario un sensore
Ingegneria della conoscenza e sistemi esperti
Azioni: destra, sinistra, aspira
Dario Bianchi , 1999
Risoluzione di problemi
Formulazione di un problema a singolo stato:
stato iniziale: essere “in Arad”
operatori: Arad -> Zerind, Arad -> Sibiu etc.
La funzione successore S fa passare dallo stato x agli stati S(x).
L’insieme degli stgati raggiungibili definisce lo spazio degli stati.
test obiettivo:
esplicito: “in Bucarest”
implicito: “NonSporco(x)”
costo del cammino: es. Somma delle distanze, numero di operatori applicati,
etc.
soluzione: una sequenza di operatori che porta da uno stato iniziale
a uno stato obiettivo.
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Una tipica istanza del rompicapo dell’8
Stati: uno stato specifica la posizione di ciascuna delle 8 tessere.
Operatori: lo spazio vuoto si muove a destra, a sinistra, sopra, sotto.
Test obiettivo: lo stato rispecchia la configurazione obiettivo (Goal).
Costo del cammino: ciascun passo costa 1. Il costo del cammino
coincide con la sua lunghezza.
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Il problema delle 8 regine
Stati: qualsiasi configurazione
da 0 a 8 regine sulla scacchiera.
Operatori: aggiungi una regina
in qualsiasi quadrato
Test obiettivo: 8 regine sulla
scacchiera, nessuna minacciata.
Costo cammino: 0.
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Mondo dell’aspirapolvere (singolo stato).
Stati: uno degli 8 stati della figura.
Operatori: spostati a destra, spostati a sinistra, aspira.
Test obiettivo: non lasciare alcuna sporcizia nei quadrati.
Costo del cammino: ciascuna azione costa 1.
Risolvere il problema da uno stato di partenza comporta seguire le frecce nel diagramma
degli stati fino a uno statoi obiettivo.
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Mondo dell’aspirapolvere (stato
multiplo).
In ogni istante l’apirapolvere si
trovain uno stato di un insieme ma
non sa quale stato dell’insieme è.
Stati: sottoinsiemi degli stati 1-8 della
figura.
Operatori: spostati a destra, spostati a
sinistra, aspira.
Test obiettivo: tutti gli stati
dell’insieme degli stati non
contengono sporcizia.
Costo del cammino: ciascuna azione
costa 1.
Una soluzione del problema è una
qualsiasi sequenza che porti
dall’insieme iniziale degli stati ad un
insieme di stati senza sporcizia.
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Cercare soluzioni
Generare sequenze di azioni.
Espansione: si parte da uno stato e apllicando gli operatori (o la funzione
successore) si generano nuovi stati.
Strategia di ricerca: ad ogni passo scegliere qiale stato espandere.
Albero di ricerca: rappresenta l’espansione degli stati a partire dallo stato
iniziale (la radice dell’albero). Le fogle dell’albero rappresentano gli stati da
espandere.
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Cercare soluzioni
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
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Albero di ricerca parziale per trovare un
itinerario da Arad a Bucarest.
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
L’algoritmo generale di ricerca
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
L’algoritmo generale di ricerca
Tramite l’argomento Queuing-Fn viene passata una
funzione per accodare i nodi ottenuti dall’espansione
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Strategie di ricerca
Una strategia di ricerca è un ordine di espansione dei nodi.
Completezza: la strategia garantisce di trovare una soluzione quando ne
esiste una?
Complessità temporale: quanto tempo ci vuole per trovare una
soluzione?
Complessità spaziale: quanta memoria occorre per effettuare una
ricerca?
Ottimalità: la strategia trova una soluzione ottima (a costo minimo)
quando ci sono varie soluzioni differenti?
La complessità temporale e spaziale è misurata in termini di:
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)
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Ricerca in ampiezza
QueueingFn = metti i successori alla fine della coda
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
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)
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
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.
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Ricerca a costo uniforme
ciascun nodo è etichettato con il costo g(n)
QueueingFn = inserisci i successori in ordine di
costo di cammino crescente
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Ricerca in profondità
si assume che i nodi di profondità 3 non abbiano successori
QueueingFn = inserisci i successori all’inizio della coda.
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
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)
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Ricerca con limite di profondità
Si scende lungo un ramo finchè non si trova la soluzione o
si raggiunge il limite di profondità.
Si evita di scendere lungo rami infiniti.
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Ricerca con approfondimento iterativo
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Ricerca con approfondimento iterativo
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
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)
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Ricerca bidirezionale
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
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à.
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Evitare ripetizioni di stati
Uno spazio degli stati che genera un albero di ricerca esponenziale . Il
lato sinistro mostra lo spazio degli stati, nel quale ci sono due azioni
possibili che conducono da A a B, due da B a C e così via. Il lato destro
mostra l`albero di ricerca corrispondente.
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Metodi di ricerca informati
usano conoscenza specifica relativa al problema
Ricerca Best First
Usa una funzione di valutazione che calcola un numero che rappresenta
la desiderabilità relativa all’espansione di nodo.
Best-first significa scegliere come nodo da espandere quello che sembra
più desiderabile.
QueuingFn = inserisce I successori in ordine decrescente di
desiderabilità.
Casi particolari:
•ricerca greedy (golosa)
•ricerca A*
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Una realizzazione della ricerca best-first che usa l’algoritmo
di ricerca generale e la funzione di valutazione EvalFn
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Mappa della Romania con distanze stradali e distanze in linea
d’aria da Bucarest
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Ricerca greedy (golosa)
Funzione di valutazione h(n) (heuristic)
= stima del costo dal nodo n al goal.
Es. h(n) = distanza in linea d’aria fra n e Bucarest.
La ricerca golosa espande quel nodo che sembra essere il più
vicino all’obiettivo (goal).
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Stadi di una ricerca golosa per Bucarest usando come funzione di valutazione la
distanza in linea d’aria. I nodi sono etichettati con i valori di h
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Ricerca A*
Evita di espandere quei cammini che sono già costosi.
Funzione di valutazione f(n) = g(n) + h(n)
g(n) = costo effettivo dalla radice al nodo n
h(n) = costo stimato dal nodo n al nodo obiettivo (goal)
f(n) = costo totale stimato di un cammino che arriva al goal
passando per n
La ricerca A* usa una euristica ammissibile cioè:
h(n) <= h*(n) dove h*(n) è il vero costo da n al goal.
(Nel nostro esempio la distanza in linea d’aria non svrastima mai
l’effettiva distanza stradale)
Teorema: la ricerca A* è ottimale (e completa)
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Stadi di una ricerca A* per Bucarest usando come funzione di valutazione
f = g + h ( h è la distanza in linea d’aria per Bucarest).
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Ottimalità di A*
Mappa della Romania che mostra le frontiere f=380, f=400, f=420,
con Arad come stato iniziale. I nodi dentro una frontiera hanno
valori più bassi del valore della frontiera.
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Funzioni euristiche
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 devono assumere
nella configurazione obiettivo. La distanza è una somma delle 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
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999
Risoluzione di problemi
Confronto fra la ricerca ad approfondimento iterativo
e l’algoritmo A* con h1 e h2
Ingegneria della conoscenza e sistemi esperti
Dario Bianchi , 1999