| 多约束最优路径算法比较研究 |
| |
| 引用本文： | 马跃勇,王海梅,廖建军. 多约束最优路径算法比较研究[J]. 南京理工大学学报(自然科学版), 2011, 35(6) |
| |
| 作者姓名： | 马跃勇 王海梅 廖建军 |
| |
| 作者单位： | 1. 南京理工大学现代教育技术中心
2. 南京理工大学自动化学院,江苏南京,210094 |
| |
| 摘 要： | 针对多弧权网络路径寻优及其效率问题,提出了4种多约束最优路径算法,并对其进行了比较研究.基于经典Dijkstra算法,提出了多约束最优路径问题的D_MCOP算法；引入启发式搜索思想,设计了A*_MCOP算法和迭代加深搜索的IDA*_MCOP算法；为克服IDA* _MCOP算法每次迭代都要回到起始节点重新搜索的缺陷,提出了一种多约束边沿搜索算法——Fringe_MCOP算法.实例研究表明:三种启发式搜索算法扩展的节点数、边数以及算法的执行时间都远小于D_MCOP算法,而且Fringe_MCOP算法在三种启发式算法中性能最优；当给定的约束条件与最优路径的权值向量越接近时,算法的执行效率越高,当网络规模较大时,这一趋势更加明显；当约束条件过于严格而得不到满足约束条件的路径时,A*_MCOP和Fringe_MCOP的算法速度比IDA*_MCOP的算法速度更快,D_MCOP的算法速度最慢.
|
| 关 键 词： | 多约束 最优路径 多弧权网络 路径算法 启发式搜索 |
Comparative Study of Multi-constrained Optimal Path Algorithms |
| |
| MA Yue-yong , WANG Hai-mei , LIAO Jian-jun. Comparative Study of Multi-constrained Optimal Path Algorithms[J]. Journal of Nanjing University of Science and Technology(Nature Science), 2011, 35(6) |
| |
| Authors: | MA Yue-yong WANG Hai-mei LIAO Jian-jun |
| |
| Affiliation: | MA Yue-yong1,WANG Hai-mei2,LIAO Jian-jun2(1.Modern Educational Technology Center,2.School of Automation,NUST,Nanjing 210094,China) |
| |
| Abstract: | |
| |
| Keywords: | multi-constraint optimal path multi-arc weights network path algorithm heuristic search |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
