/ 1
- Dettagli
- Categoria: Area Scientifica
- Scritto da Fabrizio Battaglia
- Visite: 1378
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.