Intelligenza Artificiale 1
Gestione della conoscenza
lezione 5
Prof. M.T. PAZIENZA
a.a. 2000-2001
Strategia di ricerca
Criteri di valutazione della strategia :
• Completezza (se esiste una soluzione viene
trovata sempre)
• Complessità temporale
• Complessità spaziale
• Ottimalità
Strategie di ricerca
1. Ricerca non informata ( o cieca)
Non si ha alcuna informazione sul numero di
passi o sul costo di cammino dallo stato
attuale all’obiettivo
1. Ricerca informata ( euristica)
Si hanno informazioni di preferenze tra gli stati
Ricerca informata più efficace di quella non
informata
Ricerca in ampiezza
• Tutti i nodi di profondità d nell’albero si
espandono prima dei nodi di profondità d+1
• Strategia sistematica (esaminati prima i
cammini di lunghezza i, poi i+1,poi i+2,…)
Ricerca in ampiezza
Se esiste una sola soluzione, la ricerca in
ampiezza la trova
Se esistono più soluzioni, viene trovato per
prima lo stato obiettivo più alto (quindi a
costo minimo)
Valutazione: ricerca completa ed ottimale
Ricerca in ampiezza
Se fattore di ramificazione = b
al livello i si avrà ramificazione = b i
Se la soluzione si trova dopo un cammino di
lunghezza d, il numero massimo (soluzione
peggiore) di nodi espansi è
1  b  b  b  ...  (b  1)  O(b )
2
3
d
d
(l’obiettivo non viene espanso)
Ricerca in ampiezza
Complessità spaziale coincide con complessità
temporale perché tutti i nodi foglia dell’albero
di ricerca devono essere mantenuti in memoria
contemporaneamente
Ricerca a costo uniforme
La ricerca a costo uniforme trova gli obiettivi più
superficiali.
Modifica la strategia in ampiezza espandendo
sempre il nodo sul confine con il costo più basso
(misurato con il costo del cammino g(n)),
invece del nodo di profondità minima
La prima soluzione trovata è quella più
conveniente
Ricerca a costo uniforme
• Si trova sempre la soluzione più economica
se si verifica che il costo del cammino non
decresce mai quando lo percorriamo.
g ( Successore (n))  g (n)
• Il costo del cammino di un nodo è somma
dei costi degli operatori che determinano il
cammino
Ricerca a costo uniforme
Ricerca in profondità
• La ricerca in profondità espande sempre il
primo dei nodi al livello più profondo
dell’albero.
• La ricerca torna indietro ed espande nodi a
livelli più superficiali solo quando arriva ad
un nodo foglia non obiettivo.
• La funzione di ricerca userà un meccanismo
di inserimento in un pila
Ricerca in profondità
Ricerca in profondità
• Occupazione di memoria modesta (memorizza un
solo cammino dalla radice al nodo foglia, oltre ai
nodi fratelli di ciascun nodo del cammino che
rimangono non espansi)
• Con uno spazio degli stati con fattore di
ramificazione b e profondità massima m, la ricerca
in profondità memorizza bm nodi
• Complessità temporale della ricerca in profondità
è O(b m )
• La ricerca in profondità può rimanere bloccata in
un cammino sbagliato di lunghezza infinita.
• Valutazione: né completa, né ottimale
Ricerca bidirezionale
La ricerca bidirezionale ricerca contemporaneamente
sia in avanti, dallo stato iniziale, sia all’indietro,
dall’obiettivo, fermandosi quando le due ricerche
si incontrano.
Con fattore di ramificazione pari a b in entrambe le
direzioni e soluzione a profondità d, allora la
soluzione verrà trovata in O(2b d / 2 )  O(b d / 2 )
Ricerca bidirezionale
Ricerca bidirezionale
• Problemi:
• Definire predecessori di un nodo n (quei
nodi che abbiano n come successore)
• Gli operatori in genere non sono reversibili,
per cui il calcolo dei predecessori in genere
risulta complesso.
• Cosa succede quando si hanno più stati
obiettivo?
Ripetizioni di stati
• Si possono semplificare alberi di ricerca
infiniti dovuti a ripetizioni di stati,
generando solo la porzione di albero che
ricopre il grafo dello spazio degli stati.
• Evitare riduzioni di stati può generare una
riduzione esponenziale del costo di ricerca.
Ripetizioni di stati
Suggerimenti:
• Non ritornare allo stato da cui si proviene
• Non creare cammini che abbiano cicli
• Non generare alcuno stato già generato
prima