计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (21): 220-222.

• 工程与应用 • 上一篇    下一篇

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

王继强   

  1. 山东财政学院 统计与数理学院,济南 250014
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-07-21 发布日期:2011-07-21

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

WANG Jiqiang   

  1. School of Statistics and Mathematics,Shandong University of Finance,Jinan 250014,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-07-21 Published:2011-07-21

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

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

Abstract: 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.

Key words: path packing, Traveling Salesman Problem(TSP), Hamilton cycle, approximation algorithm, Linear Interactive and General Optimizer(LINGO)