| 基于TSP的图的路包装问题的算法研究 |
| |
| 引用本文： | 王继强.基于TSP的图的路包装问题的算法研究[J].计算机工程与应用,2011,47(21):220-222. |
| |
| 作者姓名： | 王继强 |
| |
| 作者单位： | 山东财政学院 统计与数理学院，济南 250014 |
| |
| 摘 要： | 图的路包装问题是一类有着重要应用背景的最优化问题，然而它在计算复杂度上是NP-困难的。受Hassin和Rubinstein的思想启发，在max-TSP问题的基础上给出了完全图的路包装问题的近似算法，分析了算法的复杂度和近似比;基于LINGO软件的算例表明了算法的可行性和有效性。
|
| 关 键 词： | 路包装 旅行商问题（TSP） 哈密尔顿圈 近似算法 交互式的线性和通用优化求解器（LINGO） |
| 修稿时间： | |
Research of algorithm for path packing problem in graphs based on TSP |
| |
| WANG Jiqiang.Research of algorithm for path packing problem in graphs based on TSP[J].Computer Engineering and Applications,2011,47(21):220-222. |
| |
| Authors: | WANG Jiqiang |
| |
| Affiliation: | School of Statistics and Mathematics，Shandong University of Finance，Jinan 250014，China |
| |
| 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. |
| |
| Keywords: | path packing Traveling Salesman Problem（TSP） Hamilton cycle approximation algorithm Linear Interactive and General Optimize（rLINGO） |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
