有前處理下最短路徑演算法之研究

淡江大學機構典藏 > 商管學院 > 資訊管理學系暨研究所 > 學位論文 > Item 987654321/34155

請使用永久網址來引用或連結此文件: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/34155

題名:	有前處理下最短路徑演算法之研究
其他題名:	Research on the shortest path algorithm with pre-processing
作者:	謝逢鳴;Hsieh, Feng-ming
貢獻者:	淡江大學資訊管理學系碩士班魏世杰;Wei, Shih-chieh
關鍵詞:	Dijkstra演算法;直線距離A;地標A;Dijkstra algorithm;Euclidean A;landmark-based A
日期:	2006
上傳時間:	2010-01-11 04:58:54 (UTC+8)
摘要:	最短路徑演算法的研究在計算機科學中已有相當長歷史，也常應用於智慧型運輸系統(ITS）、地理資訊系統(GIS）及機器人學等領域。近來，隨著科技進步，許多人都使用電子地圖來搜尋路徑。在路徑搜尋過程，除計算最短路徑的結果需正確外，如何讓電腦快速有效的完成搜尋也相當重要。在原始地圖資料中如不引入輔助資訊下，通常是透過改進搜尋演算法的資料結構來降低搜尋時間。但這種方法將面臨瓶頸，如要再改善搜尋時間則要有效提升搜尋效率。提升搜尋效率的方法可在搜尋過程中引入輔助資訊輔助搜尋。輔助資訊可分為兩種，一種是在搜尋過程中輔助刪除不必要展開邊的資訊，如Arc-flag、Arc-reach及Node-reach等，另一種則是輔助估計剩餘距離的資訊，如直線距離A及有向地標A等。本文所謂的前處理即是對原始地圖資訊作處理以得到輔助資訊。為了提升搜尋效率表現，本文首先提出區域間最短距離以輔助估計剩餘距離資訊。接著進一步在估計剩餘距離資訊上提出容錯之無向地標A。經實驗發現，無論在以距離為成本或以時間為成本之地圖資料中，在相同錯誤率下，無向地標A相較於直線距離A及有向地標A，皆能有效改善路徑搜尋時間與效率，且其誤差尚在可容忍範圍內。最後本文也試著在無向地標A基礎上，找出與各種輔助資訊之最佳組合。以上實驗均以台灣地圖或台北縣市地圖為準。 The research on the shortest path algorithm has quite a long history in computer science. It has also seen many applications in different fields such as intelligent transportation system (ITS), geographical information system (GIS) and robotics. Recently with the progress in technology, people began to use the electronic map in hand for path finding. To find the shortest path, precision, efficiency, and time are the three factors of concern. Under the premise of no pre-processing, traditional works focus on reduction of the search time by improving the heap data structure of the algorithm. But this kind of improvement soon faces a bottleneck. By allowing pre-processing to guide the search, recent works show that much gain in efficiency and time can be obtained. The pre-processing of the original map serves to provide two kinds of information. One relates to arcs that need not be expanded, e.g. the arc-flag method. The other relates to estimation of the remaining distance, e.g. the landmark-based distance estimation in A. This paper intends to evaluate their effectiveness. To have a good base for stacking the different pre-processing methods, the Dijkstra algorithm, the Euclidean A* and their bidirectional counterparts are compared. Only the Euclidean A* survived. Both bidirectional versions are dropped out due to poor time performance. Then based on the Euclidean A* and the directional landmark-based A, various combinations of pre-processing are tested which include the zone distance, the arc-flag, the arc-reach, and the node-reach methods. To further improve the gain in performance, an error-tolerant undirectional landmark-based A is proposed where a little tradeoff in precision is considered. The results show that under the same error rate, the undirectional landmark-based A* is better than the Euclidean A* and the directional landmark-based A* in terms of both time and efficiency. Finally based on the undirectional landmark-based A*, various combinations of pre-processing are also tested. For all the results, the experiments are carried out based on an electronic map of the Taiwan or a smaller part of it, the Taipei City and the Taipei County.
顯示於類別:	[資訊管理學系暨研究所] 學位論文

文件中的檔案:

檔案	大小	格式	瀏覽次數
	0Kb	Unknown	265	檢視/開啟

在機構典藏中所有的資料項目都受到原著作權保護.

TAIR相關文章

資料載入中.....