標題: 導航系統路徑搜尋之研究
On the Routing Problems of Navigation System
作者: 林志晏
Lin, Jhih-Yan
蔡鍚鈞
Tsai, Shi-Chun
資訊科學與工程研究所
關鍵字: 最短路徑問題;資料結構;導航系統;大眾運輸;Shortest Path Problem;Data Structure;Navigation System;Public Transportation System.
公開日期: 2008
摘要: 路徑規劃問題是這幾年來被廣泛地討論的一個問題,有許多基於Dijkstra演算法的方法已被一一提出;其中優先權佇列是在 Dijkstra演算法的計算上非常重要的一個資料結構。我們針對一般平面道路圖來加以觀察,發現一般平面道路圖的節點分支度是相當地低。根據此特性我們提出一個 Lazy Heap 的資料結構。跟傳統常使用的 Binary Heap來做比較,我們的方法能夠改進效能 30%至50%。除此之外,我們針對台北大眾運輸系統,提出圖的模型和路徑規劃的系統架構;在基於不同使用者的偏好之下,我們設計不同評斷路徑好壞的方法。我們也嚐試許多不同的參數組合,來討論路徑規劃結果和運算效能上的改進的議題。
The shortest path problem has been studied for decades, and many efficient algorithms based on Dijkstra's algorithm have been developed. In this thesis, we focus on the road network graphs. Priority queue is an important data structure used in Dijkstra's algorithm. Since the road netwrok graph has low degree, we propose a lazy binary heap as the priority queue. According to our experiments, we reduce 30% to 50% running time on this kind of sparse graphs. Moreover, our implementation has better space efficiency than standard binary heap. Based on the road network, we also study the public transportation system of Taipei City. In this work, we first model it as a graph, then propose a system architecture. Because of the preference of different users, we design different metric functions for different preference. In our experiments, we have tried different metrics and parameters setting.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079655502
http://hdl.handle.net/11536/43304
顯示於類別:畢業論文


文件中的檔案:

  1. 550201.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。