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.
The dynamic programming algorithm writes itself.
We have a 2 dimensional array. 2 dimensions, 'cuz he have 2 indices, for
each sub problem. One specifying the final vertex, j.
The other specifying the set capital s. It turns out we can get away with a
pretty small set of base cases. We're only going to need to pre-compute
the entries of the 2D array, in which the final destination, j=1.
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.