English  |  正體中文  |  简体中文  |  Items with full text/Total items : 55184/89457 (62%)
Visitors : 10677591      Online Users : 82
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version
    Please use this identifier to cite or link to this item: http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/23111

    Title: 在容錯下最短路徑演算法之研究
    Other Titles: The Error-Tolerant Shortest Path Algorithm
    The Error-Tolerant Shortest Path Algorithm
    Authors: 魏世杰;謝逢鳴
    Contributors: 淡江大學資訊管理學系
    Keywords: Dijkstra
    Date: 2006-06-07
    Issue Date: 2009-11-30 14:32:59 (UTC+8)
    Publisher: 聖約翰科技大學
    Abstract: 最短路徑演算法的研究在計算機科學中已有相當長歷史,也常應用於各種領域。在路徑搜尋過程,除計算最短路徑的結果需正確外,如何讓電腦快速有效的完成搜尋也相當重要。在原始地圖資料中如不引入輔助資訊下,通常是透過改進搜尋演算法的資料結構來降低搜尋時間。但這種方法將面臨瓶頸,如要再改善搜尋時間則要有效提升搜尋效率。提升搜尋效率的方法可在搜尋過程中引入輔助資訊輔助搜尋。在本文中所引入的輔助資訊為估計距離資訊,如座標估算法或地標估算法等。本文即是針對原始地圖資料進行必要的前處理,以得到所需的輔助資訊。然而,在引入輔助資訊後,雖然可以進一步改善搜尋時間與效率,但在改善到某一程度時也將會遇到瓶頸。故本文試著利用「容錯」的方式來將路徑搜尋效率與時間作進一步的改善。但在容錯下,搜尋時間、效率與錯誤率三者仍需要兼顧。因此我們提出無向地標A*。我們首先比較無輔助資訊的Dijkstra、座標估算法的直線距離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. To find a 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 gain in time and efficiency can be obtained. In this paper, pre-processing of the original map mainly serves to provide information which helps estimate the remaining distance. However current pre-processing also has a bottleneck. To further improve the gain in performance, an error-tolerant unidirectional 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. For all the results, the experiments are carried out based on an electronic map of the Taiwan Province or a smaller part of it, the Taipei City and the Taipei Country.
    Relation: 2006資訊管理技術與實務應用發展研討會論文集=Proceedings of 2006 Symposium on Application and Development of Management Information System,7頁
    Appears in Collections:[Graduate Institute & Department of Information Management] Proceeding

    Files in This Item:

    There are no files associated with this item.

    All items in 機構典藏 are protected by copyright, with all rights reserved.

    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library & TKU Library IR teams. Copyright ©   - Feedback