基于点线回路优化求解TSP的一个新算法

New algorithm for solving TSP based on dots and lines loop optimizing

快速有效地解决TSP问题,有着重要的理论价值和极高的实际应用价值。提出了基于点线回路优化求解TSP的算法,首先将原基本回路切去一些点(线段、路径)变成残缺回路,然后把切去的点(线段、路径)重新插入到残缺回路的所有节点之间,生成新的基本回路,切去点(线段、路径)的数量,从一个变到基本回路节点数的一半。算法实现容易、运行速度快,生成的结果接近其最优解。算法尽量避免了陷入局部极小,使得在短时间内能够求解较大规模的TSP问题。

To Solve the（TSP） quickly and effectively has important theoretical values and high practical application values.An available algorithm for solving the TSP at loop optioning based on dots and lines was proposed.Firstly,the original basic loop was cut and became incomplete loop,and then the cutting points（line,path） were inserted into the node of the incomplete loop to build a new basic loop.The number of cutting points（line,path） changed from one to half of the basic loop.The algorithm implemented easily and ran quickly.The result of TSP loop using this algorithm was near to its optimal solution.This algorithm avoids sinking into the smallest part,so that it can solve more large-scale TSP problems in a short time.