English  |  正體中文  |  简体中文  |  Items with full text/Total items : 54371/62179 (87%)
Visitors : 9052587      Online Users : 103
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTHU 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://nthur.lib.nthu.edu.tw/dspace/handle/987654321/86682


    Title: 尋找一條符合使用者需求的最短路徑
    Authors: 呂其錞
    Description: GH02101062642
    碩士
    資訊工程學系
    Date: 2014
    Keywords: 道路網絡;最短路徑;使用者需求
    road network;shortest;distance;path;user requirement
    Abstract: 在道路網絡上找尋最短路徑的問題已經被研究許多年,許多有效率的解決方法都已經被提出。從使用者角度而言,有時候使用者的需求不只單單是只從出發地到目的地這麼單純,使用者可能會一些其它的需求,例如到餐廳吃飯和去郵局寄信,因為使用者這些特殊的需求,使得那一些建立在傳統的最短路徑問題上的解決方法無法滿足使用者的需求。在此篇論文中,為了滿足使用者的需求,我們提出了三個主要的方法來解決包含使用者需求的最短路徑,前面兩個主要的不含/包含終點的基本方法是利用目前已經找到符合使用者需求的路徑來當作門檻值,利用此門檻值我們可以剔除掉那些長度已經確定比門檻值還要大的路徑,第三個方法,包含終點的修剪方法,是利用我們提出的兩個lemma 和一條已符合使用者需求的路徑來規劃出的一個膠囊形狀的範圍,只有落在此膠囊形狀內的那些點所形成的路徑我們才需要考慮。我們的實驗結果顯示我們提出的方法有不錯的表現,修剪方法更是大大的加速了我們的計算效率。
    Finding the shortest paths in road networks has been studied for years. However, from the perspective of a user, finding the shortest path from a start location to a destination is only a basic requirement. Other demands may also be involved, such as asking for dining or mailing on the way to the destination. In this paper, we consider a novel problem of finding the shortest path which satisfies the user requirement represented as a set of points of interest such as a shopping center or a restaurant. Three main approaches are proposed to deal with this problem. The first two basic approaches answer the queries without and with a destination by using the BFS and DFS based algorithms, respectively. Moreover, we design some pruning strategies for reducing the search space of the paths and then propose another advanced approach. The experiment results show that the advanced approach has great performance in terms of executing time.
    URI: http://nthur.lib.nthu.edu.tw/dspace/handle/987654321/86682
    Source: http://thesis.nthu.edu.tw/cgi-bin/gs/hugsweb.cgi?o=dnthucdr&i=sGH02101062642.id
    Appears in Collections:[資訊工程學系] 博碩士論文

    Files in This Item:

    File SizeFormat
    GH02101062642.pdf147KbAdobe PDF194View/Open


    在NTHUR中所有的資料項目都受到原著作權保護,僅提供學術研究及教育使用,敬請尊重著作權人之權益。若須利用於商業或營利,請先取得著作權人授權。
    若發現本網站收錄之內容有侵害著作權人權益之情事,請權利人通知本網站管理者(smluo@lib.nthu.edu.tw),管理者將立即採取移除該內容等補救措施。

    SFX Query

    與系統管理員聯絡

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