多约束最优路径算法比较研究

被引：13

作者：

马跃勇 ^{[1
]}

王海梅 ^{[2
]}

廖建军 ^{[2
]}

机构：

[1] 南京理工大学现代教育技术中心

[2] 南京理工大学自动化学院

来源：

南京理工大学学报 | 2011年 / 35卷 / 06期

关键词：

多约束; 最优路径; 多弧权网络; 路径算法; 启发式搜索;

D O I：

10.14177/j.cnki.32-1397n.2011.06.011

中图分类号：

TP301.6 [算法理论];

学科分类号：

080201 [机械制造及其自动化];

摘要：

针对多弧权网络路径寻优及其效率问题,提出了4种多约束最优路径算法,并对其进行了比较研究。基于经典Dijkstra算法,提出了多约束最优路径问题的DMCOP算法;引入启发式搜索思想,设计了A*MCOP算法和迭代加深搜索的IDA*MCOP算法;为克服IDA*MCOP算法每次迭代都要回到起始节点重新搜索的缺陷,提出了一种多约束边沿搜索算法———FringeMCOP算法。实例研究表明:三种启发式搜索算法扩展的节点数、边数以及算法的执行时间都远小于DMCOP算法,而且FringeMCOP算法在三种启发式算法中性能最优;当给定的约束条件与最优路径的权值向量越接近时,算法的执行效率越高,当网络规模较大时,这一趋势更加明显;当约束条件过于严格而得不到满足约束条件的路径时,A*MCOP和FringeMCOP的算法速度比IDA*MCOP的算法速度更快,DMCOP的算法速度最慢。

引用

页码：749 / 754

页数：6