一种链路分离路径算法的优化

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (2): 169-171.

一种链路分离路径算法的优化

张广跃¹,汪泽焱²,张申如²

1.解放军理工大学通信工程学院研究生二队，南京 210007
2.解放军理工大学理学院，南京 210007

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-01-11 发布日期:2008-01-11
通讯作者: 张广跃

Optimization of link disjoint path algorithm

ZHANG Guang-yue¹,WANG Ze-yan²,ZHANG Shen-ru²

1.Institute of Communications Engineering，PLA University of Science and Technology，Nanjing 210007，China
2.Institute of Sciences，PLA University of Science and Technology，Nanjing 210007，China

Received:1900-01-01 Revised:1900-01-01 Online:2008-01-11 Published:2008-01-11
Contact: ZHANG Guang-yue

摘要/Abstract

摘要： DIMCRA算法能很好地解决多个加性约束下的链路分离路径问题的算法。论文对DIMCRA算法进行了理论分析，并证明了存在一类链路分离路径问题是该算法不能解决的。随后在算法中引入了组合差分的概念，对算法进行了优化，并通过实例仿真说明了改进后的算法能弥补原算法的不足。

关键词: 多约束, 链路分离, DIMCRA改进

Abstract: Algorithm DIMCRA can solve link disjoint paths problem with multiple additive constraints well.This article has analyzed algorithm DIMCRA，and has proved that the there is a sort of the link-disjoint problem the algorithm DIMCRA cannot solved.Then author has introduced the combination difference which has optimized the old algorithm，and has given an instance to show that the improved algorithm can improve the algorithm’s performance.

Key words: multiple constraints, link disjoint, DIMCRA-improved

张广跃¹,汪泽焱²,张申如². 一种链路分离路径算法的优化[J]. 计算机工程与应用, 2008, 44(2): 169-171.

ZHANG Guang-yue¹,WANG Ze-yan²,ZHANG Shen-ru². Optimization of link disjoint path algorithm[J]. Computer Engineering and Applications, 2008, 44(2): 169-171.

[1]	田保珍，余隋怀，王淑侠，曲敏，裴卉宁，刘昕. 多约束条件下定制产品模块划分方法[J]. 计算机工程与应用, 2016, 52(19): 234-240.
[2]	杨坚，彭玉旭. 基于自适应ACO的多约束QoS路由研究[J]. 计算机工程与应用, 2015, 51(13): 106-110.
[3]	张旭君，吕志民. 基于约束规划的一类排序问题通用求解方法[J]. 计算机工程与应用, 2012, 48(26): 219-224.
[4]	李敏^1，2，陆芸婷¹，邹粤^1，2. IP Mesh网络的多约束QoS选路研究[J]. 计算机工程与应用, 2011, 47(6): 78-81.
[5]	杜少波1，张国基1，刘清2. 一种新的多约束尺寸可变的装箱问题[J]. 计算机工程与应用, 2011, 47(19): 242-244.
[6]	胡琼琼，雷秀娟，张兰. 改进的蚁群算法在QoS网络路由中的应用[J]. 计算机工程与应用, 2011, 47(13): 212-215.
[7]	古明家，宣士斌，廉侃超，李永胜. 求解QoS组播路由的自适应变异二次蚁群算法[J]. 计算机工程与应用, 2010, 46(13): 98-100.
[8]	龙鹏飞,张纯,贺亮. 基于捕食模型与蚁群算法的多约束QoS路由选择[J]. 计算机工程与应用, 2009, 45(14): 116-118.
[9]	肖伟,全惠云,刘枫. 基于蚁群算法的多路径多约束QoS路由研究[J]. 计算机工程与应用, 2008, 44(30): 111-113.
[10]	薛锋,罗建. 基于遗传算法的动态MC²运输问题求解[J]. 计算机工程与应用, 2008, 44(28): 236-238.
[11]	刘枫,全惠云,肖伟. 无线mesh网中基于蚁群算法的多约束QoS路由研究[J]. 计算机工程与应用, 2008, 44(13): 122-125.
[12]	来卫国，侯惠峰，李鸥. 多约束应用层组播的算法研究[J]. 计算机工程与应用, 2007, 43(19): 10-12.