Un algoritmo efficiente di cammino minimo per sistemi informativi territoriali

L'anteprima di questa tesi è scaricabile in PDF gratuitamente.
Per scaricare il file PDF è necessario essere iscritto a Tesionline.
L'iscrizione non comporta alcun costo. Mostra/Nascondi contenuto.

____________________________________________________________________ _________________________________________________________________ 7 una solida base teorica, che hanno prodotto i risultati desiderati in termini di performance. La strategia si basa su un approccio euristico, cioè vengono sfruttate le informazioni contenute implicitamente nella rete per migliorare la qualità dei dati di input e, di conseguenza, ottenere una soluzione in minor tempo investigando solo una piccola parte della rete stradale. L’algoritmo è stato implementato mediante linguaggio di programmazione Java ed è stato testato sulla rete stradale del territorio italiano. Sono stati effettuati dei test su percorsi stradali di lunghezza diversa e le prestazioni sono state confrontate con quelle degli altri algoritmi descritti. Dall’analisi dei risultati è risultata evidente la maggiore efficienza dell’esecuzione del nostro algoritmo. Nel Capitolo 1 verrà introdotto il concetto di sistema informativo territoriale, il GIS (Geographical Information System), che rappresenta il framework del nostro lavoro e saranno analizzate le mappe utilizzate per l’esecuzione degli algoritmi. Nel Capitolo 2 sarà descritto il problema generale del cammino minimo e saranno richiamati i concetti basilari di teoria dei grafi, lo strumento matematico utile ad analizzare e formulare il problema. La letteratura presente e gli algoritmi classici sviluppati per risolvere il problema, saranno introdotti nel Capitolo 3, dove descriveremo le seguenti tecniche: Dijkstra, Dijkstra bidirezionale, A* e A* bidirezionale. Saranno, poi, studiate le strutture dati utilizzate nell’implementazione degli algoritmi. Nel Capitolo 4 sarà presentato il nuovo algoritmo introdotto in questa tesi, identificato nel corso del lavoro con Soglia*, con la descrizione dell’idea base e delle tecniche utilizzate per la su implementazione. Saranno presentate e dimostrate alcune proprietà delle funzioni euristiche di stima usate dall’algoritmo e discuteremo teoricamente i vantaggi in termini di efficienza forniti dall’algoritmo rispetto alle altre tecniche. Nel Capitolo 5 saranno esposti i risultati dei test effettuati per l’algoritmo Soglia* sulle mappe a disposizione, e confrontati con le prestazioni degli altri algoritmi descritti. Le simulazioni sono state condotte considerando due funzioni obiettivo, la distanza e il tempo, e i risultati analizzati in termini di tempo di esecuzione dell’algoritmo e di vastità dell’area visitata. Nel Capitolo 6 saranno esposte le conclusioni sul lavoro svolto e gli sviluppi futuri ipotizzati.

Anteprima della Tesi di Giancarlo Volpe

Anteprima della tesi: Un algoritmo efficiente di cammino minimo per sistemi informativi territoriali, Pagina 2

Laurea liv.II (specialistica)

Facoltà: Ingegneria

Autore: Giancarlo Volpe Contatta »

Composta da 121 pagine.

 

Questa tesi ha raggiunto 1089 click dal 01/04/2010.

 

Consultata integralmente una volta.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.