摘要
在许多应用中,实时计算一个源点到一个目的点的最短路径是一个非常重要的问题.学术界已经提出若干下界算法求解点到点的最短路径问题,如A*算法,ALT算法等.这些算法所使用的距离估值比较松散,仍然有很大的提升潜力.ACT算法是一种新的两阶段目标制导下界算法,它组合使用了A*搜索,中心点和三角不等式,并且不依赖于特定领域的先验知识.新算法充分利用了预处理数据,可以获得非常好的距离下界.在真实路网上的实验结果表明,新算法的性能明显优于以往的算法.在某些实例下,最优版本的ACT算法所扩展的顶点数量仅仅比最短路径上的顶点数量多25%左右.
Querying for the shortest path from a source vertex to a sink vertex in real time is a fundamental problem in numerous applications. Several lower-bounding schemes have been proposed to solve the problem so far, such as A^＊ search and ALT algorithm. But these schemes adopted loose valuations on distance so that there are great potentialities for improving the lower bounds. A novel two-stage goal directed lower-bounding approach, called ACT algorithm, was proposed, which combined A^＊ search, centers and triangle inequality with no prior domain knowledge. Unlike previous schemes, the new algorithm can obtain excellent distance bounds by exploiting a large number of pre-computed data. The experimental results on real road networks show that ACT algorithm significantly outperforms all previous algorithms. In some instances, the vertices scanned by ACT algorithm are only about 25% more than those on optimal paths.
基金
Supported by National Natural Science Foundation of China(61033009,61303047)
关键词
最短路径
下界
预处理
A^＊搜索
中心点
三角不等式
shortest path
lower bounds
preprocessing
A^＊ search
centers
triangle inequality
