A Improved Algorithm Of Solving TSP Problem

Traveling Salesman Problem is a representative NP-Hard problem. It has very important academic significance and actual application value. So it is a research hotspot for several years. Many scholars believe there is no polynomial time completeness algorithm for the NP problem, therefore the approximate algorithm is provided with very important meaning. The TSP becomes a chief criterion for measuring the efficiency of the approximate algorithm. The author studies manifold algorithms designed by scholars, then analyse the strongpoint and limitation of the structure algorithm and the improvement algorithm. The author designs a brand-new approximate algorithm named whole-priority algorithm . Solution procedure of the algorithm is the following four points such as "Take large"(i.e. work out the round route of the largest polygon as the original route), "Merge nearly"(i.e. connect all the stand by points to the nearest edge), "Connect far"(i.e. find out the farthest point on the same edge of "the farthest point as a whole" and connect it to the closed route), "Adjust small"(i.e. adjust the route in the best way to make the total distance of the newly connected closed route the smallest). The time complexity of the algorithm is O(n3). The author get satisfaction result with calculating the data come from TSPLIB using program based on the algorithm. This program runs very fast and its search-optimize ability is equal with mainstream algorithms, so it achieves our expectation.