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

张帅; 汪芸; 李凯

首页> 中文期刊> 《东南大学学报：自然科学版》 >基于拓扑感知的TSP快速求解算法

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

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

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

著录项

来源
《东南大学学报：自然科学版》 |2014年第3期|522-525|共4页
作者
张帅; 汪芸; 李凯;
展开▼
作者单位

东南大学计算机科学与工程学院;

东南大学网络和信息集成教育部重点实验室;

展开▼
原文格式 PDF
正文语种 chi
中图分类移动通信;
关键词
拓扑; TSP; 无线传感器网络; 启发式算法;

相似文献

中文文献
外文文献
专利

1. TSP问题的一种快速求解算法 [J] . 王建忠 ,唐红 . 微电子学与计算机 . 2011,第1期
2. 基于遗传算法的TSP问题求解算法及其系统 [J] . 代桂平 ,王勇 ,侯亚荣 . 微计算机信息 . 2010,第004期
3. 一种基于归零矩阵的TSP求解算法 [J] . 郭文强 ,秦志光 ,冯昊 . 计算机科学 . 2009,第008期
4. 基于蚁群算法的TSP的改进求解算法 [J] . 林海波 ,颜学峰 ,钱锋 . 计算机与数字工程 . 2006,第002期
5. 基于最小距离均衡系数的TSP问题求解算法 [J] . 郏宣耀 . 洛阳理工学院学报（社会科学版） . 2005,第002期
6. 一种基于蚁群算法的TSP问题分段求解算法 [C] . 吴斌 ,史忠植 . 第六届中国人工智能职合学术会议 . 2001
7. 改进的TSP进化求解算法研究 [A] . 高贤维 . 2008

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

摘要

著录项

相似文献

相关主题

期刊订阅