Abstract: Because of the deficiency that the typical dynamic programming algorithm can only solve the small-scale Traveling Salesman Problem(TSP), this paper proposes a new dynamic programming algorithm based on the combination and division. The whole sequence of TSP is divided into several parts by five strategies mentioned by the paper. Those parts are combined using the proposed dynamic programming algorithm to get a new better sequence. It repeats the process until it gets the optimum solution. Simulation results show that this algorithm with the higher solution accuracy can effectively reduce the error rate, and have low complexity and good robustness of the solution.
Traveling Salesman Problem(TSP),