1 00:00:00,012 --> 00:00:04,139 In this video and the next, we're going to revisit the famous traveling salesman 2 00:00:04,139 --> 00:00:06,598 problem. When we first talked about TSP, it was 3 00:00:06,598 --> 00:00:08,839 bad news. The context was NP completeness. 4 00:00:08,839 --> 00:00:12,611 We discussed Edmond's Conjecture. That, it's widely believed there's no 5 00:00:12,611 --> 00:00:15,773 known polynomial time algorithm for solving the TSP problem. 6 00:00:15,773 --> 00:00:19,477 But let's talk about some good news. The fact that you can do better than 7 00:00:19,477 --> 00:00:22,658 naive brute-force search. In fact, it's going to be another neat 8 00:00:22,658 --> 00:00:26,002 application of the dynamic programming algorithm design. 9 00:00:26,002 --> 00:00:29,212 Paradigm. So let me remind you briefly about the 10 00:00:29,212 --> 00:00:33,829 traveling salesman problem. The input, very simple, just a complete 11 00:00:33,829 --> 00:00:39,187 un-directed graph, and each of the end choose two edges has a non-negative cost. 12 00:00:39,187 --> 00:00:44,199 The responsibility of the algorithm is to figure out the minimum cost way of 13 00:00:44,199 --> 00:00:49,409 visiting each vertex exactly once, that is you're supposed to output a tour, a 14 00:00:49,409 --> 00:00:53,704 permutation on the vertices. That minimizes the sum of the 15 00:00:53,704 --> 00:00:58,295 corresponding end edges. For example in this four vertex pink 16 00:00:58,295 --> 00:01:02,504 network the minimum cost towards overall cost thirteen. 17 00:01:02,504 --> 00:01:08,274 You could of course solve the problem using root four search, the running time 18 00:01:08,274 --> 00:01:11,602 of root four search would be in factorial. 19 00:01:11,602 --> 00:01:14,697 Tutorial. This would allow you to solve problems 20 00:01:14,697 --> 00:01:19,257 with say, 12, 13, maybe 14 vertices. In this video, and the next, we'll 21 00:01:19,257 --> 00:01:23,662 develop a dynamic programming algorithm that solves the TSP problem. 22 00:01:23,662 --> 00:01:27,422 Now, of course, TSP is NP complete. We have to expect that. 23 00:01:27,422 --> 00:01:30,492 We're not expected a polynomial time algorithm. 24 00:01:30,492 --> 00:01:35,087 But, this dynamic programming algorithm will run quite a bit faster than 25 00:01:35,087 --> 00:01:38,669 brute-force search. The running time will be big O of n^2 26 00:01:38,669 --> 00:01:41,639 times 2^n. 2^n is of course exponential but it's 27 00:01:41,639 --> 00:01:45,983 quite a bit better than n factorial. n factorial is more ball park n^n. 28 00:01:45,983 --> 00:01:50,388 Okay, if you look at [INAUDIBLE] approximation you'll see it's really n 29 00:01:50,388 --> 00:01:55,369 over a constant raised to the n but still that's much much bigger than a constant 2 30 00:01:55,369 --> 00:01:58,779 raised to the n. To make it more concrete, you could run 31 00:01:58,779 --> 00:02:04,016 this dynamic programming algorithm for values of n, probably pushing 30 or so. 32 00:02:04,016 --> 00:02:08,526 So I realize these are still pretty absurdly small problem sizes, compared to 33 00:02:08,526 --> 00:02:10,977 the size of the arrrays, that we can sort. 34 00:02:10,977 --> 00:02:15,206 Compared to the size of the graphs on which we compute strongly connected 35 00:02:15,206 --> 00:02:19,524 componenets, or shortest paths, but, that's how it goes with NP-complete 36 00:02:19,524 --> 00:02:22,295 problems. You have to work pretty hard, even to 37 00:02:22,295 --> 00:02:26,207 solve modest sized Problems. So at least this dynamic programming out 38 00:02:26,207 --> 00:02:29,687 rhyhm proves the point. That even for empty complete problems, 39 00:02:29,687 --> 00:02:33,732 there are opportunities to improve over brute-force search and the programmer 40 00:02:33,732 --> 00:02:37,827 tool box I've already equipped you with is efficient to make some of those 41 00:02:37,827 --> 00:02:39,466 improvements. Increments. 42 00:02:39,466 --> 00:02:43,542 For the traveling salesman problem, in particular, it's been a benchmark problem 43 00:02:43,542 --> 00:02:47,269 for the development of tools and optimization, and people have worked very 44 00:02:47,269 --> 00:02:50,834 hard, to solve very large instances of the traveling salesman problem. 45 00:02:50,834 --> 00:02:54,665 Even with, 10's of thousands of cities, even sometimes over 100,000 cities. 46 00:02:54,665 --> 00:02:57,179 But, I mean, this often represents years of work. 47 00:02:57,179 --> 00:03:00,971 As I said earlier there's some really nice Some popular accounts of the 48 00:03:00,971 --> 00:03:03,274 Traveling Salesman Problem books out there. 49 00:03:03,274 --> 00:03:07,059 Check it out if you want to know more about the state of the art for solving 50 00:03:07,059 --> 00:03:09,966 large TSP instances. So say we're going to pursue a dynamic 51 00:03:09,966 --> 00:03:14,037 programming approach to the TSP, so that means we should be looking for optimal 52 00:03:14,037 --> 00:03:16,334 substructure. A way in which an optimal must 53 00:03:16,334 --> 00:03:20,025 necessarily be composed of an optimal solution to a smaller sub-problem 54 00:03:20,025 --> 00:03:22,627 extended in some easy way to the original problem. 55 00:03:22,627 --> 00:03:27,179 So what could that look like for TSP? So of all of the programs that we've tackled 56 00:03:27,179 --> 00:03:31,584 using dynamic programming I think the 1 which seems the most like TSP is single 57 00:03:31,584 --> 00:03:34,786 source shortest paths. So think of a tour, not as a cycle 58 00:03:34,786 --> 00:03:39,303 exactly but as a path from some vertex, let's say vertex number 1 looping all the 59 00:03:39,303 --> 00:03:43,696 way back to itself, with, of course, the constraint that it should visit each 60 00:03:43,696 --> 00:03:45,846 other vertex exact. Once on root. 61 00:03:45,846 --> 00:03:50,392 We want to minimize the overall cost of this path from 1 back to itself, so that 62 00:03:50,392 --> 00:03:55,105 sounds a lot like wanting to minimize the length of a path from some source to some 63 00:03:55,105 --> 00:03:59,757 destination, and I'm sure you'll recall that our dynamic programming algorithm 64 00:03:59,757 --> 00:04:03,812 for the single source shortest path problem was the Bellman Ford. 65 00:04:03,812 --> 00:04:08,169 So what then did the sub-problems look like in the Bellman-Ford algorithm. 66 00:04:08,169 --> 00:04:12,946 Well, the cool idea there was to measure sub-problem size using an edge budget, so 67 00:04:12,946 --> 00:04:15,842 a cannotical sub-problem with Bellman-Ford was. 68 00:04:15,842 --> 00:04:20,816 To compute the length of a shortest path from the given source vertex to some 69 00:04:20,816 --> 00:04:23,938 destination vertex v. That has I edges or less. 70 00:04:23,938 --> 00:04:29,327 So, by analogy, we could think here about subproblems, where we want the shortest 71 00:04:29,327 --> 00:04:33,888 path from the starting node vertex, number 1, to some other vertex j. 72 00:04:33,888 --> 00:04:35,974 That uses, at most. I edges. 73 00:04:35,974 --> 00:04:39,394 So precisely, let's define sub-problems as follows. 74 00:04:39,394 --> 00:04:44,146 Given choice I, this represents the number of edges that you're allowed to 75 00:04:44,146 --> 00:04:46,998 use. Given destination J, let's assume that 76 00:04:46,998 --> 00:04:51,715 vertices are They're just named from 1 to n, so I'll call it generic destination j, 77 00:04:51,715 --> 00:04:54,913 an integer from 1 to n. Lets denote capital L sub i j, as the 78 00:04:54,913 --> 00:04:59,030 shortest length of a path from the starting vertex 1, to this destination j, 79 00:04:59,030 --> 00:05:02,178 using at most i edges. So suppose we try to set up a dynamic 80 00:05:02,178 --> 00:05:04,865 programming algorithm using these sub-problems. 81 00:05:04,865 --> 00:05:09,614 What do you think? Can we use these to get polynomial time algorithm for the TSP 82 00:05:09,614 --> 00:05:13,271 problem? All right so the correct answer is C. 83 00:05:13,271 --> 00:05:19,267 So this proposed collections sub problem does not yield the polynomial time 84 00:05:19,267 --> 00:05:25,744 algorithm that is D is not the correct answer that will be surprising, right TSP 85 00:05:25,744 --> 00:05:30,316 is an NP complete problem. So, if this give a polynomial time 86 00:05:30,316 --> 00:05:36,672 algorithm we can all report directly to the Clay Institute for a million dollar 87 00:05:36,672 --> 00:05:40,631 cash prize. Now there's a lot of students in this class, but at least we'd each get 88 00:05:40,631 --> 00:05:43,785 20 bucks or so out of the deal. So that's not the case, this is not going 89 00:05:43,785 --> 00:05:47,461 to be problem time out with them. What's the problem, well the problem is 90 00:05:47,461 --> 00:05:50,687 also not A, it's not that there are too many subproblems. 91 00:05:50,687 --> 00:05:53,381 We only have o of n choice for i, and o of n choices for j. 92 00:05:53,381 --> 00:05:55,850 So there's only a quadratic number of sub-problems. 93 00:05:55,850 --> 00:05:58,472 Just like in Bellman-Ford, that's totally reasonable. 94 00:05:58,472 --> 00:06:02,569 We also can correctly compute the, value of large sub-problems from smaller ones, 95 00:06:02,569 --> 00:06:05,750 it's really exactly the same as what we were doing in Bellman-Ford. 96 00:06:05,750 --> 00:06:08,066 The problem is that our semantics are incorrect. 97 00:06:08,066 --> 00:06:11,833 By solving these sub-problems, we don't actually get an optimal solution to the 98 00:06:11,833 --> 00:06:14,582 traveling salesman incident that we started with. 99 00:06:14,582 --> 00:06:18,488 So what are we hoping is going to be the case? Well, in our dynamic programming 100 00:06:18,488 --> 00:06:22,452 algorithms thus far, after we solved all of the sub-problems, the answer to the 101 00:06:22,452 --> 00:06:25,830 original question was just lying there waiting for us in the biggest 102 00:06:25,830 --> 00:06:28,485 sub-problem. So here, the biggest sub-problem would 103 00:06:28,485 --> 00:06:32,512 correspond to i equaling n, where you allowed to use up to n edges in your 104 00:06:32,512 --> 00:06:34,648 path. The issue with these subproblems is they 105 00:06:34,648 --> 00:06:37,914 only specify an upper bound I. And the number of edges you're allowed to 106 00:06:37,914 --> 00:06:39,928 use. The dude does not enforce that you have 107 00:06:39,928 --> 00:06:43,097 to use your full budget of I edges. So that means when we look at these 108 00:06:43,097 --> 00:06:45,896 biggest sub problems. Yeah the shortest paths could use us as 109 00:06:45,896 --> 00:06:48,623 much as N edges if they wanted. But in general, they won't. 110 00:06:48,623 --> 00:06:51,889 They'll use much fewer than N edges. They'll skip tons of the vertices, 111 00:06:51,889 --> 00:06:55,277 and that's not a traveling salesman tour. A traveling salesman tour has to 112 00:06:55,277 --> 00:06:58,355 [INAUDIBLE]. Every vertex wants that is not enforced 113 00:06:58,355 --> 00:07:02,153 by these sub-problems. But that problem doesn't seem so hard to 114 00:07:02,153 --> 00:07:04,952 fix. Let's just insist in each sub-problem and 115 00:07:04,952 --> 00:07:08,106 instead of using most I-edges and the shortest path. 116 00:07:08,106 --> 00:07:11,547 It has to use exactly I edges and the shortest Path. 117 00:07:11,547 --> 00:07:18,285 So in this set of sub problems there's not quite as misguided as the previous 118 00:07:18,285 --> 00:07:23,281 one, the answer remains the same. The answer is still C. 119 00:07:23,281 --> 00:07:28,552 Of course, we still don't get polynomial time algorithm. 120 00:07:28,552 --> 00:07:32,037 We're not claiming to prove P = NP. The number of sub-problems hasn't 121 00:07:32,037 --> 00:07:34,487 changed. It's still quadratic, and if you think 122 00:07:34,487 --> 00:07:38,597 about it, you can still efficiently solve, for small, bigger sub-problems, 123 00:07:38,597 --> 00:07:42,027 with a bigger edge budget, given the solutions to all of the smaller 124 00:07:42,027 --> 00:07:44,722 sub-problems. So what's the issue? The issue is that 125 00:07:44,722 --> 00:07:48,292 our semantics are still incorrect. Just because you solve all of these 126 00:07:48,292 --> 00:07:52,107 sub-problems doesn't mean you can extract from it the cost of a minimum cost 127 00:07:52,107 --> 00:07:54,180 Traveling Sales. Has been told. 128 00:07:54,180 --> 00:07:58,247 So the problem briefly is that we don't enforce the constrain that you can't 129 00:07:58,247 --> 00:08:02,128 visit a vertex more than once. What would be hoping would be true, we're 130 00:08:02,128 --> 00:08:04,881 hoping and then we look at the biggest sub problem. 131 00:08:04,881 --> 00:08:09,073 So this is when I is equal to n and I'm looking at path that have exactly n edges 132 00:08:09,073 --> 00:08:13,121 and when we take j the destination to be. One, the same as the origin. 133 00:08:13,121 --> 00:08:17,654 We were hoping that that shortest path with images from one back to itself would 134 00:08:17,654 --> 00:08:21,482 be a tour and therefore the minimum cost travelling salesman tour. 135 00:08:21,482 --> 00:08:25,498 But that need not be the case. Just because this path has n edges and it 136 00:08:25,498 --> 00:08:28,494 starts at 1 and it ends at 1 doesn't mean it's a tour. 137 00:08:28,494 --> 00:08:33,165 It might for example visit vertices 7 and 23 twice, and as a result it never visits 138 00:08:33,165 --> 00:08:37,454 vertices 14 or 29 At all. For this reason, the number computed by 139 00:08:37,454 --> 00:08:40,676 the largest sub problem, when i = n and when j = 1. 140 00:08:40,676 --> 00:08:45,358 That can be much, much smaller than the true answer for the minimum cost 141 00:08:45,358 --> 00:08:49,648 traveling salesman tour. A good algorithm designer is nothing if 142 00:08:49,648 --> 00:08:53,379 not tenacious. So, let's just recognize the flaw in this 143 00:08:53,379 --> 00:08:58,662 proposal, that we're not enforcing. Fact that you can't have repeat visits to 144 00:08:58,662 --> 00:09:03,537 a vertex, and let's just change the subproblems again to explicitly disallow 145 00:09:03,537 --> 00:09:08,762 repeated visits to a vertex. So precisely let's index the sub-problems 146 00:09:08,762 --> 00:09:14,472 in exactly the same way as before. There's going to be one for each budget i 147 00:09:14,472 --> 00:09:20,167 and once for each destination j. For a given i and a given j, the value of 148 00:09:20,167 --> 00:09:26,532 the sub-problem is now defined, as the length, of a shortest path, beginning at 149 00:09:26,532 --> 00:09:30,053 one, ending at j. A, using exactly i edges, with the 150 00:09:30,053 --> 00:09:33,527 additional constraint, that no repeated vertices are allow. 151 00:09:33,527 --> 00:09:37,821 The one exception being that if j = 1, then of course you're allowed to have 1 152 00:09:37,821 --> 00:09:41,904 at the beginning and 1 at the end. But for the internal vertices, and the 153 00:09:41,904 --> 00:09:46,683 shortest path, we do not allow, repeats. So what do you think? Does think refine 154 00:09:46,683 --> 00:09:51,166 collection of sub-problems allow us to get a polynomial time algorithm for the 155 00:09:51,166 --> 00:09:55,057 travelling salesman problem. So in today's quiz is more suttle than 156 00:09:55,057 --> 00:09:58,620 the past couple and the correct answer is switched from C to B. 157 00:09:58,620 --> 00:10:02,750 Its still the case that there is a quadratic number of sub-problems, its 158 00:10:02,750 --> 00:10:07,245 still the case that we don't expect upon on our time algorithm but now that with 159 00:10:07,245 --> 00:10:11,272 this different definition of sub problems they do capture the TSP. 160 00:10:11,272 --> 00:10:14,192 Specifically, look at the biggest subproblem. 161 00:10:14,192 --> 00:10:18,926 Take I equal to N, take J equal to 1. The responsibility of that subproblem is 162 00:10:18,926 --> 00:10:23,864 to compute the shortest path from 1 to 1 that has exactly n edges, and no vertices 163 00:10:23,864 --> 00:10:27,786 repeated internally. That is exactly the original problem that 164 00:10:27,786 --> 00:10:30,232 we started with. That is exactly TSP. 165 00:10:30,232 --> 00:10:35,067 The issue is that you cannot efficiently solve larger sub problems, problems with 166 00:10:35,067 --> 00:10:39,292 a larger edge budget, given the solutions to the smaller sub-problems. 167 00:10:39,292 --> 00:10:43,557 The smaller sub-problems are just not very useful for solving the bigger 168 00:10:43,557 --> 00:10:46,712 sub-problems. And the reason is a little bit subtle. 169 00:10:46,712 --> 00:10:50,223 Now the hope would be that like in all our previous dynamic programming 170 00:10:50,223 --> 00:10:53,975 algorithms, you can just formulate a recurrence which tells you how to fill 171 00:10:53,975 --> 00:10:57,565 in, how to solve your sub-problems given the solutions to smaller ones. 172 00:10:57,565 --> 00:11:00,486 And there's even a natural guess, for these sub-problems. 173 00:11:00,486 --> 00:11:02,551 What you hope the recurrence. Might be. 174 00:11:02,551 --> 00:11:06,193 Recurrences generally follow from a thought experiment about what optimal 175 00:11:06,193 --> 00:11:09,274 solutions have to look like. So you want to focus on a particular 176 00:11:09,274 --> 00:11:13,250 subproblem, like given destination j and a given budget i on the number of edges, 177 00:11:13,250 --> 00:11:15,963 you'd say, well let's think about an optimal solution. 178 00:11:15,963 --> 00:11:18,408 So what is that? That's a path that starts at one. 179 00:11:18,408 --> 00:11:20,220 It ends at j. It has exactly i edges. 180 00:11:20,220 --> 00:11:23,510 It has no repeated vertices. And amongst all such paths, it has the 181 00:11:23,510 --> 00:11:26,997 minimum length. And it's natural to proceed by analogy 182 00:11:26,997 --> 00:11:31,647 with Bellman - Ford, and say, well, wouldn't it be cool if a little birdie 183 00:11:31,647 --> 00:11:36,342 tells me what the penultimate vertex k was on the shortest path from 1 to j. 184 00:11:36,342 --> 00:11:40,762 So if I knew that the second to last vertex on the shortest path was k. 185 00:11:40,762 --> 00:11:45,713 Well then, surely, the length of this path would be the length of an optimal 186 00:11:45,713 --> 00:11:49,494 path from 1 to k. Using exactly I-1 edges, and no repeated 187 00:11:49,494 --> 00:11:52,810 vertices. With this final hop, kj concatenated at 188 00:11:52,810 --> 00:11:55,982 the end. Now, of course, you don't know what the 189 00:11:55,982 --> 00:11:58,837 second to last vertex k is. But no big deal. 190 00:11:58,837 --> 00:12:04,432 As usual, in dynamic programming, we're just going to try all of the possibility. 191 00:12:04,432 --> 00:12:09,707 So we can encode this root for search as a minimum over the sensible choices for 192 00:12:09,707 --> 00:12:12,332 k. Clearly, k should not be equal to j. 193 00:12:12,332 --> 00:12:17,532 It should be some other vertex that precedes j, and ignoring some base cases, 194 00:12:17,532 --> 00:12:21,832 let's also preclude k from being 1. That's the starting vertex. 195 00:12:21,832 --> 00:12:27,182 And of course, pictorially, what we have in mind, is we have in mind taking some 196 00:12:27,182 --> 00:12:30,742 shortest path. From one to k so we'd look that up that 197 00:12:30,742 --> 00:12:35,877 would be previously computed in some small sub problem and then can candidate 198 00:12:35,877 --> 00:12:38,619 into it a final half that goes from k to j. 199 00:12:38,619 --> 00:12:43,385 Well hey that sounds pretty good. Right, this is that kind of sound that 200 00:12:43,385 --> 00:12:48,112 may be this is the key ingredient to polynomial time algorithm for TSP. 201 00:12:48,112 --> 00:12:51,607 [INAUDIBLE]. So what's the problem? Well, the problem 202 00:12:51,607 --> 00:12:56,602 is that we've defined our sub problems to disallow repeated visits to a vertex. 203 00:12:56,602 --> 00:13:01,317 So when we compute a sub problem, we better make sure we're respecting that 204 00:13:01,317 --> 00:13:04,482 constraint. That no repeated visits are allowed. 205 00:13:04,482 --> 00:13:09,202 And if we have in our mind, concatenating a shortest path from 1 to K with no 206 00:13:09,202 --> 00:13:11,562 repeats with this final hop. k to j. 207 00:13:11,562 --> 00:13:15,113 Well this might result in a repeated visit to j. 208 00:13:15,113 --> 00:13:20,435 In particular, for all we know, the shortest path from 1 to k, that uses 209 00:13:20,435 --> 00:13:26,513 exactly i-1 edges, and has no repeated vertices, that path might well go through 210 00:13:26,513 --> 00:13:29,762 j. In which case, concatenating this final 211 00:13:29,762 --> 00:13:33,326 hop kj, results in the cycle of second visit to j. 212 00:13:34,466 --> 00:13:38,607 So, this bug means that the proposed recurrence is not correct. 213 00:13:38,607 --> 00:13:43,518 The recurrence is computing something, which, in general, is less than the 214 00:13:43,518 --> 00:13:47,443 actual shortest path length from 1 to j with exactly i edges. 215 00:13:47,443 --> 00:13:50,595 With the no repeat visits constraint respected. 216 00:13:50,595 --> 00:13:55,322 That could be a bigger number than what's computed by this recurrent. 217 00:13:55,322 --> 00:13:59,072 And I encourage to think about, is there any way to fix this bug? Could you 218 00:13:59,072 --> 00:14:02,947 propose a different, more complicated recurrence whicih would still easy to 219 00:14:02,947 --> 00:14:06,982 evaluate but was actually getting the sub problem correct? I don't think you're 220 00:14:06,982 --> 00:14:09,862 going to find one. So the moreal of the story is that this 221 00:14:09,862 --> 00:14:13,657 constraint in the traveling salesman problem that these vertex get visited 222 00:14:13,657 --> 00:14:16,137 exactly once, that's a quite tricky constraint. 223 00:14:16,137 --> 00:14:19,782 And we're going to have to work quite hard to make sure it's satisfied. 224 00:14:19,782 --> 00:14:23,773 The solution we're going to use is in some sense a logical next step from this 225 00:14:23,773 --> 00:14:26,271 recurrence here. We need to be able to know more 226 00:14:26,271 --> 00:14:30,522 information about sub problems than just where they end, we actually need to know 227 00:14:30,522 --> 00:14:34,601 the identities of the vertices on the path used to travel from 1 to K, we need 228 00:14:34,601 --> 00:14:38,818 to know whether or not V is on that path. So we're going to look at a much bigger 229 00:14:38,818 --> 00:14:43,146 set of sub-problems where we remember not just destinations, but also all of the 230 00:14:43,146 --> 00:14:46,287 intermediate stops. That idea will translate to a dynamic 231 00:14:46,287 --> 00:14:50,177 programming algorithm, not a polynomial time one needless to say, the details are 232 00:14:50,177 --> 00:14:50,177 coming right up.