[1]马跃勇,王海梅,廖建军.多约束最优路径算法比较研究[J].南京理工大学学报(自然科学版),2011,(06):749-754.
 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,2011,(06):749-754.
点击复制

多约束最优路径算法比较研究
分享到:

《南京理工大学学报》(自然科学版)[ISSN:1005-9830/CN:32-1397/N]

卷:
期数:
2011年06期
页码:
749-754
栏目:
出版日期:
2011-12-31

文章信息/Info

Title:
Comparative Study of Multi-constrained Optimal Path Algorithms
作者:
马跃勇1王海梅2廖建军2
南京理工大学1. 现代教育技术中心; 2. 自动化学院,江苏南京210094
Author(s):
MA Yue-yong1WANG Hai-mei2LIAO Jian-jun2
1. Modern Educational Technology Center; 2. School of Automation,NUST,Nanjing 210094,China
关键词:
多约束 最优路径 多弧权网络 路径算法 启发式搜索
Keywords:
multi-constraint optimal path multi-arc weights network path algorithm heuristic search
分类号:
TP393
摘要:
针对多弧权网络路径寻优及其效率问题,提出了4 种多约束最优路径算法,并对其进行 了比较研究。基于经典Dijkstra 算法,提出了多约束最优路径问题的D_MCOP 算法; 引入启发 式搜索思想,设计了A* _MCOP 算法和迭代加深搜索的IDA* _MCOP 算法; 为克服IDA* _MCOP 算法每次迭代都要回到起始节点重新搜索的缺陷,提出了一种多约束边沿搜索算法———Fringe_ MCOP 算法。实例研究表明: 三种启发式搜索算法扩展的节点数、边数以及算法的执行时间都 远小于D_MCOP 算法,而且Fringe_MCOP 算法在三种启发式算法中性能最优; 当给定的约束条 件与最优路径的权值向量越接近时,算法的执行效率越高,当网络规模较大时,这一趋势更加明 显; 当约束条件过于严格而得不到满足约束条件的路径时,A* _MCOP 和Fringe_MCOP 的算法 速度比IDA* _MCOP 的算法速度更快,D_MCOP 的算法速度最慢。
Abstract:
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.

参考文献/References:

[1] Li Yuxi,Harms J,Holte R. Fast exact multiconstraint shortest path algorithms[A]. 2007 IEEE International Conference on Communication[C]. Glasgow,Scodland, UK: IEEE, 2007: 123-130.
[2] Fujita N, Iwata A. Adaptive and efficient multiple path pre-computation for QoS routing protocols[A]. 2001 Global Telecommunications Conference[C]. San Antonio, TX,USA: IEEE, 2001: 2215-2219.
[3] Yuan Y,Wang Dingwei. Multi-objective path selection model and algorithm for emergency evacuation[A]. 2007 IEEE International Conference on Automation and Logistics[C]. Jinan,China: IEEE, 2007: 340-344.
[4] Ji Zhaowang,Chen A,Subprasom K. Finding multi-objective paths in stochastic networks: A simulation-based genetic algorithm approach[A]. 2004 Congress on Evolutionary Computation[C]. Portland,OR,USA: IEEE, 2004: 174-180.
[5] 戴树贵,孙强,潘荫荣. 带限制条件的多权最短路径 近似算法[J]. 计算机工程, 2003, 29( 7) : 88-91.
[6] 邹永贵,魏来. 带多约束条件的最优路径选择算法 研究[J]. 计算机应用, 2008, 28( 5) : 1101-1103.
[7] Gang Liu,Ramakri-shnan K C. A* prune: An algorithm for finding K shortest paths subject to multiple constraints [A]. 2001 IEEE Computer and Communications Societies [C]. Anchorage,AK,USA: IEEE, 2001: 743-749.
[8] Korkmaz T,Krunz M. Multi-constrained optimal path selection[A]. 2001 IEEE Computer and Communications Societies[C]. Anchorage,AK,USA: IEEE, 2001: 834-843.
[9] 胡永良. 启发式多约束路由算法研究[J]. 计算机工 程与应用, 2005, 41( 30) : 155-157.

备注/Memo

备注/Memo:
作者简介: 马跃勇( 1968-) ,男,副研究员,主要研究方向: 信息化、计算机及网络,E-mail: mayueyong@139. com。
更新日期/Last Update: 2012-10-25