| K则最短路径算法效率与精度评估 |
| |
| 引用本文： | 高松,陆锋.K则最短路径算法效率与精度评估[J].中国图象图形学报,2009,14(8):1677-1683. |
| |
| 作者姓名： | 高松 陆锋 |
| |
| 作者单位： | （中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室，北京 100101) |
| |
| 基金项目： | 国家高技术研究发展计划（863）项目（2006AA12Z209，2007AA12Z241）；中国科学院知识创新工程前沿基金项目（CXIOG-D04-02） |
| |
| 摘 要： | 精度和效率是决定最短路径算法实用价值的重要依据。对于K则最短路径问题，各种理论严密算法和有损算法的实用性分析是目前研究的薄弱环节。理论严密算法的实际运行效率比较及其有损算法的精度损耗与效率提高幅度的定量化一直未得到深入研究。针对这一问题，在对K则最短路径算法进行系统分类的基础上，分析了各种经典的理论严密算法和精度有损算法的特征与时间复杂度，结合实际城市路网数据对各种K则最短路径算法的运行效率和精度进行了测试和比较。结果显示，与有损算法相比，理论严密的K则最短路径算法普遍缺乏实用性，只有多重标号算法适合于某些要求精度无损的应用；而一些有损K则最短路径算法以较小的精度损失换取了较大幅度的效率提高，尤以双向搜索算法最具应用推广价值。
|
| 关 键 词： | K则最短路径算法 交通网络 效率 精度 |
| 收稿时间： | 2007/12/12 0:00:00 |
| 修稿时间： | 2008/5/19 0:00:00 |
The Kth Shortest Path Algorithms: Accuracy and Efficiency Evaluation |
| |
| GAO Song,LU Feng and GAO Song,LU Feng.The Kth Shortest Path Algorithms: Accuracy and Efficiency Evaluation[J].Journal of Image and Graphics,2009,14(8):1677-1683. |
| |
| Authors: | GAO Song LU Feng and GAO Song LU Feng |
| |
| Affiliation: | (State Key Laboratory of Resources and Environmental Information System, Institute of Geographical Science and Natural Resources Research, CAS, Beijing 100101) |
| |
| Abstract: | |
| |
| Keywords: | Kth shortest paths algorithms roads network efficiency accuracy |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《中国图象图形学报》浏览原始摘要信息 |
|
点击此处可从《中国图象图形学报》下载免费的PDF全文 |
