A problem is in the set NP if we have an efficient algorithm to verify whether an output solves the problem. Given a weighted directed graph and a bound D on the distance traveled, the traveling salesman problem ask if there is a tour visiting all vertices in the graph with length D or less. Reducing the Hamiltonian cycle problem to the traveling salesman problem in polynomial time, we show that the traveling salesman problem is NP-complete. If there would be an efficient algorithm to solve the traveling salesman problem, then the distinction between the set NP and P would disappear.
Негізгі бет the traveling salesman problem is NP-complete
Пікірлер