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

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

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

王继强

山东财政学院统计与数理学院，济南 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

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

摘要/Abstract

摘要： 图的路包装问题是一类有着重要应用背景的最优化问题，然而它在计算复杂度上是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）

王继强. 基于TSP的图的路包装问题的算法研究[J]. 计算机工程与应用, 2011, 47(21): 220-222.

WANG Jiqiang. Research of algorithm for path packing problem in graphs based on TSP[J]. Computer Engineering and Applications, 2011, 47(21): 220-222.

[1]	陈佳，游晓明，刘升，李娟. 结合信息熵的多种群博弈蚁群算法[J]. 计算机工程与应用, 2019, 55(16): 170-178.
[2]	赵亚文，熊瑞平，乔治，梁齐齐，罗勇. 应用捕食搜索策略的改进多态蚁群算法[J]. 计算机工程与应用, 2019, 55(14): 115-121.
[3]	曾维新1，赵翔1，2，冯滔1，唐九阳1，2. 面向领域的命名实体消歧方法改进研究[J]. 计算机工程与应用, 2018, 54(17): 126-134.
[4]	蒋小娟1，张安1，陈永1，陈光亭2. 内部节点受限的最小生成树问题算法研究[J]. 计算机工程与应用, 2017, 53(10): 35-37.
[5]	段艳明1，肖辉辉1，2. 求解TSP问题的改进果蝇优化算法[J]. 计算机工程与应用, 2016, 52(6): 144-149.
[6]	李絮，刘争艳. 基于云模型的模糊自适应蚁群算法研究[J]. 计算机工程与应用, 2016, 52(2): 24-27.
[7]	聂文艳1，王仲根2. 应用ACA算法快速分析导体目标电磁散射特性[J]. 计算机工程与应用, 2015, 51(4): 232-234.
[8]	叶永刚1，徐耀群2. SLF混沌神经网络及其应用[J]. 计算机工程与应用, 2015, 51(21): 74-79.
[9]	马福祥，马秀娟. 一种基于二次变异策略的改进型遗传算法[J]. 计算机工程与应用, 2014, 50(13): 62-65.
[10]	方霞，席金菊. 基于变异和启发式选择的蚁群优化算法[J]. 计算机工程与应用, 2013, 49(24): 24-27.
[11]	王继强. 集合覆盖问题的模型与算法[J]. 计算机工程与应用, 2013, 49(17): 15-17.
[12]	姚明海1，2，王娜3，赵连朋1. 改进的模拟退火和遗传算法求解TSP问题[J]. 计算机工程与应用, 2013, 49(14): 60-65.
[13]	纪鹏宇1，谢红1，赵蕴龙2. 一种中继节点上的网络-信道编码联合设计方案[J]. 计算机工程与应用, 2012, 48(34): 102-106.
[14]	张敬敏，马丽，李媛媛. 求解TSP问题的改进混合蛙跳算法[J]. 计算机工程与应用, 2012, 48(11): 47-50.
[15]	李絮，刘争艳，谭拂晓. 求解TSP的新量子蚁群算法[J]. 计算机工程与应用, 2011, 47(32): 42-44.