Dynamic Programming Algorithm Based On Optimal Insertion Subset For The Travelling Salesman Problem

Traveling salesman problem is a typical problem which is easy to describe and difficult to solve.Is there an efficient solution to the traveling salesman problem?This problem involves the boundary of feasible calculation and touches the core of complexity theory.Traveling salesman problem is also widely used in many fields,such as genome sequencing,computer processor design,planet searching and so on.In virtue of its important theoretical and practical significance,traveling salesman has become one of the most studied problems in combinatorial optimization.It drives the development direction of Applied Mathematics,operational research and mathematical planning,and plays a significant role in the new discovery.Looking back on the research history of traveling salesman problem,the first thing people study is the accurate algorithm.But with the deepening of people's understanding of NP problem,it is hard to find the research of trying to use the accurate algorithm to solve traveling salesman problem.For many years,all kinds of approximate methods are generally studied.In contrast,at present,most of the well-known authorities in this field tend to think that NP is not equal to P.even though the authorities can not provide any strong evidence for this,this view seems to be tacitly accepted by most people.However,there is no lack of the story of breaking the shackles of authoritative thoughts and discovering the truth in history.In the precise algorithm of traveling salesman problem,the known running time limit is given by the dynamic programming method of hold and Karp.The Held-Karp method can solve the TSP problem of any n cities in a time proportional to n22n.Based on the research of insertion algorithm for TSP,this thesis redesigns a new dynamic programming algorithm which is different from the Held-Karp algorithm.The main research works of this thesis are as follows:(1)the backtracking algorithm of traveling salesman problem is improved according to convex hull rule optimization,and the upper limit of city scale of backtracking algorithm is raised,which successfully solves the problem of Chinese traveling salesman in acceptable time;(2)the insertion algorithm of traveling salesman problem is studied deeply,and simple insertion optimization is proposed from the analysis of experimental results Based on the conjecture of the same type socket,a dynamic programming algorithm based on the simple insertion subset is proposed;(4)the concept of the optimal insertion subset is proposed according to the conjecture of the same type socket,based on which a new dynamic programming method is designed,and the performance and complexity of the new dynamic programming method are analyzed.The new dynamic programming method has a simpler structure,but also reaches the running time limit of n22n;(5)the implementation process of the new algorithm is described in detail with an example,and the algorithm is programmed.The experimental results show the effectiveness of the new algorithm.Any algorithm has its advantages and disadvantages,and optimization algorithm design is an eternal research topic.The method proposed in this thesis provides a new way to solve the traveling salesman problem.It has certain enlightenment for understanding and analyzing many complex problems,and plays a positive role in promoting the research of combinatorial optimization.