Metodi di ricerca informata
Prof. M.T. PAZIENZA
a.a. 2013-2014
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 non informata sono dette anche
cieche perché non usano conoscenza specifica sul
problema; non usano nessuna informazione relativa
all’obiettivo cui stanno mirando finché non ci capitano su.
Strategia di ricerca
Le strategie di ricerca informata definiscono
metodologie risolutive che usano informazione
euristica per decidere quali sono i nodi più
convenienti da scegliere ad ogni passo.
Le strategie 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 addizionali
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
L’informazione euristica rappresenta conoscenza esplicita
rispetto ad un nodo, si esprime come una funzione h(n)
che rappresenta una stima della lunghezza del cammino
da un nodo n al nodo obiettivo.
Si assume che il valore euristico possa essere derivato
dalle proprietà di un nodo.
La funzione euristica è un modo veloce per informare la
strategia di ricerca relativamente alla direzione per
raggiungere il nodo.
Essa fornisce una indicazione su quale vicino di un nodo
condurrà all’obiettivo più facilmente.
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
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 attivare ricerche
esaustivamente.
Se le euristiche vengono espresse come regole, si
parla di sistemi basati su regole.
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
All’interno dell’algoritmo di ricerca, si può inserire
conoscenza nella modalità di espansione del prossimo nodo.
I punti in cui applicare l’informazione euristica sono relativi a:
• decidere quali nodi espandere (invece di applicare tecniche
generali di ricerca 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
L’idea generale è quella di espandere il nodo che
sembra “più promettente”.
In genere la specifica strategia di ricerca si distingue per
la diversa funzione di valutazione usata per
determinare il prossimo nodo da espandere.
La funzione di valutazione determina il valore di
desiderabilità (o non desiderabilità) dell’espansione di
ogni specifico nodo.
Funzioni di valutazione
Quando tale valutazione è fornita da una stima (e non viene
determinata esattamente) si parla di funzione euristica di
valutazione, quindi
La funzione euristica h(n) stima il costo del cammino più
conveniente dallo stato del nodo n ad uno stato obiettivo;
per cui suggerisce di espandere il nodo che “sembra” più
promettente.
Ogni funzione euristica è specifica al problema, ovvero
viene definita a seconda del problema che si sta risolvendo
Algoritmi di ricerca best-first
La più semplice funzione euristica è scegliere sempre
l’elemento di frontiera che appare essere più vicino
all’obiettivo, ovvero scegliere il nodo n con il più basso
valore di h(n).
Implementare questa strategia consiste nel trattare la
frontiera come una coda a priorità, ordinata con la
funzione h(n).
E’ simile alla ricerca a costo uniforme, dove la scelta cade
sull’elemento con minimo valore dell’euristica h piuttosto
che sull’elemento della coda con minimo valore del costo
del cammino g fino a quel 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
Algoritmi di ricerca best-first
La ricerca best-first persegue un certo numero di cammini
espandendo il nodo che sembra localmente il migliore.
Ha lo svantaggio (come la ricerca in ampiezza) di usare
uno spazio esponenziale rispetto alla lunghezza del
cammino.
A differenza della ricerca in ampiezza, non assicura di
trovare una soluzione anche se ne esiste una. Inoltre non
trova necessariamente per primo il cammino più breve.
Ricerca golosa
Esiste tutta una famiglia di algoritmi di best-first con
differenti funzioni di valutazione.
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)
Nel caso della ricerca di un itinerario, la
distanza in linea d’aria dall’obiettivo,
hDLA (n)
ovvero la distanza in linea d’aria tra n e la posizione
dell’obiettivo,
viene considerata una buona funzione
euristica
Ricerca di itinerario (with step costs in km)
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)
La ricerca golosa minimizza il costo stimato per
raggiungere l’obiettivo h(n).
La ricerca a costo uniforme minimizza il costo
del cammino dall’origine al nodo corrente
g(n).
Il costo stimato della soluzione più conveniente
attraverso n (ricerca A*) è dato da f(n) pari
alla somma
f(n)=g(n)+h(n)
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
La soluzione più conveniente espande prima il nodo con
il valore più basso di f
Ricerca A* (euristica ammissibile)
*
A
search example
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))
In alternativa usare informazioni statistiche
Argomenti trattati in questa lezione
• Strategie di ricerca
• Cosa si intende per euristica; livello di
generalità/specificità supportato
• Quali informazioni fornisce una funzione
euristica
• Algoritmi di ricerca best first: ricerca golosa,
DLA, A*
• Come determinare una funzione euristica
ottimale per un problema