非线性约束最短路问题的启发式算法

• 作者: 刁兴春 汪泽焱
• 来源期刊: 系统仿真学报
• 学科: 工学
• 关键词: 受限最短路 非线性约束 整数规划 QoS路由 启发式算法
• 年，卷（期）: 2004,（7）
• 所属期刊栏目: 信息与控制
• 页码范围: 1556-1559
• 页数: 4页
• 分类号: TN915.0
• 字数: 2745字
• 语种: 中文
• DOI: 10.3969/j.issn.1004-731X.2004.07.050

摘要

多约束QoS路由优化是当前网络研究中的一个重要课题,而受限最短路问题(RSP)是QoS路由的一个基本问题.它是NP-完全的,并有许多具有多项式时间和伪多项式时间的启发式求解算法.然而这些方法只能求解一些带有线性约束的RSP.对一些非线性的约束(比如丢失率约束)大都用数学方法转化成线性约束来求解,这增加了问题的复杂性.本文提出了一种新的具有伪多项式时间的启发式算法来求解这类带非线性约束的RSP.主要思想是将非线性约束作为检验条件来使用.当每得到一个解时,检查解是否满足非线性约束.如满足,则得到最终解;否则在原问题中添加一个线性约束.该新约束将去除已经找到的解,从而使原问题的解空间进一步缩小,直到得到最终解.仿真算例说明了算法的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	汪泽焱	解放军理工大学理学院	43	602	12.0	24.0
2	刁兴春		13	128	7.0	11.0