凸包工作集TSP算法  

TSP Algorithm Based on Working Set of Convex Hull

作　　者：葛华[1] 李香云[1] 

机构地区：[1]安徽科技学院数理与信息工程学院,安徽凤阳233100

出　　处：《安徽科技学院学报》2014年第2期43-48,共6页Journal of Anhui Science and Technology University

基　　金：安徽省教育厅自然科学研究项目(KJ2013Z050);安徽科技学院引进人才基金项目(ZRC2010255)

摘　　要：TSP问题是一个NP完全问题,在现实生活中许多领域得到充分应用。通过对"S计算几何"中凸包算法分析,提出了一种最大凸包工作集规划TSP路径算法,能快速解决二维TSP问题。首先运用凸包算法构造城市的最大凸包工作集,将剩余城市节点根据隶属度大小加入到相应的凸包子工作集中。再应用最大凸包算法逐个划分凸包子工作集,直至子工作集中的尺度为2。最后依次访问每个子工作集头,得到TSP最短路径。实验结果表明,该算法能更快速地得到问题的近似最优解。The TSP problem is NP-complete problems fully applied in many areas of real life. By analyzing computational geometry ＂S＂in the convex hull algorithm,we propose that a maximum convex hull for planning TSP path algorithm can quickly resolve the two-dimensional TSP problem. Firstly,we use convex hull algorithm to construct the largest convex hull of the city set,with the node to the remaining cities according to the size of the membership of the urban nodes added to the convex hull of set. Then,the convex hull of concentrated urban node one by one division in accordance with the maximum convex hull algorithm until the work has focused on the scale. Finally,the sub working sets are visited one by one to ensure the correctness of the TSP algorithm. The experimental results show that the algorithm bionic intelligent algorithm can more quickly get the approximate solution of the problem.

关 键 词：凸包 工作集 工作集划分 TSP 二维 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]