多约束最短链路分离路径精确算法

在通信的源和目的间寻找两条(主用和备用)链路分离的qos路径是提供可靠qos路由的重要途径.现有求解多约束链路分离路径对(multi-constrainedlink-disjointpathpair,简称mclpp)的算法难以保证求得存在于任意网络中的可行解和最优解.为解决这一问题,分析了mclpp问题最优解的性质,提出了精确算法的设计原则,在此基础上给出了求解mclpp问题的精确算法(link-disjointoptimalmulti-constrainedpathsalgorithm,简称lidompa算法),可对任意网络求解客观存在的多约束最短链路分离路径对.为了降低算法的复杂性,引入了候选最优解、紧缩的约束向量和结构化的路径支配3种关键方法,在保障算法精确性的同时,有效地降低了lidompa的搜索空间.大量的实验结果表明,lidompa的求解能力优于现有算法,同时可以实现较低的算法执行时间开销.