  Traveling salesman problem is a NP-hard problem. Until now, researchers have
not found a polynomial time algorithm for traveling salesman problem. Among the
existing algorithms, dynamic programming algorithm can solve the problem in
time O(n^2*2^n) where n is the number of nodes in the graph. The branch-and-cut
algorithm has been applied to solve the problem with a large number of nodes.
However, branch-and-cut algorithm also has an exponential worst-case running
time.
  In this paper, a new exact algorithm for traveling salesman problem is
proposed. The algorithm can be used to solve an arbitrary instance of traveling
salesman problem in real life and the time complexity interval of the algorithm
is (O(n^4), O(n^3*2^n)). It means that for some instances, the algorithm can
find the optimal solution in polynomial time although the algorithm also has an
exponential worst-case running time. In other words, the algorithm tells us
that not all the instances of traveling salesman problem need exponential time
to compute the optimal solution. The algorithm of this paper can not only
assist us to solve traveling salesman problem better, but also can assist us to
deepen the comprehension of the relationship between NP-complete and P.
Therefore, it is considerable in the further research on traveling salesman
problem and NP-hard problem.
