Sistemi basati su conoscenza
Metodi di ricerca informata
Prof. M.T. PAZIENZA
a.a. 2003-2004
Strategia di ricerca
• Le strategia di ricerca non informata trovano
soluzioni (spesso non efficienti) a problemi
generando sistematicamente nuovi stati che sono
poi verificati rispetto all’obiettivo. (possibile
esplosione combinatoria dello spazio di ricerca)
• Le strategia di ricerca informata, utilizzando
conoscenza addizionale specifica al problema e
al dominio di applicabilità, trovano soluzioni più
efficienti, ovvero riducono il costo della ricerca.
Euristica - Ricerca euristica
Euristica (definizioni)
“tutto ciò che supporta meglio l’attività di
ricerca”
“lo studio di metodi e regole a supporto
dell’attività di ricerca”
“un processo che può risolvere un dato
problema ma che non offre alcuna garanzia
di farlo (euristica per quel problema)”
Euristica - Ricerca euristica
Euristica (definizione di Minsky, 1961)
“tutto ciò che è collegato al miglioramento delle
prestazioni del problem-solving;
si usa in relazione a qualsiasi metodo od espediente
per migliorare l’efficienza di un programma di
problem-solving”
ma:
Metodi imperfetti non sono necessariamente euristici,
né è vero il viceversa!
Euristica - Ricerca euristica
Euristica (definizione di Feigenbaum e Feldman, 1963)
“una euristica (regola o metodo) è una regola,
strategia, semplificazione o qualunque altro
strumento che drasticamente limita la ricerca di
soluzioni nello spazio degli stati del problema.
Le euristiche non garantiscono soluzioni ottimali; non
garantiscono soluzioni in ogni caso.
Una euristica utile è ciò che offre soluzioni che sono
abbastanza buone il più delle volte.
Euristica - Ricerca euristica
Ricerca euristica (definizione di Nilsson, 1971)
“E’ importante distinguere tra ricerca cieca e ricerca
euristica: la prima corrisponde alla generazione
sistematica ed al test degli elementi dello spazio di
ricerca , lasciando spazio all’introduzione di
informazioni addizionali sul dominio dello specifico
problema. Quando tali informazioni vanno oltre le
necessarie per definire una classe di problemi di
ricerca, allora è possibile restringere notevolmente
la ricerca. In tal caso si parla di ricerca euristica
piuttosto che ricerca cieca.”
Strategia di ricerca informata
Le tecniche euristiche non sono facilmente adattabili a
nuovi problemi: tecniche sostanzialmente simili
vengono reinventate continuamente.
Esiste l’interesse nello sviluppare algoritmi di ricerca
euristici generalizzati le cui proprietà possano essere
studiate indipendentemente dal particolare dominio e
dal programma che li usi.
Dato un problema generale di rappresentazione, le
tecniche di ricerca euristica più basilari possono
essere studiate come variazione dei metodi di ricerca
cieca per lo stesso tipo di rappresentazione del
problema.
Strategia di ricerca euristica
I punti in cui applicare l’informazione euristica
sono relativi a:
• decidere quali nodi espandere (invece di
applicare tecniche in profondità od in ampiezza)
• nel corso dell’espansione del nodo, decidere
quale successore/i generare (invece di una
generazione cieca di tutti i possibili successori
ad un dato istante)
• decidere che certi nodi devono essere scartati,
od eliminati, dall’albero di ricerca.
Strategia di ricerca
In genere la specifica strategia di ricerca si distingue
per la diversa funzione di valutazione usata per
determinare il prossimo nodo da espandere.
L’idea generale è quella di espandere il nodo che
sembra “più promettente”. Una ricerca che
implementa questa idea è chiamata ricerca
ordinata o best-first search.
La funzione di valutazione determina il valore di
desiderabilità (o non desiderabilità)
dell’espansione di ogni specifico nodo.
Algoritmi di ricerca best-first
I nodi sono ordinati in modo che venga espanso
prima il nodo (che sembra) migliore secondo la
funzione di valutazione
Funzioni di valutazione
Quando tale valutazione è fornita da una
stima (e non viene determinata esattamente)
si parla di funzione euristica, quindi
La funzione euristica h(n) stima il costo del
cammino più conveniente dallo stato del
nodo n ad uno stato obiettivo
Ogni funzione euristica è specifica al
problema
Tecniche euristiche
Nei sistemi esperti le tecniche euristiche
erano viste come “regole empiriche” che gli
esperti del dominio potevano usare per
generare “buone soluzioni” senza ricercare
esaustivamente.
Se le regole euristiche vengono espresse come
regole, si parla di sistemi basati su regole.
Tecniche euristiche
Euristica è qualunque
tecnica che migliora le prestazioni del
compito di risoluzione del problema
nel caso medio, ma non migliora
necessariamente nel caso peggiore.
Negli algoritmi di ricerca si riferisce ad una
funzione che fornisce una stima del costo
della soluzione
Ricerca golosa
Una ricerca di best-first che usa h (minimizzare il
costo per raggiungere l’obiettivo) per selezionare
il nodo successivo da espandere è detta ricerca
golosa.
Viene espanso prima il nodo giudicato più vicino
allo stato obiettivo da una qualunque funzione
euristica h purché:
h(n)=0
se n è un nodo obiettivo
La ricerca golosa è simile ad una ricerca in
profondità; segue un cammino fino all’obiettivo,
per tornare indietro quando si imbatte in un vicolo
cieco.
Ricerca di itinerario (euristica)
La distanza in linea d’aria dall’obiettivo,
ovvero la distanza in linea d’aria tra n e la
posizione dell’obiettivo, hDLA (n)
viene considerata una buona funzione
euristica nella ricerca di un itinerario
Ricerca di itinerario (euristica)
Ricerca di itinerario (euristica)
Si può calcolare
hDLA (n)
solo se si conoscono le coordinate dei nodi.
Queste ultime (e altre informazioni
aggiuntive) permettono alle euristiche di
aiutare a ridurre il costo della ricerca
Ricerca di itinerario (euristica)
Ricerca di itinerario (euristica)
L’euristica
hDLA (n)
determina un costo di ricerca minimo,
trova una soluzione senza mai espandere alcun
nodo che non sia sul cammino della soluzione.
Non è perfettamente ottimale (ricerca golosa),
tende a trovare una soluzione velocemente
anche se non ottimale
Ricerca di itinerario
(ricerca golosa - euristica)
Ricerca non ottimale ed incompleta
Può intraprendere un vicolo cieco con ricerca infinita
m
Complessità temporale nel caso peggiore
O(b )
con m profondità massima dello spazio di ricerca e b fattore
di ramificazione.
Complessità spaziale = complessità temporale (tutti i nodi
sono mantenuti in memoria)
Una buona funzione euristica può ridurre le due
complessità (in funzione della tipologia del problema e
natura della funzione h)
Ricerca A* (euristica ammissibile)
L’algoritmo A* cerca il cammino di minimo costo dal
punto di partenza al nodo d’arrivo nel grafo dello
spazio degli stati (ovvero il cammino contenente il
minor numero di archi nel caso pesino ognuno 1).
La funzione, quindi, considera che ciascun nodo n avrà
due componenti:
1. il costo per raggiungere n dal nodo di partenza
2. il costo per raggiungere il nodo obiettivo dal nodo n.
Ricerca A* (euristica ammissibile)
g(n) = costo del cammino dal nodo iniziale al
nodo n
h(n) = costo stimato del cammino più
conveniente da n all’obiettivo
f(n) = g(n) + h(n)
f(n) = costo stimato della soluzione più
conveniente attraverso n
Strategia di ricerca
La “ricerca di una soluzione” avviene prima
della esecuzione delle azioni corrispondenti.
La ricerca di una soluzione coincide con
l’identificazione di una sequenza
(possibilmente la migliore) di azioni da
proporre all’agente perché vengano
eseguite.
Ricerca A* (euristica ammissibile)
La soluzione più conveniente espande prima il
nodo con il valore più basso di f
Scegliere la funzione euristica h che non
sopravvaluti mai il costo per raggiungere
l’obiettivo
Se h è ammissibile, f(n) non sopravvaluta mai il
costo reale della soluzione migliore attraverso n.
Lungo qualsiasi cammino che parte dalla radice, il
costo di f non decresce mai (proprietà di
monotonia)
Ricerca A* (euristica ammissibile)
Cercare funzioni euristiche
Se per un problema esiste una collezione di
euristiche ammissibili, e nessuna domina le altre,
allora si pone:
h(n)  max( h1 ),..., h(n))
Usare informazioni statistiche