Politecnico di Torino
INTELLIGENZA ARTIFICIALE 2012
Esempio: visita in profondità
Carlo Prone
[email protected]
Problema: da Arad a Bucarest
Problema
Metodo risolutivo
• Trovare un percorso dalla
città di Arad alla città di
Bucarest sul grafo appena
visto
• Visita in profondità del grafo
Visita in profondità – in breve
• Si visita il primo nodo di una lista di OPEN
• Tutti i suoi figli non ancora etichettati vengono
segnati OPEN e inseriti IN TESTA ALLA LISTA
con ordine arbitrario
• Il nodo diventa CLOSED
• Primo passo: il nodo di partenza (radice
dell’albero) in OPEN
Visita in profondità – in breve
• Terminazione:
– nodo goal raggiunto (successo)
– OPEN vuota (fallimento)
• Possibile introdurre un limite di profondità:
se il nodo attuale ha una distanza maggiore o uguale a
un limite fissato e non è soluzione NON proseguo
l’esplorazione sui suoi discendenti, ma altrove
(BACKTRACKING)
– non si hanno garanzie di trovare soluzione, se esiste
– non adottato in questo esempio
Visita in profondità – in breve
• Stesso procedimento di una visita in ampiezza
ma utilizzando una STACK (LIFO) piuttosto che
una QUEUE (FIFO) per i nodi OPEN
• Si scende sull’albero piuttosto che esplorare
esaustivamente un livello
• Inserimento dei nodi figli in OPEN con ordine
ARBITRARIO
– approccio greedy: figli con costo minore
Step 0
Arad
0
Zerind
Sibiu
75
• OPEN:
– Arad
Timisoara
140
• CLOSED:
(empty)
118
Step 1
Arad
0
Zerind
Sibiu
75
• OPEN:
– Zerind
– Timisoara
– Sibiu
Timisoara
140
• CLOSED:
– Arad
118
Step 2
Zerind
75
Oradea
71
• OPEN:
– Oradea
– Timisoara
– Sibiu
• CLOSED:
– Arad
– Zerind
Step 3
Oradea
146
Sibiu
151
ATTENZIONE:
nodo Sibiu già presente in OPEN, nessun nodo
successore da etichettare
⇒ BACKTRACK
Step 3
Oradea
146
Sibiu
151
• OPEN:
– Timisoara
– Sibiu
• CLOSED:
– Arad
– Zerind
– Oradea
Step 4
Timisoara
118
Lugoj
111
• OPEN:
– Lugoj
– Sibiu
• CLOSED:
–
–
–
–
Arad
Zerind
Oradea
Timisoara
Step 5
Lugoj
229
Mehadia
70
• OPEN:
– Mehadia
– Sibiu
• CLOSED:
–
–
–
–
–
Arad
Zerind
Oradea
Timisoara
Lugoj
Step 6
Mehadia
299
Dobreta
75
• OPEN:
– Dobreta
– Sibiu
• CLOSED:
–
–
–
–
–
Arad
– Mehadia
Zerind
Oradea
Timisoara
Lugoj
Step 7
Dobreta
374
Craiova
120
• OPEN:
– Craiova
– Sibiu
• CLOSED:
–
–
–
–
–
Arad
– Mehadia
Zerind – Dobreta
Oradea
Timisoara
Lugoj
Step 8
Craiova
494
Rimnicu
Vilcea
• OPEN:
– Pitesti
– Rimnicu Vilcea
– Sibiu
Pitesti
146
138
• CLOSED:
–
–
–
–
–
Arad
– Mehadia
Zerind – Dobreta
Oradea – Craiova
Timisoara
Lugoj
Step 9
Pitesti
632
Rimnicu
Vilcea
• OPEN:
– Bucharest
– Rimnicu Vilcea
– Sibiu
Bucharest
97
101
• CLOSED:
–
–
–
–
–
Arad
– Mehadia
Zerind – Dobreta
Oradea – Craiova
Timisoara
Lugoj
– Pitesti
Albero finale
Arad
0
Zerind
Timisoara
75
Sibiu
118
Oradea
140
Lugoj
71
111
Mehadia
70
Dobreta
75
Craiova
120
Pitesti
138
Bucharest
101
Rimnicu
Vilcea
146
Percorso finale
Arad
0
Zerind
Timisoara
75
Sibiu
118
Oradea
140
Lugoj
71
111
Mehadia
70
Dobreta
75
Craiova
120
Pitesti
138
Bucharest
101
Rimnicu
Vilcea
146
Soluzione trovata NON ottima
Costo percorso finale
• Arad 0
• Timisoara 118
• Lugoj 111
• Mehadia 70
• Dobreta 75
• Craiova 120
• Pitesti 138
• Bucharest 101
TOTALE 733
Costo percorso ottimo
• Arad 0
• Sibiu 140
• Rimnicu Vilcea 80
• Pitesti 97
• Bucharest 101
TOTALE 418
Considerazioni finali
• Trovata una soluzione (SUCCESSO)
• Non necessariamente percorso migliore
(soluzione NON OTTIMA)
• Implementazione diversa avrebbe potuto dare:
– diversa ottimalità della soluzione
– un altro albero esplorato
– tempo d’esecuzione differente
⇒ ALGORITMO NON DETERMINISTICO
(ex: no approccio greedy ma ordine casuale, o alfabetico
sul nome)
Euristiche
• È possibile introdurre delle valutazioni di tipo
euristico con l’intento di migliorare le
prestazioni dell’algoritmo
• Valutazione euristica dei nodi:
– espandere il figlio "più promettente" anziché uno
a caso
– abbandonare un nodo senza esplorare tutta la sua
discendenza e ripartire da un predecessore su un
altro figlio (leap-frogging)
Euristiche
• Possibili criteri euristici per valutare se un
nodo è subversive (ovvero non porterà mai a
una soluzione e non ha senso esplorarne la
discendenza)
– distanza finora compiuta maggiore del risultato
che mi aspetto
– direzione errata (so che devo andare verso sud, il
nodo è a nord, necessita di informazioni
aggiuntive)