基于拓扑感知的TSP快速求解算法

• 作者: 张帅 李凯 汪芸
• 来源期刊: 东南大学学报（自然科学版）
• 学科: 工学
• 关键词: 拓扑 TSP 无线传感器网络 启发式算法
• 年，卷（期）: 2014,（3）
• 页码范围: 522-525
• 页数: 4页
• 分类号: TP212.9|TN929.5
• 字数: 3930字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-0505.2014.03.013

摘要

为了适应无线传感器网络环境的特点，提出了一种基于拓扑感知的旅行商问题（TSP）启发式快速求解算法．通过分析无线传感器网络拓扑与TSP解之间的关系，提出了基于最大公共同构子图的拓扑距离，并用于度量拓扑之间的相似度．然后，以拓扑距离为标准，对输入拓扑进行聚类分析，继而映射得出该输入拓扑的TSP解．该算法设置了合适的剪枝条件以提高运行速度，通过加入阈值参数来平衡类内拓扑间的相似度和聚类类别数目．仿真结果表明，在节点数为90和70的TSP环境下，这种拓扑感知算法的运行时间分别为0．615和0．508 s，约为Lin-Kernighan算法和蚁群算法的3％～4％，且其精确度介于这两种算法之间．

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张帅	东南大学计算机科学与工程学院	20	185	7.0	13.0
5	汪芸	东南大学计算机科学与工程学院	48	332	9.0	16.0
9	李凯	东南大学计算机科学与工程学院	15	33	4.0	5.0