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

摘要

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