Torna alla Home Page del corso
Torna alla pagina degli Elaborati
Successiva
|
|
|
|
|
|
|
|
|
|
|
|
|
COS'E' IL BACKTRACKING?
Il backtracking è una tecnica, utilizzata nei problemi di ricerca,
che permette di ripercorrere al contrario i rami di un albero di ricerca
e quindi di visitare nodi già visitati in precedenza. Questo può
essere molto utile nel caso in cui si verifichi un "vicolo cieco", cioè
ogni volta in cui ci si accorge che la strada intrapresa nell’albero di
ricerca non può portare ad alcuna soluzione.
A CHE PROBLEMI SI APPLICA IL BACKTRACKING?
Il backtracking può essere applicato in molti settori diversi
dell’Intelligenza Artificiale; in particolar modo:
TIPI DI BACKTRACKING
I possibili tipi di backtracking sono molti, con funzionamento diverso,
caratteristiche diverse e vantaggi diversi. In questo nostro elaborato
ci siamo concentrati in particolar modo sul funzionamento di
5 tipi di backtracking:
ELABORATO
Il nostro elaborato
è basato in buona parte sull’articolo "A
Theoretical Evaluation of Selected Backtracking Algorithms"
dei Prof. Grzegorz Kondrak e Peter van Beek del Dipartimento di Computer
Science dell’Università di Alberta (Canada). Dopo aver definito
il CSP e questi 5 tipi di backtracking, si è potuta ottenere una
gerarchia che consente di stabilire quali siano gli algoritmi migliori
relativamente al numero di nodi visitati nell’albero di ricerca e del numero
di controlli di consistenza effettuati. Infine, utilizzando le
librerie in linguaggio C ideate dal Prof. van Beek, abbiamo
sviluppato un semplice programma
di valutazione, con il quale abbiamo potuto verificare sperimentalmente
la correttezza delle gerarchie ottenute e dedurre ulteriori considerazioni
sull’efficienza degli algoritmi.