給定分群下加快最短路徑計算之時空成本考量

機構典藏 > College of Business and Management > Graduate Institute & Department of Information Management > Thesis > Item 987654321/34193

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/34193

Title:	給定分群下加快最短路徑計算之時空成本考量
Other Titles:	Space and time costs of cluster-based techniques for speedup of shortest path computation
Authors:	鄭宇辰;Cheng, Yu-chen
Contributors:	淡江大學資訊管理學系碩士班魏世杰;Wei, Shih-chieh
Keywords:	最短路徑演算法;有向地標A;階層式路徑搜尋;建立邊界點演算法;群內邊界點ALT;空間省除方法;Shortest Path Algorithm;A Search With Landmarks and Triangle Inequaliy (ALT);Hierarchical Shortest Path Search;Border Node Construction Algorithm;Local Cluster-Based ALT;Space Reduction Techniques
Date:	2009
Issue Date:	2010-01-11 05:01:04 (UTC+8)
Abstract:	加快傳統Dijkstra最短路徑計算的方法，可依有無分群資訊輔助劃分為兩類，無分群資訊的方法例如雙向搜尋、直線距離A、有向地標A，雖然可提升搜尋效率，但由於路網節點數眾多，提升程度很快遇到瓶頸。有分群資訊的方法中，一種是記錄每個有向邊可到達群的集合，以限制展開節點數，但其前處理時間很耗時。另一種採用階層概念，將路網利用分群劃分為高低兩層級，高層路網可由各低層路網的邊界點構成。找尋最短路徑時透過高層路網可減少展開低層節點數。這類方法依照高低層級路網選擇記錄資訊之不同，所佔用的記憶體及搜尋效率表現也不同。本文研究給定圖形分群之下的階層式最短路徑演算法，利用其前處理得到的輔助資訊加速最短路徑的搜尋。其中高層路網記錄任兩邊界點最短距離及沿途路徑下一節點，低層路網則記錄任一點往返邊界點之最短距離及下或上一節點。對於無交集的分群結果，提供了建立邊界點演算法以找尋銜接各分群之節點。而路徑搜尋的演算核心，提出三個可省除輔助資訊記錄之空間的方案以供選擇，並整理出時空成本考量下的各種方案。至於起終點同群的情況，提出改良式有向地標演算法(群內邊界點ALT)。實驗以台灣路網進行搜尋時間以及所需空間的評估，並與HEPV、Wang兩階層式作法進行比較，結果顯示本文提出的演算法組合空間需求較低，且能在數毫秒內完成最短路徑的搜尋。 Based on use of the cluster information or not, there are two types of techniques for speedup of shortest path computation. Without the cluster information, traditional speedup techniques such as bidirectional search, A* search, and ALT (A* search with Landmarks and Triangle inequality) search can improve the search efficiency but soon reach a bottleneck as the road network grows large. With the cluster information, one kind of cluster-based approach records the set of clusters that each directed edge can reach without detour. It can restrict the number of nodes expanded during the shortest path search, but computing the cluster set information consumes too much time. The other kind of cluster-based approach uses the concept of hierarchical road networks. Nodes of the same clusters form the low-level networks. The high-level network is then built on the border nodes of the low-level networks. Using the high-level network can reduce the number of nodes expanded in low-level networks. The memory requirement and the search efficiency of this approach will vary with the amount of information recorded in high-level and low-level networks. We study the cluster-based approach which precomputes the hierarchical network information to speed up the search. Specifically, our high-level network records the distance and the next border node of the shortest path for each pair of border nodes. Our low-level network records the to/fro distance and the next/previous node of the shortest path between each node in a low-level network and each of its border nodes. For clustering algorithms which produce disjoint clusters, we propose a border node construction algorithm to find minimal border nodes shared by clusters. Based on the constructed hierarchical networks, several cluster-based algorithms for shortest path computation are implemented. For the case of limited memory, we also propose three alternative search options for space reduction. For the case of intra cluster search where traditional cluster-based methods cannot apply, a local cluster-based ALT is proposed to reduce the node expansion during search. Based on the Taiwan road network, our approach is evaluated in terms of the search time and the memory requirement. For comparison, the space and time complexities of HEPV, Wang''s approach and ours are analyzed. The evaluation results show that our approach require less memory and can finish shortest path search in just several milliseconds.
Appears in Collections:	[Graduate Institute & Department of Information Management] Thesis

Files in This Item:

File	Size	Format
	0Kb	Unknown	221	View/Open

Loading...