共 4 条
- [1] Bauer Reinhard, 2010, ACM J EXPT ALGORITHM, P15
- [2] Dijkstra E. W., 1959, NUMER MATH, V1, P269
- [3] Geisberger R, 2008, LECT NOTES COMPUT SC, V5038, P319, DOI 10.1007/978-3-540-68552-4_24
- [4] HAHNE F., 2000, THESIS U HILDESHEIM
Contraction Hierarchies with A* for digital road maps
被引：2
作者：
Nowak, Curt
[1
]
Hahne, Felix
[1
]
Ambrosi, Klaus
[1
]
机构：
[1] Univ Hildesheim, Inst Betriebswirtschaft & Wirtschaftsinformat, D-31141 Hildesheim, Germany
来源：
OPERATIONS RESEARCH PROCEEDINGS 2011
|
2012年
关键词：
D O I：
10.1007/978-3-642-29210-1_50
中图分类号：
C93 [管理学];
O22 [运筹学];
学科分类号：
070105 ;
12 ;
1201 ;
1202 ;
120202 ;
摘要：
One of the most successful recent approaches for solving single source single destination problems in graphs is the Contraction Hierarchies (CH) algorithm, originally published by [3]. The general algorithm consists of two phases: Firstly, a total order on the nodes in the graph is calculated. Secondly for queries, a modified bi-directional Dijkstra-search is performed on the hierarchy implied hereby. Relying on Dijkstra's algorithm, CH makes no use of the geometric information contained within digital road maps. We propose A*-like modifications of the original query algorithm that double query speed. Results are presented in a benchmark using a map from the OpenStreetMap project.
引用
收藏
页码：311 / 316
页数：6
相关论文