凸包工作集TSP算法

TSP问题是一个NP完全问题,在现实生活中许多领域得到充分应用。通过对"S计算几何"中凸包算法分析,提出了一种最大凸包工作集规划TSP路径算法,能快速解决二维TSP问题。首先运用凸包算法构造城市的最大凸包工作集,将剩余城市节点根据隶属度大小加入到相应的凸包子工作集中。再应用最大凸包算法逐个划分凸包子工作集,直至子工作集中的尺度为2。最后依次访问每个子工作集头,得到TSP最短路径。实验结果表明,该算法能更快速地得到问题的近似最优解。