计算机应用与软件
計算機應用與軟件
계산궤응용여연건
COMPUTER APPLICATIONS AND SOFTWARE
2014年
10期
1-9
,共9页
最短路径%道路网%层次化
最短路徑%道路網%層次化
최단로경%도로망%층차화
Shortest path%Road networks%Hierarchy
在道路网上计算两点之间的最短路径是图论算法的众多实际应用之一。经典的Dijkstra算法在大规模图上过于缓慢。过去十年间，这个经典问题在道路网上取得了重大突破，目前已知最快算法的运行效率比Dijkstra算法快了百万倍。这些算法都对道路网数据进行预处理，产生一定的辅助信息以加速查询，其中目标向导方法和层次化方法是两类典型方法。一些算法的实验性能良好，但缺乏理论支撑。这是因为难以用数学语言严格地刻画道路网的特性。因此，如何弥合理论与实践的差距是此问题面临的主要挑战。
在道路網上計算兩點之間的最短路徑是圖論算法的衆多實際應用之一。經典的Dijkstra算法在大規模圖上過于緩慢。過去十年間，這箇經典問題在道路網上取得瞭重大突破，目前已知最快算法的運行效率比Dijkstra算法快瞭百萬倍。這些算法都對道路網數據進行預處理，產生一定的輔助信息以加速查詢，其中目標嚮導方法和層次化方法是兩類典型方法。一些算法的實驗性能良好，但缺乏理論支撐。這是因為難以用數學語言嚴格地刻畫道路網的特性。因此，如何瀰閤理論與實踐的差距是此問題麵臨的主要挑戰。
재도로망상계산량점지간적최단로경시도론산법적음다실제응용지일。경전적Dijkstra산법재대규모도상과우완만。과거십년간，저개경전문제재도로망상취득료중대돌파，목전이지최쾌산법적운행효솔비Dijkstra산법쾌료백만배。저사산법도대도로망수거진행예처리，산생일정적보조신식이가속사순，기중목표향도방법화층차화방법시량류전형방법。일사산법적실험성능량호，단결핍이론지탱。저시인위난이용수학어언엄격지각화도로망적특성。인차，여하미합이론여실천적차거시차문제면림적주요도전。
To compute exact point-to-point shortest path in road networks is one of numerous practical applications in graph algorithm. Classic Dijkstra’s algorithm has already turned out to be far too slow in large road networks.Over past decade this classical problem in road networks achieves significant breakthrough,the current known fastest algorithm has the operation efficiency one million faster than the Dijkstra’s algorithm.These algorithms all make pretreatment on the data of road networks,which brings about certain auxiliary information for speeding up the query.Among them there are two typical algorithms,the goal-directed approach and the hierarchical technique.Some of the algorithms have good performances in experimental studies,but the theoretical bounds are unknown to support these observation results.This is because it is hard to depict the characteristics of road networks strictly.Therefore it is the main challenge of the problem that how to fill the gap between the theories and the experimental results.
