|
|||||
|
|
| 凸包工作集TSP算法 | |
| 引用本文： | 葛华,李香云.凸包工作集TSP算法[J].安徽科技学院学报,2014,28(2). |
| 作者姓名： | 葛华 李香云 |
| 作者单位： | 安徽科技学院数理与信息工程学院,安徽凤阳,233100;安徽科技学院数理与信息工程学院,安徽凤阳,233100 |
| 基金项目： | 安徽省教育厅自然科学研究项目(KJ2013Z050);安徽科技学院引进人才基金项目(ZRC2010255) |
| 摘 要： | TSP问题是一个NP完全问题,在现实生活中许多领域得到充分应用。通过对"S计算几何"中凸包算法分析,提出了一种最大凸包工作集规划TSP路径算法,能快速解决二维TSP问题。首先运用凸包算法构造城市的最大凸包工作集,将剩余城市节点根据隶属度大小加入到相应的凸包子工作集中。再应用最大凸包算法逐个划分凸包子工作集,直至子工作集中的尺度为2。最后依次访问每个子工作集头,得到TSP最短路径。实验结果表明,该算法能更快速地得到问题的近似最优解。 |
| 关 键 词： | 凸包 工作集 工作集划分 TSP 二维 |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |