0:00

Having laid the groundwork in the previous video, we're now ready to follow

Â our usual dynamic programming recipe to develop a faster than brute-force search

Â dynamic programming algorithm for the traveling Salesman problem.

Â Editing through all those quizzes in the last video, we developed some healthy

Â respect for the traveling salesman problem.

Â We understood why the more natural approaches, which were sufficient for the

Â path problem. For example, the Bellman Ford Algorithm

Â are not good enough to solve TSP. Now no surprise, TSP is an NP complete

Â problem, so you're sort of ready for this, but we know understand it in a

Â pretty. Concrete way.

Â In the single source, shortest path problem, in a sub-problem, all you need

Â to know is where's the path ending and how long could the path be.

Â That's not enough for the traveling salesman problem because there's this

Â extra tricky constraint. But at the end of the day, we want to

Â visit every vertex exactly once. So, in particular, to make sure we don't

Â have repeat vertices show up in our sub-problem solutions.

Â We're going to need to remember not just where smaller sub-problems end.

Â But also the identities of all of the intermediate vertices in the path.

Â Here, then, is the final definition of the sub-problems that we're going to use.

Â We still want to keep track of where this path ends so we still have our

Â destination j, and rather than just specifying a number of vertices that you

Â visit on this path, we specify exactly which vertices get visited.

Â So that's going to be a subset S. A subset of 1 through n.

Â And, of course, it better contain the initial vertex 1, and the final vertex j.

Â And so, for a given choice of j, and a given set choice of capital s.

Â We define l sub s, j, as the length of a shortest path.

Â It starts at vertex 1, end at vertex j. Visits precisely the vertices in capital

Â s, exactly once each. Now, I can understand if your eyes widen

Â a little bit when you see this definition.

Â After all, there's an awful lot of choices for this said capital s, an

Â exponential number. So you'd be right to wonder whether this

Â approach could possibly give any saving whatsoever.

Â Overt naive brute-force search. One thing worth pointing out, and in some

Â sense the source of the computational savings, is that in a given sub problem

Â while it's true we're keeping track of which vertices are visited en route from

Â 1 to j, we're not keeping track Of the order in which those vertices get

Â visited, and indeed, if we had 1 sub-problem for every order in which you

Â might visit vertices from a given source to a given destination, then we'd be

Â stuck with a factorial number of sub-problems.

Â As it is, since we forget the order, and we only focus on sub-sets, that gets us

Â down in more than 2^n range, and that's ultimately.

Â Where the savings over brute-force search come from.

Â So as usual once we've gotten the right set of sub-problems the rest of the

Â dynamic programming recipe pretty much writes itself.

Â But to fill in the details let me just tell you exactly what the optimal

Â substructure limit is, what's the corresponding recurrence and the final

Â pseudocode that gives us our better than brute-force search.

Â Algorithm for the traveling salesman problem.

Â So, for the optimal substructure lemma, we just focus on 1 particular subproblem.

Â So that corresponds to a choice of the destination J.

Â And a choice of the set s. It specifies 1, the starting point.

Â J, the ending point. Plus the rest of the intermediate

Â vertices that we've got to visit along the way, exactly once each.

Â So now we proceed exactly as we did before in [UNKNOWN], namely by focusing

Â on the last hop of this path P. So if the last hop is say from vertex K

Â to vertex J, then we can look at the previous part of the path, call it P

Â prime, what can we say about it? Well clearly it begins at the vertex 1.

Â [INAUDIBLE]. Clearly, it ends at the vertex k.

Â Because of the path p, it visited every vertex in s exactly once.

Â The path, p prime visits every vertex in the set s - j exactly once.

Â And, of course, the optimal substructure lemma says.

Â Not only is prime [INAUDIBLE]. Path.

Â From 1, to k, visiting exactly the vertices of s minus j, once each.

Â It is the shortest, such, path. The proof is an utterly standard, cut and

Â paste argument, like we've been doing for all our other optimal substructure

Â lemmas. I'll leave it as an exercise for you to

Â fill in the details. Tells, as usual the optimal substructure

Â lemma naturally induces a recurrence. recurrence just says well let's look at

Â all of the candidates when [UNKNOWN] solution identified by the lemma and the

Â boot force search among other candidates. That is, for a given sub-problem indexed

Â by a destination j and a set of vertices s, what the recurrence does is it takes

Â the best case scenario, that is the best choice of the second to last vertex k.

Â Of course, k should lie somewhere in the set S, also it should not be the vertex

Â j. And for a given choice of k, we know the

Â corresponding candidate solution has to be a shortest path from 1 to k.

Â Visiting exactly the vertices of s-j. Combined with the cost of the

Â corresponding final hop from k to j. And effectively, we're using the same

Â measure of sub-problem size that we were in the Bellman - Ford solution, just the

Â number of allowable intermediate vertices.

Â Of course, here, the sub-problem also specifies exactly which those vertices

Â are, but as far as a measure of size, we just use the cardinality of that set.

Â As always, the important property of the size measure is that to solve a

Â sub-problem of a given size, you only need to know the answers of sub-problems

Â with strictly smaller size, and staring at the recurrence, you see that that is

Â indeed the case here. You only care about sub-problems that

Â visit 1 fewer vertex, because in particular, j is excluded.

Â 6:14

It's the same as the started vertex.Now if S happens to contain just the vertex

Â 1, then the empty path goes from 1 to 1 with no intermediate stops that has

Â length 0. Otherwise, if S contains extra vertices

Â there's no way to go from 1 back to 1 with intermediate stops.

Â Visiting the vertex 1 only once. So we define the other set problems with

Â j=1 want to have plus infinity value. Now as usual we saw what the set problem

Â systematically using the recurrence. We want to make sure that rather smaller

Â set problems are solved before the bigger ones, so 1 out of 4 loops we iterate over

Â the measure of set problem size which member of the carnality of the set s.

Â Amongst sub-problems of this same size, we don't care what order we solve them.

Â So we just iterate through the sets S of [UNKNOWN] M in arbitrary order.

Â So these outer two for loops accomplish the following, they iterate through the

Â relevant choices of S. That is sets S to have cardinality at

Â least 2 and contain the vertex of 1. So that's the first index of our 2D

Â array. What about the 2nd index J, so this is

Â where the shortest path in a given sub. The problem is supposed to stop.Well sub

Â problems only make sense, are only defined if that final vertex J, is one of

Â the vertices S, that you are supposed to visit.So when we get to a given choice of

Â capital S, at that point we are going to iterate through all the relevant choices

Â of j.and if you recall our argument in the base case and the fact the this SS

Â has size at east 2, there is no point in trying j=1.

Â So now that we have a subproblem. We have our choice of S, we have our

Â choice of J. We just compute the recurrence for this

Â particular subproblem. So what is that? Well, we take a best

Â case choice of the penultimate vertex. So that's some vertex that we've got to a

Â visit. A vertex k and capital S.

Â Other than the one where we stopped, so it can't be equal to j.

Â And then, given a choice of k, what is the corresponding solution of that

Â candidate path from 1 to j. Well, it's whatever the shortest path is

Â from 1 to k. Which of course is visiting everything in

Â s, except for j. Plus whatever the cost of the final hop

Â is from K to J, so the recurrence just figures out what is the optimal choice of

Â K by brute-force search and then by our optimal substructure lemma we know that's

Â the correct answer to this sub problem. Now in almost all of our dynamic

Â programming algorithms, after we solved for the sub problems, all we did was

Â return the value of the biggest one. Here we actually have to do a tiny bit of

Â extra work. It is not the case that the solution we

Â care about. The minimum cost traveling salesman tour

Â is literally one of the sub problems. However, it is true that we can easily

Â compute the minimum cost of a traveling salesman tour given solutions to all of

Â the sub problems. So what is the biggest sub problem? Well

Â there's actually n of them. Remember our measure of sub problem size

Â is the cardinality of the set S, the number of vertices that you've got to

Â visit in that In that sub problem. So in the biggest sub problems S is equal

Â to everything, you have to compute a shortest path that visits each of the N

Â vertices exactly once. So 1 are the semantics of 1 of those sub

Â problems, for a given choice of the 2nd index J, there's N different choices for

Â that final vertex J. That sub problem was responsible for

Â computing the length of the shortest path.

Â Its starts at the vertex 1 it concludes at the vertex J, and it visits every

Â single vertex exactly once. Now hows is this different than a travel

Â salesman tour? Well all thats missing is that finally hop, that hop from J to 1.

Â So what this means is that, after we've solved all of the subproblems in our

Â triple 4 loop. We can complete the algorithm with 1

Â final brute-force search. This final time that brute-force search

Â is over the choice of J. The last vertex that you visit before you

Â return home to vertex #1. So you can skip the choice of J, for 1,

Â that 1 doesn't make sense. But for the other N-1 possibilities for

Â that final vertex J, you take the previously computed value of the shortest

Â path, it starts at 1 and goes to J. Exactly once, you tack on to that the

Â cost of the final hop, going home to 1 from vertex j, and of those n-1 different

Â solutions, you return the best of 'em. That is in fact the cost of the, minimum

Â cost travelling salesman tour. The correctness argument is the same as

Â it always is. The correctness of the optimal

Â substructure lemma Implies the correctness of the recurrence and then

Â the correctness of the dynamic programming algorithm follows from the

Â correctness of the recurrence plus induction.

Â The running time is equally straight forward.

Â So because of the sub problems we're keeping track of a lot of information.

Â Specifically the identities of all the intermediate vertices.

Â There are a lot of sub problems. So in particular there's roughly 2^n

Â choices for the set capital S, there's roughly n choices, for the final

Â destination j. So combining those, we get n*2^n sub

Â problems. How much work do you do per sub-problem?

Â Well you have to execute this brute-force search over the chase, choices of the

Â vertex k. The second to last vertex on the path, k

Â can be almost anything in the set capital S, capital S could have linear size.

Â So you're going to do o(n) work per sub-problem.

Â Thus, the overall amount of work, as promised is O of n^2*2n^2.

Â This is still exponential time, there's still sever limits on how big a value of

Â n you're going to be able to execute this algorithm for.

Â That said, the problem is mp complete and you have to respect its computational

Â intractability. And again, at least this shows there are

Â often interesting algorithmic opportu, opportunities to beat brute-force search,

Â even for mp complete problems like the traffic salesman.

Â