基于TSP的图的路包装问题的算法研究  

Research of algorithm for path packing problem in graphs based on TSP

作　　者：王继强[1] 

机构地区：[1]山东财政学院统计与数理学院,济南250014

出　　处：《计算机工程与应用》2011年第21期220-222,共3页Computer Engineering and Applications

基　　金：国家自然科学基金No.10901093~~

摘　　要：图的路包装问题是一类有着重要应用背景的最优化问题,然而它在计算复杂度上是NP-困难的。受Hassin和Rubinstein的思想启发,在max-TSP问题的基础上给出了完全图的路包装问题的近似算法,分析了算法的复杂度和近似比;基于LINGO软件的算例表明了算法的可行性和有效性。The path packing problem is an optimization problem with many important applications.However,it is NP-hard in computational complexity.Motivated by the idea of Hassin and Rubinstein,an approximation algorithm based on the max-TSP problem for the path packing problem in the complete graphs is presented,and its complexity and approximation ratio are analyzed;an instance based on LINGO software demonstrates the feasibility and efficiency of this algorithm.

关 键 词：路包装 旅行商问题(TSP) 哈密尔顿圈 近似算法 交互式的线性和通用优化求解器(LINGO) 

分 类 号：O224[理学—运筹学与控制论] TP301.6[理学—数学]