91影视

Travelling salesman problem deals with the set of cities and the distance between the cities. The aim of the problem is to find the shortest route that leads to visit every city exactly once. A tour is a walk around the city that does not use any route or edge more than once and ends with the city that tour has begun.

In order to solve TSP-OPT in polynomial time, the TSP has to be called to polynomial number of calls with varying input using binary search. Consider the graph G with the cities as vertices and the routes as edges. Consider Tbe the sum of all the edge weights and minimum tour is at most T.

Start the binary search on TSP with$b=\frac{T}{2}$, If found then the min tour must be between 0 and $\frac{T}{2}$. If the answer is not found, then the value of the min tour must be between T and $\frac{T}{2}$. Continue the binary search until the resolution of the min-edge length is reached in the graph. The complexity of the binary search must be polynomial in the input argument.

Consider L be the largest edge weight and to replace all the edge weights with L , It takes at most $\left|E\right|\log 鈦�L$bits to represent T. The former representation is still polynomial in the input size.

Therefore, only a polynomial number of calls to TSP using binary search solves the TSP-OPT in polynomial time.