| 节点约束型最短路径的分层Dijkstra 算法 |
| |
| 作者姓名： | 康文雄 许耀钊 |
| |
| 作者单位： | 华南理工大学 自动化科学与工程学院,广东 广州 510640 |
| |
| 基金项目： | 国家自然科学基金资助项目( 61573151, 61105019) ; 广东省自然科学基金资助项目( 2016A030313468) |
| |
| 摘 要： | 针对节点约束型最短路径问题,提出了基于回溯法的分层Dijkstra 算法,通过分 层结构寻找局部最优解来求得全局最优解或次优解．该算法利用分层结构可保存搜索进 度的优势,使其在寻找过必经点最短路径时可以实现对搜索进度的保存与回溯等操作．实 验结果表明: 分层Dijkstra 算法虽然增加了一定的空间复杂度,但能有效地减少Dijkstra 算法的调用次数; 与深度优先搜索、几何代数算法相比,分层Dijkstra 算法虽然不一定能 找到理论最优解,但出解速度较快,在数据量较大的情况下能快速找到次优解．
|
| 关 键 词： | 路由算法 最短路径 节点约束型 回溯法 贪心算法法 |
| 收稿时间： | 2016-05-20 |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《华南理工大学学报(自然科学版)》浏览原始摘要信息 |
|
点击此处可从《华南理工大学学报(自然科学版)》下载全文 |
|
