算法高级教程3.3Thetravelingsalesmanproblem.pptVIP

Traveling Salesman Problem Traveling Salesman Problem (TSP) Optimization problem: Given a complete weighted graph, find a minimum weight Hamiltonian cycle Decision Problem: Given a complete weighted graph and an integer k, is there a Hamiltonian cycle with total weight at most k? TSP as a CombinatorialOptimization Problem If n is the number of cities then (n-1)! is the total number of possible routes n=5 120 possible routes n=10 3,628,800 possible rotes n=20 2,432,902,008,176,640,000 possible routes TSP is a NP-Complete combinatorial optimization problem = non-deterministic polynomial time Scientific challenge for solving TSP $1 million prize for solving the TSP as one representative problem of a larger class of NP-complete combinatorial optimization problems has been offered by Clay Mathematics Institute of Cambridge (CMI) The traveling-salesman problem The triangle inequality: if for all vertices u, v, w∈V, cost function w satisfies w(u, w) ≤ w(u, v) + w(v, w). The traveling-salesman problem with the triangle inequality ApproxMSTTSP(G) 1 select a vertex r∈V to be a root vertex 2 compute a minimum spanning tree T for G from root r using MSTPrim(G, w, r) 3 let L be the list of vertices visited in a preorder tree walk of T 4 return the hamiltonian cycle H that visits the vertices in the order L Even with a simple implementation of MSTPrim, the running time of ApproxMSTTSP(G) is O(|V|2). Theorem ApproxMSTTSP(G) is a polynomial-time 2-approximation algorithm for the traveling salesman problem with the triangle inequality. Proof. Let H* denote an optimal tour for the given set of vertices. Since we obtain a spanning tree by deleting any edge from a tour, the weight of the minimum spanning tree T is a lower bound on the cost of an optimal tour, that is, w(T) ≤w(H*)-w(e) ≤w(H*) A full walk of T lists the vertices when they are first visited and also whenever they are returned to after a visit to a subtree. Let us call this w