Tree Algorithms For Solving The TSP

Traveling Salesman Problem is a representative NP-Hard problem. It has very important academic significance and actual application values. So it is a research hotspot for several years. Many scholars believe there is no polynomial time complete algorithm for the NP-Hard 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 has fully studied manifold algorithms designed by scholars, and has analyzed the superiors and inferiors of the greedy algorithm and the traditional tree algorithm as well as other approximate methods. We have done the prime tasks from the following aspects: First, we designed the tree algorithm for solving the symmetrical TSP, the algorithm runs based on a minimum spanning tree of a complete graph, guarantees the shorter chains belong to the TSP tour, and then finds a minimal perfect matching in the complete graph composed of remainder nodes. Join the matching in the chains to obtain a TSP tour. Next, we designed the tree algorithm for solving the asymmetrical TSP; the algorithm constructs a minimum directed spanning graph of the original graph to start, transforms it to the transportation problem and solves it, and then adds the arcs corresponding to the solution to the oriented graph and searches a TSP tour. Finally, based on the consideration of the TSP, we designed two approximate algorithms to solve the Multi-TSP, and pointed out some problems to be further studied.