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.