## 3.6 The Traveling Salesperson Problem Suppose a salesperson is planning a sales trip that includes 20 cities. Each city is connected to some of the other cities by a road. To minimize travel time, we want to determine a shortest route that starts at the salesperson's home city, visits each of the cities once, and ends up at the home city. This problem of determining a shortest route is called the Traveling Salesperson problem. An instance of this problem can be represented by a weighted graph, in which each vertex represents a city. As in [Section 3.2](LiB0026.html#265), we generalize the problem to include the case in which the weight (distance) going in one direction can be different from the weight going in another direction. Again we assume that the weights are nonnegative numbers. [Figures 3.2](LiB0026.html#267) and [Figures 3.16](#ch03fig16) show such weighted graphs. A ***tour*** (also called a *Hamiltonian circuit*) in a directed graph is a path from a vertex to itself that passes through each of the other vertices exactly once. An ***optimal tour*** in a weighted, directed graph is such a path of minimum length. The Traveling Salesperson problem is to find an optimal tour in a weighted, directed graph when at least one tour exists. Because the starting vertex is irrelevant to the length of an optimal tour, we will consider *v*1 to be the starting vertex. The following are the three tours and lengths for the graph in [Figure 3.16](#ch03fig16):  [](fig3-16_0.jpg) Figure 3.16: The optimal tour is \[*v1*, *v3*, *v4*, *v2*, *v1*\]. The last tour is optimal. We solved this instance by simply considering all possible tours. In general, there can be an edge from every vertex to every other vertex. If we consider all possible tours, the second vertex on the tour can be any of *n* − 1 vertices, the third vertex on the tour can be any of *n* − 2 vertices, …, the *n*th vertex on the tour can be only one vertex. Therefore, the total number of tours is  which is worse than exponential. Can dynamic programming be applied to this problem? Notice that if *vk* is the first vertex after *v*1 on an optimal tour, the subpath of that tour from *vk* to *v*1 must be a shortest path from *vk* to *v*1 that passes through each of the other vertices exactly once. This means that the principle of optimality applies, and we can use dynamic programming. To that end, we represent the graph by an adjacency matrix *W*, as was done in [Section 3.2](LiB0026.html#265). [Figure 3.17](#ch03fig17) shows the adjacency matrix representation of the graph in [Figure 3.16](#ch03fig16). Let  [](fig3-17_0.jpg) Figure 3.17: The adjacency matrix representation *W* of the graph in [Figure 3.16](#ch03fig16). Example 3.10****For the graph in [Figure 3.16](#ch03fig16),  Notice that {*v*1, *v*2, *v*3, *v*4} uses curly braces to represent a set, whereas \[*v*1, *v*2, *v*3, *v*4\] uses square brackets to represent a path. If *A* = {*v*3}, then  If A = {*v*3, *v*4}, then  **** Because *V* − {*v*1, *vj*} contains all the vertices except *v*1 and *vj* and the principle of optimality applies, we have  and, in general for *i* ≠ 1 and *vi* not in *A*,  We can create a dynamic programming algorithm for the Traveling Salesperson problem using Equality 3.7. But first, let's illustrate how the algorithm would proceed. Example 3.11****Determine an optimal tour for the graph represented in [Figure 3.17](#ch03fig17). First consider the empty set:  Next consider all sets containing one element:  Similarly,  Next consider all sets containing two elements:  Similarly,  Finally, compute the length of an optimal tour:  **** The dynamic programming algorithm for the Traveling Salesperson problem follows. Algorithm 3.11: The Dynamic Programming Algorithm for the Traveling Salesperson Problem****Problem: Determine an optimal tour in a weighted, directed graph. The weights are nonnegative numbers. Inputs: a weighted, directed graph, and *n*, the number of vertices in the graph. The graph is represented by a two-dimensional array *W*, which has both its rows and columns indexed from 1 to *n*, where *W* \[*i*\] \[*j*\] is the weight on the edge from *i*th vertex to the *j*th vertex. Outputs: a variable *minlength*, whose value is the length of an optimal tour, and a two-dimensional array *P* from which an optimal tour can be constructed. *P* has its rows indexed from 1 to *n* and its columns indexed by all subsets of *V* − {*v*1}. *P* \[*i*\] \[*A*\] is the index of the first vertex after *vi* on a shortest path from *vi* to *v*1 that passes through all the vertices in *A* exactly once. ``` void travel (int n, const number W [] [], index P [] [], number & minlength) { index i, j, k; number D [1 .. n] [subset of V - {v1}]; for (i = 2; i <= n; i++) D [i] [⊘] = W[i] [1]; for (k = 1; k <= n - 2; k++) for (all subsets A ⊆ V - {v1} containing k vertices) for (i such that i ≠ 1 and vi is not in A){ D [i] [A] = minimum (W [i] [j] + D [j [A - {vj}]); j: [vj ∊ A P[i] [A] = value of j that gave the minimum; } D [1] [V - {v1}] = minimum (W[1] [j] + D[j] [V - {v1, vj}]); 2 ≤ j ≤ n P[1] [V - {v1}] = value of j that gave the minimum; minlength = D[1] [V - {v1}]; } ``` **** Before showing how an optimal tour can be obtained from the array *P*, we analyze the algorithm. First we need a theorem: Theorem 3.1****For all *n* ≤ 1  Proof: It is left as an exercise to show that  Therefore,  The last equality is obtained by applying the result found in [Example A.10](LiB0099.html#1326) in [Appendix A](LiB0093.html#1281). **** The analysis of [Algorithm 3.11](#ch03ex22) follows. ****Analysis of Algorithm 3.11 Every-Case Time and Space Complexity (The Dynamic Programming Algorithm for the Traveling Salesperson Problem)Basic operation: The time in both the first and last loops is insignificant compared to the time in the middle loop because the middle loop contains various levels of nesting. Therefore, we will consider the instructions executed for each value of *vj* to be the basic operation. They include an addition instruction. Input size: *n*, the number of vertices in the graph. For each set *A* containing *k* vertices, we must consider *n* − 1 − *k* vertices, and for each of these vertices, the basic operation is done *k* times. Because the number of subsets *A* of *V* − {*v*1} containing *k* vertices is equal to , the total number of times the basic operation is done is given by  It is not hard to show that  Substituting this equality into Equality 3.8, we have  Finally, applying [Theorem 3.1](#ch03ex23), we have  Because the memory used in this algorithm is also large, we will analyze the memory complexity, which we call *M* (*n*). The memory used to store the arrays *D* \[*vi*\] \[*A*\] and *P* \[*vi*\] \[*A*\] is clearly the dominant amount of memory. So we will determine how large these arrays must be. Because *V* − {*v*1} contains *n* − 1 vertices, we can apply the result in [Example A.10](LiB0099.html#1326) in [Appendix A](LiB0093.html#1281) to conclude that it has 2*n*−1 subsets *A.* The first index of the arrays *D* and *P* ranges in value between 1 and *n.* Therefore,  **** At this point you may be wondering what we have gained, because our new algorithm is still Θ (*n*22*n*). The following example shows that even an algorithm with this time complexity can sometimes be useful. Example 3.12****Ralph and Nancy are both competing for the same sales position. The boss tells them on Friday that, starting on Monday, whoever can cover the entire 20-city territory faster will get the position. The territory includes the home office, and they must return to the home office when they are done. There is a road from every city to every other city. Ralph figures he has the whole weekend to determine his route; so he simply runs the brute-force algorithm that considers all (20 − 1)! tours on his computer. Nancy recalls the dynamic programming algorithm from her algorithms course. Figuring she should take every advantage she can, she runs that algorithm on her computer. Assuming that the time to process the basic instruction in Nancy's algorithm is 1 microsecond, and that it takes 1 microsecond for Ralph's algorithm to compute the length of each tour, the time taken by each algorithm is given approximately by the following:  Dynamic programming algorithm: (20 − 1) (20 − 2) 220−3μs = 45 seconds. We see that even a Θ (*n*22*n*) algorithm can be useful when the alternative is a factorial-time algorithm. The memory used by the dynamic programming algorithm in this example is  Although this is quite large, it is feasible by today's standards. Using the Θ (*n*22*n*) algorithm to find the optimal tour is practical only because *n* is small. If, for example, there were 60 cities, that algorithm, too, would take many years. **** Let's discuss how to retrieve an optimal tour from the array *P.* We don't give the algorithm; rather, we simply illustrate how it would proceed. The members of the array *P* needed to determine an optimal tour for the graph represented in [Figure 3.16](#ch03fig16) are:  We obtain an optimal tour as follows:  The optimal tour is, therefore,  No one has ever found an algorithm for the Traveling Salesperson problem whose worst-case time complexity is better than exponential. Yet no one has ever proved that such an algorithm is not possible. This problem is one of a large class of closely related problems that share this property and are the focus of [Chapter 9](LiB0074.html#880).