Intelligenza Artificiale
2013
Fulvio Valenza
Serena Spinoso


Il metodo di ricerca in profondità, come gli altri
metodi, partendo da un nodo iniziale costruisce un
grafo di ricerca, che è una porzione dello spazio degli
stati.
In particolare i metodi di ricerca in profondità
espandono per primo l’ultimo nodo generato,
utilizzando di fatto come uno stack la lista OPEN , che
contiene i nodi ancora da espandere.
Il giovane Dionisio è uno studente di Ingegneria
Informatica, che ha deciso di partecipare al progetto di
Erasmus in Romania. Atterrato all’aeroporto di Arad,
Dionisio deve raggiungere la città di Bucharest, meta
finale del suo viaggio.
Essendo un tipo molto temerario, il nostro studente ha
deciso di affrontare questo viaggio in macchina e senza
una carta stradale. Allora, da buon informatico,
Dionisio metterà in pratica ciò che ha appreso dal
corso di Intelligenza Artificiale e la strategia da lui
preferita sarà la Ricerca in Profondità.
Riuscirà ad arrivare …..?



Utilizzo di due liste
◦ Open=Lista dei nodi da esplorare
◦ Closed=Lista dei nodi esplorati
Azione
◦ Rimuovere il primo nodo n da Open
◦ Porlo in Closed
◦ Espandere n generando tutti i suoi successori e porli
all’inizio di open (ordine arbitrario)
Condizioni di Uscita
◦ Se uno dei successori è un nodo finale uscire con la
soluzione altrimenti rieseguire l’azione
◦ Se open è vuota torno fail
OPEN
CLOSED
Arad
OPEN
CLOSED
OPEN
CLOSED
Lugoj
Arad
Sibiu
Sibiu
Timisoara
Zerind
Zerind
Timisoara
Arad
ARAD
Sibiu
Timisoara
Lugoj
Zerid
OPEN
CLOSED
OPEN
CLOSED
OPEN
CLOSED
Mehadia
Arad
Dobreta
Arad
Craiova
Arad
Sibiu
Timisoara
Sibiu
Timisoara
Sibiu
Timisoara
Zerind
Lugoj
Zerind
Lugoj
Zerind
Lugoj
Mehadia
Mehadia
Mehadia
Dobreta
Craiova
Dobreta
OPEN
Pitesti
Rimnicu
Vilcea
Sibiu
Zerind
CLOSED
Arad
Timisoara
OPEN
CLOSED
Bucharest
Arad
Rimnicu
Vilcea
Timisoara
Sibiu
Lugoj
Zerind
Mehadia
Lugoj
Mehadia
Dobreta
Rimnicu
Vilcea
Pitesti
Dobreta
BUCHAREST
Craiova
Craiova
Pitesti
ARAD
Timisoara
Sibiu
Lugoj
Mehadia
Dobreta
Craiova
Pitesti
Bucharest
Rimnicu
Vilcea
Zerind

Backtracking cronologico

Hindsight backtracking

Leap-frogging

Hill-climbing

Algoritmo ricorsivo
◦ Chiamo ricorsivamente la funzione BT( [stati] )

Condizioni di Uscita
◦ if goal(stato) -> return [ ]
◦ if deadend(stato) ->fail
◦ if length([stati])>Soglia -> fail

Azione
◦
◦
◦
◦
Rimuovere il primo nodo stato da Open
Calcolo un suo nuovo figlio = nuovoStato
Aggiungo nuovoStato a [stati]
Richiamo BT([stati])
Soglia=5
BT(Arad)
BT(Timisoara,Arad)
BT(Lugoj,Timisoara,Arad)
BT(Mehadia,Lugoj,Timisoara,
Arad)
BT(Dobreta,Mehadia,Lugo
j,Timisoara,Arad)
BT(Craiova,Dobreta,Meha
dia,Lugoj,Timisoara,Arad)
BT(Pitesti,Craiova,Dobreta,
Mehadia,Lugoj,Timisoara,Ar
ad)
Soglia=5
BT(Arad)
BT(Timisoara,Arad)
BT(Lugoj,Timisoara,Arad)
BT(Mehadia,Lugoj,Timisoara,
Arad)
BT(Dobreta,Mehadia,Lugoj
,Timisoara,Arad)
BT(Craiova,Dobreta,Meha
dia,Lugoj,Timisoara,Arad)
BT(Rimincu
Vilcea,Craiova,Dobreta,Meh
adia,Lugoj,Timisoara,Arad)
Soglia=5
BT(Arad)
BT(Sibiu,Arad)
BT(Fagaras,Sibiu,Arad)
BT(Bucharest,Fagaras,Sibiu,Arad)

Backtracking cronologico

Hindsight backtracking

Leap-frogging

Hill-climbing



Utilizzo di due liste
◦ Open=Lista dei nodi da esplorare
◦ Progeny=Lista dei nodi generati
Azione
◦ Rimuovere il primo nodo x da Open e generare un suo
successore n e, se questo non è presente in Progeny ,
inserirlo.
◦ Se x non non può generare figli, eliminarlo da Open e fare
una ricerca in Open dei nodi sovversivi.
◦ Se n non è renegade, ricorrente o insipid, allora inserirlo alla
cima di Open.
Condizioni di Uscita
◦ Se uno dei successori è un nodo finale uscire con la
soluzione altrimenti rieseguire l’azione
◦ Se open è vuota torno fail
Passo1
Passo2
Passo3
Passo4
Passo5
Passo6
Soglia=418
•O[Arad]
•P[ ]
•O[Arad,Timisoara]
•P[Timisoara]
•O[Arad,Timisoara,Lugoj]
•P[Timisoara,Lugoj]
•O[Arad,Timisoara,Lugoj,Mehadia]
•P[Timisoara,Lugoj,Mehadia]
•O[Arad,Timisoara,Lugoj,Mehadia]
•P[Timisoara,Lugoj,Mehadia,Dobreta]
•O[Arad,Timisoara,Lugoj,Mehadia,Dobreta]
•P[Timisoara,Lugoj,Mehadia,Dobreta,Craiova]
Insipid->Arad-Craiova 494
Non ha più figli
Passo7
Passo8
Passo9
• O[Arad,Timisoara,Lugoj,Mehadia,Dobreta]
• P[Timisoara,Lugoj,Mehadia,Dobreta,Craiova]
• O[Arad]
• P[Timisoara,Lugoj,Mehadia,Dobreta,Craiova]
Sovversivo
• O[Arad,Sibiu]
• P[Timisoara,Lugoj,Mehadia,Dobreta,Sibiu,Craiova]
• O[Arad,Sibiu,Rimincu Vilcea]
Passo11
• P[Timisoara,Lugoj,Mehadia,Dobreta,Craiova,Sibiu,Rimincu
Vilcea]
• O[Arad,Sibiu,Rimincu Vilcea,Pitesti]
Passo13
• P[Timisoara,Lugoj,Mehadia,Dobreta,Craiova,Sibiu,Rimincu
Vilcea,Pitesti]
• O[Arad,Sibiu,Rimincu Vilcea,Pitesti]
Passo14
• P[Timisoara,Lugoj,Mehadia,Dobreta,Craiova,Sibiu,Rimincu
Vilcea,Pitesti,Bucharest]
Goal

Backtracking cronologico

Hindsight backtracking

Leap-frogging
 Cronologico
 Hindsight

Hill-climbing


Principio base
◦ Di ciascuno nodo espanso si generano tutti i figli
◦ Si sceglie un solo figlio e lo si espande
◦ Quando si trova un percorso barricato in xn, si salta
ad uno dei fratelli
Metodi di salto
◦ Cronologico: per individuare il fratello a cui saltare si
scandiscono i nodi del percorso barricato a ritroso,
fino a che non si trova un nodo che ha un fratello non
ancora attraversato
◦ Hindsight: cercare il nodo sovversivo x e ripartire da
questo
Soglia=4
ARAD
Sibiu
Timisoara
Lugoj
Mehadia
Fagaras
Bucharest
Dobreta
Craiova
Insipid
Oradea
Zerind
Rimnicu
Vilcea
Sovversivo
Sibiu 140
Timisoara 118
Lugoj 229
Mehadia 299
Fagaras 239
Bucharest 450
Dobreta 374
Craiova 494
Soglia=418
ARAD
Insipid
Oradea 291
Zerind 75
Rimnicu
Vilcea 220

Backtracking cronologico

Hindsight backtracking


Leap-frogging
 Cronologico
 Hindsight
Hill-climbing

Principio base
ARAD
◦ Si sceglie il figlio
più promettente e
lo si espande
◦ Valore di ‘‘bontà’’
utilizziamo la
distanza da Arad
Timisoara
118
Sibiu140
Lugoj 111
Mehadia 70
Dobreta 75
Craiova 120
Pitesti138
Rimnicu
Vilcea 97
Rimnicu
Vilcea 146
Bucharest 101
Zerind 75
Oradea 71
Sibiu 151