【摘要】 在许多应用中,实时计算一个源点到一个目的点的最短路径是一个非常重要的问题.学术界已经提出若干下界算法求解点到点的最短路径问题,如A*算法,ALT算法等.这些算法所使用的距离估值比较松散,仍然有很大的提升潜力.ACT算法是一种新的两阶段目标制导下界算法,它组合使用了A*搜索,中心点和三角不等式,并且不依赖于特定领域的先验知识.新算法充分利用了预处理数据,可以获得非常好的距离下界.在真实路网上的实验结果表明,新算法的性能明显优于以往的算法.在某些实例下,最优版本的ACT算法所扩展的顶点数量仅仅比最短路径上的顶点数量多25%左右.更多还原

【Abstract】 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.更多还原