Politecnico di TorinoINTELLIGENZA ARTIFICIALE 2012

Esempio: visita in profondità

Carlo Pronecarlo.prone@studenti.polito.it

Problema: da Arad a Bucarest

Problema• Trovare un percorso dalla

città di Arad alla città di Bucarest sul grafo appena visto

Metodo risolutivo• 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

• OPEN:– Arad

Arad0

Zerind75

Sibiu140

Timisoara118

• CLOSED:(empty)

Step 1

• OPEN:– Zerind– Timisoara– Sibiu

Arad0

Zerind75

Sibiu140

Timisoara118

• CLOSED:– Arad

Step 2

• OPEN:– Oradea– Timisoara– Sibiu

Zerind

Oradea

• CLOSED:– Arad– Zerind

Step 3

ATTENZIONE:nodo Sibiu già presente in OPEN, nessun nodo

successore da etichettare BACKTRACK

Oradea

Sibiu

Step 3

• OPEN:– Timisoara– Sibiu

Oradea

Sibiu

• CLOSED:– Arad– Zerind– Oradea

Step 4

• OPEN:– Lugoj– Sibiu

Timisoara

Lugoj

• CLOSED:– Arad– Zerind– Oradea– Timisoara

Step 5

• OPEN:– Mehadia– Sibiu

Lugoj

Mehadia

• CLOSED:– Arad– Zerind– Oradea– Timisoara– Lugoj

Step 6

• OPEN:– Dobreta– Sibiu

Mehadia

Dobreta

• CLOSED:– Arad – Mehadia– Zerind– Oradea– Timisoara– Lugoj

Step 7

• OPEN:– Craiova– Sibiu

Dobreta

Craiova

• CLOSED:– Arad – Mehadia– Zerind – Dobreta– Oradea– Timisoara– Lugoj

Step 8

• OPEN:– Pitesti– Rimnicu Vilcea– Sibiu

Craiova

Pitesti Rimnicu Vilcea

• CLOSED:– Arad – Mehadia– Zerind – Dobreta– Oradea– Craiova– Timisoara– Lugoj

Step 9

• OPEN:– Bucharest– Rimnicu Vilcea– Sibiu

Pitesti

Bucharest Rimnicu Vilcea

• CLOSED:– Arad – Mehadia– Zerind – Dobreta– Oradea– Craiova– Timisoara– Lugoj – Pitesti

Albero finaleArad

0

Zerind75

Oradea71

Timisoara118

Lugoj111

Mehadia70

Dobreta75

Craiova120

Pitesti138

Bucharest101

Rimnicu Vilcea

146

Sibiu140

Percorso finaleArad

0

Zerind75

Oradea71

Timisoara118

Lugoj111

Mehadia70

Dobreta75

Craiova120

Pitesti138

Bucharest101

Rimnicu Vilcea

146

Sibiu140

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)