凸包工作集TSP算法

TSP Algorithm Based on Working Set of Convex Hull

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.