Analisi delle performance degli algoritmi A* e Dijkstra bidirezionali nel problema del Route Planning

Saracchini, Tommaso (2020) Analisi delle performance degli algoritmi A* e Dijkstra bidirezionali nel problema del Route Planning. [Laurea magistrale], Università di Bologna, Corso di Studio in Matematica [LM-DM270]
Documenti full-text disponibili:
[thumbnail of Thesis] Documento PDF (Thesis)
Disponibile con Licenza: Salvo eventuali più ampie autorizzazioni dell'autore, la tesi può essere liberamente consultata e può essere effettuato il salvataggio e la stampa di una copia per fini strettamente personali di studio, di ricerca e di insegnamento, con espresso divieto di qualunque utilizzo direttamente o indirettamente commerciale. Ogni altro diritto sul materiale è riservato

Download (15MB)

Abstract

Questa tesi ha l'obiettivo di confrontare le performance degli algoritmi A star e bidirezionali per il problema del calcolo del cammino più breve attraverso una rete stradale. In particolare, l'analisi verte ad analizzare il numero di nodi visitati e il tempo di esecuzione degli algoritmi, su alcune mappe stradali europee morfologicamente diverse andando ad evidenziare pregi e difetti dei diversi approcci. I dati stradali sono stati ottenuti dal sito web OpenStreetMap.com, gli algoritmi presentati sono stati scritti in linguaggio Python.

Abstract
Tipologia del documento
Tesi di laurea (Laurea magistrale)
Autore della tesi
Saracchini, Tommaso
Relatore della tesi
Correlatore della tesi
Scuola
Corso di studio
Indirizzo
Curriculum C: Didattico
Ordinamento Cds
DM270
Parole chiave
teoria dei grafi cammino di costo minimo algoritmo A star Dijkstra Bidirezionale
Data di discussione della Tesi
27 Marzo 2020
URI

Altri metadati

Statistica sui download

Gestione del documento: Visualizza il documento

^