English  |  正體中文  |  简体中文  |  全文笔数/总笔数 : 56821/90555 (63%)
造访人次 : 12169049      在线人数 : 66
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU Library IR team.
搜寻范围 查询小技巧:
  • 您可在西文检索词汇前后加上"双引号",以获取较精准的检索结果
  • 若欲以作者姓名搜寻,建议至进阶搜寻限定作者字段,可获得较完整数据
  • 进阶搜寻


    jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://tkuir.lib.tku.edu.tw:8080/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.
    显示于类别:[資訊管理學系暨研究所] 學位論文

    文件中的档案:

    档案 大小格式浏览次数
    0KbUnknown233检视/开启

    在機構典藏中所有的数据项都受到原著作权保护.

    TAIR相关文章

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