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