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

Comparative Study of Multi-constrained Optimal Path Algorithms

作　　者：马跃勇[1] 王海梅[2] 廖建军[2] 

机构地区：[1]南京理工大学现代教育技术中心,江苏南京210094 [2]南京理工大学自动化学院,江苏南京210094

出　　处：《南京理工大学学报》2011年第6期749-754,共6页Journal of Nanjing University of Science and Technology

摘　　要：针对多弧权网络路径寻优及其效率问题,提出了4种多约束最优路径算法,并对其进行了比较研究。基于经典Dijkstra算法,提出了多约束最优路径问题的D_MCOP算法;引入启发式搜索思想,设计了A*_MCOP算法和迭代加深搜索的IDA*_MCOP算法;为克服IDA*_MCOP算法每次迭代都要回到起始节点重新搜索的缺陷,提出了一种多约束边沿搜索算法———Fringe_MCOP算法。实例研究表明:三种启发式搜索算法扩展的节点数、边数以及算法的执行时间都远小于D_MCOP算法,而且Fringe_MCOP算法在三种启发式算法中性能最优;当给定的约束条件与最优路径的权值向量越接近时,算法的执行效率越高,当网络规模较大时,这一趋势更加明显;当约束条件过于严格而得不到满足约束条件的路径时,A*_MCOP和Fringe_MCOP的算法速度比IDA*_MCOP的算法速度更快,D_MCOP的算法速度最慢。In view of the problems of optimal path search and its efficiency for multi-arc weights network,four algorithms of multi-constrained optimal path（MCOP）are presented and comparatively studied.A D_MCOP algorithm for MCOP is proposed based on the classical Dijkstra ＇ s algorithm;an exact A＊_MCOP algorithm and an iterative deepening search algorithm—IDA＊_MCOP algorithm are designed by introducing a heuristic idea;a multi-constrained fringe search algorithm—Fringe_MCOP algorithm is proposed to overcome the shortcoming of the IDA＊_MCOP algorithm that restarts search from the start node in each iteration.Example research results show：the extended node numbers,edge-numbers and execution times of the heuristic search algorithms are less than those of the D_MCOP algorithm,and the Fringe_MCOP algorithm has the best performance in the heuristic search algorithms;the more approximate the given constraint conditions and the weight vectors of the optimal path are,the higher the execution efficiencies of the algorithms are.The trend is more obvious when the network is bigger;when the constraint condition is too strict to get the fulfilling path,the speeds of the A＊_MCOP algorithm and Fringe_MCOP algorithm are faster than that of the IDA＊_MCOP algorithm,and the D_MCOP algorithm is the slowest.

关 键 词：多约束 最优路径 多弧权网络 路径算法 启发式搜索 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]