| 一种求解点到点的最短路径的高效下界算法（英文） |
| |
| 引用本文： | 张钟,吕敏,孙广中,陈国良.一种求解点到点的最短路径的高效下界算法（英文）[J].中国科学技术大学学报,2014(10):874-880. |
| |
| 作者姓名： | 张钟 吕敏 孙广中 陈国良 |
| |
| 作者单位： | 中国科学技术大学计算机科学与技术学院 |
| |
| 基金项目： | Supported by National Natural Science Foundation of China(61033009,61303047) |
| |
| 摘 要： | 在许多应用中,实时计算一个源点到一个目的点的最短路径是一个非常重要的问题.学术界已经提出若干下界算法求解点到点的最短路径问题,如A*算法,ALT算法等.这些算法所使用的距离估值比较松散,仍然有很大的提升潜力.ACT算法是一种新的两阶段目标制导下界算法,它组合使用了A*搜索,中心点和三角不等式,并且不依赖于特定领域的先验知识.新算法充分利用了预处理数据,可以获得非常好的距离下界.在真实路网上的实验结果表明,新算法的性能明显优于以往的算法.在某些实例下,最优版本的ACT算法所扩展的顶点数量仅仅比最短路径上的顶点数量多25%左右.
|
| 关 键 词： | 最短路径 下界 预处理 A*搜索 中心点 三角不等式 |
| 本文献已被 CNKI 等数据库收录！ |
|
