Metodi di ricerca informata Prof. M.T. PAZIENZA a.a. 2013-2014.

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.


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 (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 (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.


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.”


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 obiettivoda 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.


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.


I nodi sono ordinati in modo che venga espanso prima il nodo (che sembra) migliore secondo la funzione di valutazione


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 obiettivoLa 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,

ovvero la distanza in linea d’aria tra n e la posizione dell’obiettivo,

viene considerata una buona funzione euristica

)(nhDLA

Ricerca di itinerario (with step costs in km)


Si può calcolare

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

)(nhDLA


L’euristica

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

)(nhDLA

Ricerca di itinerario (ricerca golosa - euristica)

Ricerca non ottimale ed incompletaPuò intraprendere un vicolo cieco con ricerca infinitaComplessità temporale nel caso peggiorecon 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)

)( mbO

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)


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.


g(n) = costo del cammino dal nodo iniziale al nodo nh(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

A* search example

Cercare funzioni euristiche

Se per un problema esiste una collezione di euristiche ammissibili, e nessuna domina le altre, allora si pone:

In alternativa usare informazioni statistiche

))(),...,max()( 1 nhhnh

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

Metodi di ricerca informata Prof. M.T. PAZIENZA a.a. 2013-2014.

Documents

Transcript of Metodi di ricerca informata Prof. M.T. PAZIENZA a.a. 2013-2014.