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

摘要：

图的路包装问题是一类有着重要应用背景的最优化问题,然而它在计算复杂度上是NP-困难的.受Hassin和Rubinstein 的思想启发,在max-TSP问题的基础上给出了完全图的路包装问题的近似算法,分析了算法的复杂度和近似比；基于LINGO软件的算例表明了算法的可行性和有效性.

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

所属期刊栏目：47

分类号：O224;TP301.6(运筹学)

资助基金：国家自然科学基会the National Natural Science Foundation of China under Grant 10901093

在线出版日期：2012-01-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：220-222