PubbliTesi è un archivio bibliografico e di diffusione delle Migliori Tesi di Laurea Specialistica e di Dottorato di Ricerca, presentate negli Atenei italiani, e delle Prove pratiche d’Esame di Laurea Specialistica svolte nella Scuole di Alta Formazione Musicale italiane, realizzato dal CNR e dall’Inforav, in collaborazione con le Università e con il patrocinio del MIUR (www.pubblitesi.it).

PubbliTesi - La Tesi
Instradamento su grafi dinamici di grandi dimensioni
Scheda Sintetica

Autore: Fabrizio Battaglia
Relatore: Camil Demetrescu
Università: Università degli Studi di Roma “La Sapienza”
Facoltà: Facoltà di Ingegneria
Corso: Laurea Spec. in Ingegneria Informatica
Data di Discussione: 28/05/2007
Voto: 105
Disciplina: Ingegneria degli Algoritmi
Tipo di Tesi: Sperimentale
Lingua: Italiano
Grande Area: Area Scientifica

Descrizione:
Nuovo algoritmo di calcolo dello shortest path in grafi dinamici, chiamato Euclidean. Si tratta di una versione di A* bidirezionale che sfrutta le coordinate geografiche per calcolare il lower bound delle distanze e quindi riordinare le code di priorità delle ricerche, sia in avanti che all’indietro. Esperimenti effettuati su rete stradale americana, confronto delle prestazioni con ALT con 2, 4, 8 e 16 landmark. Utilizzando Euclidean si ottine grande risparmio di memoria rispetto ad ALT, ottenendo prestazioni temporali simili ad ALT con 4/8 landmark.

Per ulteriori informazioni su questa e sulle altre Tesi Accededere all’Area Riservata o Registrarsi. grafi dinamici, roadnetwork, algoritmi dinamici, tiger, coordinate, Euclidean, A*, ALT, landmark, coordinate euclidee,