|
|||||
|
|
| 基于拓扑感知的TSP快速求解算法 | |
| 引用本文： | 张帅,汪芸,李凯.基于拓扑感知的TSP快速求解算法[J].东南大学学报(自然科学版),2014(3):522-525. |
| 作者姓名： | 张帅 汪芸 李凯 |
| 作者单位： | 东南大学计算机科学与工程学院;东南大学网络和信息集成教育部重点实验室 |
| 摘 要： | 为了适应无线传感器网络环境的特点,提出了一种基于拓扑感知的旅行商问题(TSP)启发式快速求解算法.通过分析无线传感器网络拓扑与TSP解之间的关系,提出了基于最大公共同构子图的拓扑距离,并用于度量拓扑之间的相似度.然后,以拓扑距离为标准,对输入拓扑进行聚类分析,继而映射得出该输入拓扑的TSP解.该算法设置了合适的剪枝条件以提高运行速度,通过加入阈值参数来平衡类内拓扑间的相似度和聚类类别数目.仿真结果表明,在节点数为90和70的TSP环境下,这种拓扑感知算法的运行时间分别为0.615和0.508 s,约为Lin-Kernighan算法和蚁群算法的3%~4%,且其精确度介于这两种算法之间. |
| 关 键 词： | 拓扑 TSP 无线传感器网络 启发式算法 |
| 本文献已被 CNKI 等数据库收录！ | |