| 基于二维凸包的TSP算法 |
| |
| 引用本文： | 刘宏兵,邬长安,周文勇.基于二维凸包的TSP算法[J].计算机工程与设计,2009,30(8). |
| |
| 作者姓名： | 刘宏兵 邬长安 周文勇 |
| |
| 作者单位： | 1. 武汉理工大学计算机科学与技术学院,湖北武汉430070;信阳师范学院计算机与信息技术学院,河南信阳464000
2. 信阳师范学院计算机与信息技术学院,河南信阳,464000 |
| |
| 基金项目： | 河南省教育厅自然科学基金，校青年骨干教师计划 |
| |
| 摘 要： | 二维凸包是指包含平面点集的最小简单多边形,广泛应用于GIS.将二维凸包与TSP相结合,提出了基于二维凸包的TSP算法,首先快速凸包算法构造城市点集的凸包,该凸包是经过部分城市点且其余点都在其内部的回路.其次将其余的城市点依次插入回路形成新回路,使新回路的长度增量最小,直至所有的城市点都在回路上.在TSPLIB中的典型实例上的实验结果表明,该算法比简单遗传算法更快得到问题的近似解.
|
| 关 键 词： | 二维凸包 旅行商问题 长度增量 快速凸包算法 凸点 |
TSP algorithm based on two dimensional convex hull |
| |
| LIU Hong-bing,WU Chang-an,ZHOU Wen-yong.TSP algorithm based on two dimensional convex hull[J].Computer Engineering and Design,2009,30(8). |
| |
| Authors: | LIU Hong-bing WU Chang-an ZHOU Wen-yong |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
