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

摘要：

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

关键词：拓扑、TSP、无线传感器网络、启发式算法

分类号：TP212.9;TN929.5(自动化技术及设备)

在线出版日期：2014-07-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：522-525