一种基于边界收敛算法的TSP求

A TSP Solver Base on Boundary Convergence Algorithm

通过对旅行商问题(TSP)进行深入研究并结合对一些求解TSP的典型算法的分析研究,提出一种边界收敛算法。在给定的平面点分布中,搜索最边缘的点并连接起来形成一个包围全部点的多边形回路,具有唯一性;然后根据被包围点加入多边形使得回路周长增加最短的原则,将被包围的点依次加入多边形边界回路,最终形成一条遍历全部点的回路。算法由java编程实现,与领域中其他典型算法进行实验比较,实验结果表明本算法不但能取得更优解而且具有快速求解、结果稳定的优势。

By means of studying the traveling salesman problem（TSP） deeply and analyzing some classic algorithms about solving TSP,put forward a boundary convergence algorithm;In the distribution of the planar points were given,search the remotest border points and connect these points to a connected return circuit including all the points,then,according to the principle that the surrounded points add to the polygon so that the return circuit circumference increase the shortest,let the surrounded points add to the polygon constantly,a polygon contain all the points was formed at last;The algorithm was realized by Java program,compare the experimental result with other classic algorithms,the experimental result shows that the boundary convergence algorithm has the advantages in solving problem quickly、stabilized result、simple operation.