Dipartimento di Ingegneria dell’Informazione
Università degli Studi di Parma
Intelligenza Artificiale
Risoluzione dei Problemi
Agostino Poggi
Stefano Cagnoni
Risoluzione di Problemi
 Un problema è definito da un goal e dall’insieme di strumenti a
disposizione per raggiungerlo.
 La prima fase della risoluzione di un problema è la
formulazione del problema.
 In questa fase, oltre a dare una buona definizione del goal,
bisogna decidere quali sono le azioni, quale è lo spazio degli
stati e quale è lo stato da cui si parte (stato iniziale).
 E’ essenziale scegliere delle azioni, e quindi degli stati, che
permettano di formulare soluzioni al giusto livello di dettaglio.
Risoluzione dei Problemi
2
Risoluzione di Problemi
 A partire dallo stato iniziale bisogna trovare una sequenza di azioni, detta
soluzione, che soddisfi il goal del problema.
 L’esecuzione di ogni azione ha un costo, che può variare da azione ad
azione, che costituisce il criterio utilizzato nella ricerca della soluzione
migliore.
 Quindi, ad ogni sequenza di azioni è possibile assegnare un costo
complessivo (somma dei costi associati alle varie azioni), per valutare
quale sia la soluzione migliore.
 La scelta della sequenza corrisponde alla seconda fase della risoluzione di
un problema e viene individuata con il nome di ricerca.
 Infine, trovata la soluzione, nella terza fase, detta di esecuzione, le azioni
sono eseguite per raggiungere il goal.
Risoluzione dei Problemi
3
Classi di Problemi
 I problemi possono essere divisi in quattro classi in dipendenza della
conoscenza che si ha sullo stato del mondo e sulle azioni che si possono
eseguire su di esso:
 Problemi a stato singolo (single-state problems) : si ha conoscenza dello stato del
mondo e degli effetti delle azioni.
 Problemi a stato multiplo (multiple-state problems) : si ha conoscenza completa
degli effetti delle azioni, ma non dello stato del mondo.
 Problemi con imprevisti (contingency problems): alcune azioni possono avere
effetti non del tutto determinati (incertezza, malfunzionamenti ecc.). Spesso per la
soluzione è necessario agire (e verificare l’effetto della propria azione) prima di
avere trovato una soluzione.
 Problemi di esplorazione (exploration problems) : non si ha conoscenza né sullo
stato del mondo né sugli effetti delle azioni. E’ necessario apprendere i possibili stati
del mondo e gli effetti delle proprie azioni attraverso l’esperienza.
Risoluzione dei Problemi
4
Esempi di Problemi
 Problemi giocattolo (modelli semplificati di classi di problemi reali):
 Il problema dell’8-puzzle (versione ridotta del gioco del 15)
 Il problema delle 8 regine (disporre 8 regine su una scacchiera in modo che nessuna
dia scacco alle altre)
 Il problema della cripto-aritmetica (GATTO - CANE = TOPO)
 Il problema dei tre missionari e dei tre cannibali
(trasportare 3 m. e 3 c. da un lato a un altro di un fiume con una barca a due posti in modo tale
che sulle 2 rive non ci siano mai c. in sovrannumero rispetto ai m.)
 Problemi reali
 Il calcolo di un percorso su un grafo
 Il problema del commesso viaggiatore
(date n città, trovare il percorso più breve che passa una e una sola volta per ciascuna di esse)
 Il disegno di un layout VLSI
 La navigazione di robot
 Il calcolo di una sequenza di assemblaggio
Risoluzione dei Problemi
5
Algoritmo Generale
 Cerchiamo di definire un algoritmo generale di ricerca per il caso di
problemi a stato singolo.
 Per semplificare la sua definizione, introduciamo alcune funzioni
ausiliarie.
 Occorre definire il tipo di dato Problem
Datatype Problem
Components: Initial-State,
Operators, Goal-Test, Path-Cost-Function
 Occorre una funzione per ricavare lo stato iniziale dalla descrizione del
problema:
 Init-State(Problem)
 Occorre una funzione per trasformare una descrizione di stato nel nodo di
un albero:
 Make-Node(State)
Risoluzione dei Problemi
6
Algoritmo generale
 Occorre definire il tipo di dato Node
Datatype Node
Components: State,
Parent-Node, Operator, Depth, Path-Cost
 Occorre una funzione per espandere un nodo:
 Expand(Node, Problem, [Depth ]), genera i successori del nodo se non è stata
raggiunta la profondità Depth.
 Servono 4 funzioni per gestire delle code di nodi:




Make-Queue(Elements), genera una coda contenente Elements;
Empty(Queue), controlla se la coda è vuota;
Remove-Front(Queue), estrae il primo elemento;
Queueing-Fn(Queue, Elements), inserisce Elements nella coda.
 Infine serve una funzione per controllare se il nodo coincide con un goal
del problema:
 Goal(Node, Problem)
Risoluzione dei Problemi
7
Algoritmo Generale
 Possiamo definire un algoritmo generale per la ricerca su alberi come
segue:
function General-Search(problem, Queueing-Fn, [ Depth ]) {
nodes = Make-Queue(Make-Node(Initial-State(problem)));
while true {
if Empty(nodes) return failure;
node =Remove-Front(nodes);
if Goal(State(node), problem) return node;
nodes = Queueing-Fn(nodes, Expand(node, problem, Depth));
}
 L’insieme di nodi contenuti in nodes è detta frontiera dell’albero di
ricerca.
Risoluzione dei Problemi
8
Valutazione delle strategie di ricerca
 Completezza : l’algoritmo garantisce di trovare una soluzione,
se questa esiste ?
 Complessità temporale : quanto tempo è necessario per
raggiungerla ?
 Complessità spaziale : quanta memoria è richiesta per
raggiungerla ?
 Ottimalità : la soluzione trovata è la migliore ?
Risoluzione dei Problemi
9
Ricerca in Ampiezza
(Breadth-First Search)
 Un algoritmo di ricerca in ampiezza garantisce che ogni nodo
di profondità d sia espanso prima di qualsiasi altro nodo di
profondità maggiore.
 Possiamo definire un algoritmo di ricerca in ampiezza come
segue:
function Breadth-First-Search(problem) {
return General-Search(problem, Enqueue-At-End);
}
Risoluzione dei Problemi
10
Ricerca in Ampiezza
 Ottimalità: è ottimo quando
 il costo è una funzione non decrescente della profondità del nodo;
 il costo è lo stesso per ciascun operatore.
 Completezza: è completo visto che utilizza una strategia
sistematica che considera prima le soluzioni di lunghezza 1, poi
quelle di lunghezza 2 e così via.
 Complessità: Se b è il fattore di ramificazione e d la profondità
della soluzione, allora il numero massimo di nodi espansi è:
1 + b + b2 + b3 + ... + bd
 Complessità temporale: bd
 Complessità spaziale: bd
Risoluzione dei Problemi
11
Ricerca in Ampiezza
 Se b =10 e per ogni nodo sono richiesti un tempo di
elaborazione di 1 millisecondo e un’occupazione di memoria di
100 byte avremo i seguenti valori:

Profondità
Nodi
Tempo
Memoria
0
2
4
6
8
10
12
14
1
111
11111
106
108
1010
1012
1014
1 millisec
100 millisec
11 secondi
18 minuti
31 ore
128 giorni
35 anni
3500 anni
100 byte
11 kilobyte
1 Megabyte
111 Megabyte
11 Gigabyte
1 Terabyte
111 Terabyte
11111 Terabyte
(la cosiddetta “Curse of Dimensionality”!)
Risoluzione dei Problemi
12