原文传递
大规模路网上点到点的最短路径计算的Anytime算法研究
| 论文题名： | 大规模路网上点到点的最短路径计算的Anytime算法研究 |
| 关键词： | 最短路径;大规模路网地图;Anytime算法;异步并行加权;交通导航;图预处理 |
| 摘要： | 图上最短路径问题是一个经典问题，在诸多领域有着广泛的应用，路网上交通导航就是其中尤为重要的一项应用。随着信息化的高速发展，路网趋于精细，数据量较大;比如纽约市路网地图就包含了26万个节点，73万条边。面对大规模的路网数据，传统的最短路径算法在求解时耗时较长，不能满足应用中的实时需求。 Anytime算法是一类能够随时被中断运行，且中断时能返回所求问题的解的算法，并且允许运行的时间越长，算法返回的解的质量就越好。对于求解点到点最短路径问题而言，一个Anytime算法能够在任意时刻终止并返回一条路径，且返回的路径随着允许运行的时间的增加而减短，直至最终返回最短路径。由于这类算法能够尽快的返回一个相对较短的路径，并在时间允许的情况下返回最短路径，从而能够在路径长度和求解时间之间取得平衡。 本文主要工作有: 1，对图预处理算法的实验分析与比较文中描述了几种对图进行预处理的算法，通过实验从预处理时间、边覆盖比例、加速比等角度分析了各个图预处理算法在不同路网地图上的表现，指出了各个算法的特点。本文在已有工作的基础上提出了一种基于路网信息的Scatter预处理算法。 2，对已有点到点最短路径问题的Anytime算法的实验分析与比较文中介绍了三个用于求解点到点最短路径问题的Anytime算法，并对各个算法进行了对比分析，指出它们相同点和不同点，通过实验比较了各个算法在求解时间和求解质量上的不同。分析指出，由于使用了上一轮的计算信息，相对于WA*算法，这些算法找到的路径不够短或耗时较长。 3，提出APWA*算法（异步并行加权A*算法） 该算法利用利用现代计算机具有计算资源冗余性的特点，异步并行的运行多个权值不同的WA*算法实例，并在用户给出中断信号后返回已找到的最短的路径。该算法返回的路径长度随着允许运行的时间的增加而变短，并在时间允许的情况下返回最短路径。 |
| 作者： | 冷勋泰 |
| 专业： | 计算机软件与理论 |
| 导师： | 孙广中 |
| 授予学位： | 硕士 |
| 授予学位单位： | 中国科学技术大学 |
| 学位年度： | 2014 |
| 正文语种： | 中文 |
检索历史
应用推荐
