Risoluzione di problemi e ricerca

Risoluzione di problemi e

ricerca

Risoluzione di problemi

Un semplice agente risolutore di problemi

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

Risoluzione di problemi

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 Azioni: destra, sinistra, aspira

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.

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

Risoluzione di problemi

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.

Il problema delle 8 regine

Risoluzione di problemi

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.

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.

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.

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

Risoluzione di problemi

Albero di ricerca parziale per trovare un

itinerario da Arad a Bucarest.

Risoluzione di problemi

L’algoritmo generale di ricerca

Risoluzione di problemi L’algoritmo generale di ricerca

Tramite l’argomento Queuing-Fn viene passata una

funzione per accodare i nodi ottenuti dall’espansione

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

Risoluzione di problemi

Ricerca in ampiezza

QueueingFn = metti i successori alla fine della coda

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)

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.

Risoluzione di problemi

Ricerca a costo uniforme

ciascun nodo è etichettato con il costo g(n)

QueueingFn = inserisci i successori in ordine di

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.

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

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.

Risoluzione di problemi

Ricerca con approfondimento iterativo

Risoluzione di problemi

Ricerca con approfondimento iterativo

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)

Risoluzione di problemi

Ricerca bidirezionale

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

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.

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)

Risoluzione di problemi

Una realizzazione della ricerca best-first che usa l’algoritmo

di ricerca generale e la funzione di valutazione EvalFn

Risoluzione di problemi

Mappa della Romania con distanze stradali e distanze in linea

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

Risoluzione di problemi

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)

Risoluzione di problemi

Stadi di una ricerca A* per Bucarest usando come funzione di valutazione

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.

Risoluzione di problemi Funzioni euristiche

E’possibile definire differenti funzioni euristiche. Ad esempio:

h

= numero di tessere che sono fuori posto (h

= 7)

h

= la somma delle distanze dalle posizioni che le tessere devono assumere

nella configurazione obiettivo. La distanza è una somma delle distanze

Risoluzione di problemi

Confronto fra la ricerca ad approfondimento iterativo

e l’algoritmo A* con h

e h