基于贪心环路的减量迭代TSP优化新算法

Use for reference Kruskal algorithm on the minimum spanning tree to produce the edges in the solution of Traveling Salesman Problem and build the initial solution of the greed circuit in order of precedence of the shortest edge. Then, make the first optimization arrangement with the iterative decrease of point and the twice optimization arrangement with the iterative decrease of single edge. Finally, continue the third optimization arrangement with the iterative decrease of multiple edges. In order to convenience of computation, status of each point is described as a six tuple, and each edge is characterized as a three tuple, and then these coordinate data and adjacency matrix data in TSPLIB is reconstructed as adjacency matrix of upper triangle. Tested on thirteen illustrations, one part of which is twelve illustrations in TSPLIB and another is CHN144, the new algorithm of which is able to largely decrease these known best solutions and eil101, eil76 and brazil58 are deceased from 629 to 620, from 538 to 533 and from 25395 to 18456 respectively, at the same time show the circuit path sequence of their solution on Traveling Salesman Problem. The time complexity of the new algorithm is polynomial.