Traveling Salesperson Problem
• Given a directed graph G = (V,E) with edge costs cij
• cij is defined such that cij > 0 for all i and j and cij = ∞ if <i, j> ϵ E.
• |V | = n and n > 1
• Tour
– A tour of G is a directed cycle that includes every vertex in V , and no vertex
occurs more than once except for the starting vertex
– Cost of a tour is the sum of the cost of edges on the tour
– Traveling salesperson problem is to find a tour of minimum cost
• Comments
– 0/1 knapsack is a subset selection problem
– Traveling salesperson is a permutation problem
– Permutation problems are harder to solve
∗ n! different permutations of n objects
∗ 2n different subsets of n objects
∗ n! > 2n
• Greedy algorithm
– Start with vertex v1; call it vi
– Visit the vertex vj that is nearest to vi, or can be reached from vi with least
cost
– Repeat the above starting at vertex vj (call it as new vi) taking care never to
visit a vertex already visited
• Dynamic programming algorithm
– Regard the tour to be a simple path that starts and ends at vertex 1
– Every tour consists of an edge <1, k> for some k ∈ V − {1} and a path
from vertex k to vertex 1
– The path from vertex k to vertex 1 goes through each vertex in V − {1, k}
exactly once
– If the tour is optimal, then the path from k to 1 must be a shortest k to 1 path
going through all vertices in V −{1, k}
– Let g(i, S) be the length of a shortest path starting at vertex i, going through all vertices
in S, and terminating at vertex 1
– g(1, V − {1}) is the length of an optimal salesperson tour
– From the principal of optimality
g(1, V − {1}) = min {c1k + g(k, V − {1, k})} ------- (1)
2≤k≤n
– Generalizing (for i S)
g(i, S) = min {cij + g(j, S − {j})} --------- (2)
j∈S
– Equation 1 may be solved for g(1, V − {1}) if we know g(k, V − {1, k}) for all values
of k
– The g values may be obtained by using Equation 2
∗ g(i, ∅ ) = ci,1, 1 ≤ i ≤ n
∗ We can use Equation 2 to obtain g(i, S) for all S of size 1
∗ Then we can obtain g(i, S) for S with |S| = 2
∗ When |S| < n − 1, the values of i and S for which g(i, S) is needed are such that i ≠ 1,
1 S, and i S
• Solving traveling salesperson problem with dynamic programming – example
– Consider the directed graph presented below
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0
– Solving for 2, 3, 4
g(2,∅ ) = c21 = 5
g(3,∅ _) = c31 = 6
g(4,∅ ) = c41 = 8
– Using Equation 2, we get
g(2, {3}) = c23 + g(3, ∅ ) = 15 g(2, {4}) = 18
g(3, {2}) = 18 g(3, {4}) = 20
g(4, {2}) = 13 g(4, {3}) = 15
– Next, we compute g(i, S) with |S| = 2, i 1, 1 S, and i S
g(2, {3, 4}) = min{c23 + g(3, {4}), c24 + g(4, {3})} = 25
g(3, {2, 4}) = min{c32 + g(2, {4}), c34 + g(4, {2})} = 25
g(4, {2, 3}) = min{c42 + g(2, {3}), c43 + g(3, {2})} = 23
– Finally, from Equation 1, we obtain
g(1, {2, 3, 4}) = min{c12 + g(2, {3, 4}), c13 + g(3, {2, 4}), c14 + g(4, {2, 3})}
= min{35, 40, 43}
= 35
– Optimal tour
∗ Has cost 35
∗ A tour of this length may be constructed if we retain with each g(i, S) the value
of j that minimizes the right hand side of Equation 2
∗ Let this value be called J(i, S)
∗ Then, J(1, {2, 3, 4}) = 2
∗ Thus the tour starts from 1 and goes to 2
∗ The remaining tour may be obtained from g(2, {3, 4})
∗ Now, J(2, {3, 4}) = 4
∗ Thus the next edge is < 2, 4 >
∗ The remaining tour is for g(4, {3})
∗ J(4, {3}) = 3
∗ The optimal tour is 1, 2, 4, 3, 1
• Analysis of traveling salesperson
– Let N be the number of g(i, S) s that have to be computed before Equation 1 may
be used to compute g(1, V −{1})
– For each value of |S|, there are n − 1 choices of i
– The number of distinct sets S of size k not including 1 and i is ∑ (n−2
k )
– Hence,
n −2
k=0
(k)
N =∑ ( n−k−1 ) n−2 =(n−1) 2
n−2
– An algorithm that finds an optimal tour using Equations 1 and 2 will require Θ(n22n)
time as the computation of g(i, S) with |S| = k requires k − 1 comparisons when solving
Equation 2
– Better than enumerating all n! different tours to find the best one
– The most serious drawback of the dynamic programming solution is the space needed
(O(n2n))
∗ This can be too large even for modest values of n.
