會議論文
| 學年 | 94 |
|---|---|
| 學期 | 2 |
| 發表日期 | 2006-05-27 |
| 作品名稱 | 有輔助資訊下最短路徑演算法之研究---以台灣地圖為例 |
| 作品名稱（其他語言） | |
| 著者 | 魏世杰;謝逢鳴 |
| 作品所屬單位 | 淡江大學資訊管理學系 |
| 出版者 | |
| 會議名稱 | 第十七屆國際資訊管理學術研討會=The 17th International Conference on Information Management |
| 會議地點 | 高雄, 臺灣 |
| 摘要 | 最短路徑演算法的研究在計算機科學中已有相當長歷史，也常應用於各種領域。在路徑搜尋過程，除計算最短路徑的結果需正確外，如何讓電腦快速有效的完成搜尋也相當重要。在原始地圖資料中如不引入輔助資訊下，通常是透過改進搜尋演算法的資料結構來降低搜尋時間。但這種方法將面臨瓶頸，如要再改善搜尋時間則要有效提升搜尋效率。提升搜尋效率的方法可在搜尋過程中引入輔助資訊輔助搜尋。輔助資訊可分為兩類，一類是估計距離資訊，如座標估算法或地標估算法等，另一類是刪除冗邊資訊，如Arc-flag、Arc-reach、Node-reach等。本文即是針對原始地圖資料進行必要的前處理，以得到所需的輔助資訊。本文先在估計距離資訊上提出區域間最短距離。為驗證各輔助資訊之效能，我們首先比較無輔助資訊的Dijkstra、座標估算法的直線距離A*及兩者在單向、雙向搜尋之表現。接下來在估計距離資訊與刪除冗邊資訊上我們找出最佳交叉組合。為了提升表現，本文進一步在估計距離資訊上提出容錯之無向地標A*。經實驗發現，在相同錯誤率下，無向地標A*相較於直線距離A*及有向地標A*，能有效改善路徑搜尋時間與效率。最後本文也試著在無向地標A*基礎上，找出與各種輔助資訊之最佳交叉組合。以上實驗結果皆以台灣省或台北縣市地圖為準。 |
| 關鍵字 | 直線距離 |
| 語言 | zh_TW |
| 收錄於 | |
| 會議性質 | 國際 |
| 校內研討會地點 | |
| 研討會時間 | 20060527~20060527 |
| 通訊作者 | |
| 國別 | TWN |
| 公開徵稿 | Y |
| 出版型式 | 紙本 |
| 出處 | 第十七屆國際資訊管理學術研討會論文集=Proceedings of the 17th International Conference on Information Management，8頁 |
| 相關連結 |
機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/95191 ) |