WIS in Path Graphs: Optimal Substructure

So, having out iterated through all of our algorithm design paradigms and

noticing that none of them seem to work very well for computing the maximum

weight independent set of a path graph, we're going to develop some ideas for a

new paradigm. And the key approach in this new paradigm

is to first reason about the structure of an optimal solution.

What I mean by this is we're going to seek out statements of the following

form. The optimal solution, whatever it may be,

has to possess a certain form. It has to have been built up from an

optimal solution to a sub-problem in a prescribed way.

So in fact, in much of our discussion of both divide and conquer and greedy

algorithms, this kind of reasoning was implicit.

With dynamic programming, we're going to make it systematic.

For example, implicit in the correctness of many of divide and conquer algorithm

is the fact that an optimal solution to the whole problem has to be expressible,

has to be constructable in a prescribed way from solutions to smaller

sub-problems. So, what's the motivation for doing this

thought experiment, trying to understand what the optimal solution could possibly

look like? Well, the plan is we're going to narrow

the possible candidates for the optimal solution down to a relatively small set

of candidates. With a small set, we can get away with

brute force search to pick the best one. So, one lesson you learn once you get

good at dynamic programming, is that it's not at all circular to reason about the

very object that you're trying to compute.

Remember, the goal here is to devise an algorithm to compute an optimal solution.

And now, I'm telling you to do a thought experiment as if you had already computed

it, as if I had handed it to you on a silver platter.

But that kind of daydreaming can be very productive.

And thinking hey, what if I did have an optimal solution?

What could I say about it? What would it look like?

Observations of that form can actually light up a trail to the computation of

that exact object and we'll see that in the next couple videos.

Alright so that's enough loft, lofty philosophy for now, lets get concrete.

Okay, so we've got this path graph, the vertices have weights.

We want the max weight independent set. Let's again do this thought experiment.

What if someone handed to us, what could we say about it's structure?

We'll be using the following notation when we reason about this maximum weight

independent set. S denotes the vertices in that optimal

solution, in that max weight independent set and we're going to let V sub n denote

the right most, the final vertex of the input graph.

So, here's a content-free statement. This last vertex of the path, V sub n.

Either it's an S or it isn't. So, that's going to give us two cases,

when we reason about the optimal solution.

Let's start with the case where Vn is excluded from the optimal solution

capital S. So, let's let G prime denote the path

graph you get by plucking off Vn, plucking off the right-most vertex from

the original graph G. So, let's make a couple of trivial

observations. So, first of all, this set, capital S,

it's an independent set in G. It doesn't include the last vertex.

So, we can regard this set as equally well as an independent set of the smaller

graph G prime. If it didn't contain consecutive vertices

in G, nor does it in G prime. But actually, we can say more.

Not only is S any old independent set in G prime.

It has to be an optimal, that is, maximum weight independent set in G prime.

Why? Well, if there was something better than

S in G prime, we could take that exact same independent set S star regarded as

an independent set in G and, of course, it would still be better than S in G.

But that contradicts our assumption that S was a max weight independent set in G.

So summarizing, if the max weight independent set S of the original path

graph G does not include the right-most vertex, it can be very simply described

in terms of an optimal solution to a smaller sub-problem.

It literally is a max weight independent set of G prime, the path graph with one

fewer vertex. Alright. So, case one is a warm up for

case two, which is similar but slightly more complicated.

Now, let's assume that the maximum independent S does, in fact, use the

right-most vertex, Vn. Now, by the definition of an independent

set, no two consecutive, no two adjacent

vertices can be chosen. So, by virtue of choosing, choosing V sub

n, the right-most vertex S, in this case, absolutely cannot include the penultimate

vertex V sub n - 1. So, we want to know by G double prime,

the path you get from G by plucking off both of the right-most two vertices.

So now, let's do our best to mimic the argument in case one.

In case one, we said well, S has to also be an independent set of G

prime. Now, here that doesn't make sense, right?

Here, S contains the last vertex so we can't talk about it even being a subset

of any smaller graph. However, if we think about S except for

the last vertex of V sub n, S with Vn removed is an independent set, in fact,

of G double prime, because remember, S can't contain the second to last vertex.

And once again, just like in case one we can say something stronger, S with Vn

removed is not any old independent set of G double prime, it actually must be an

optimal one. It must have maximum possible weight. The

reasoning is similar. Suppose S with Vn removed was not the best possible

independent set in G double prime. Then there's something else called an S

star which is even better, has even bigger weight.

How do we get a contradiction? Well, if we just add Vn to this even

bigger independent set S star that lies in G double prime, we get a bonafide

independent set of the entire graph G with overall weight even bigger than that

of S, but that contradicts the optimality of S.

So, for example you could imagine that this reported optimal solution capital S

had total weight 1,100 in two parts, it had 1,000 weight coming from vertices in

the G double prime, but it also had V sub n which had weight 100 on its own. And so

now, in the contradiction, you say, well, suppose there was an independent set that

had even more than 1,000 weight just in G double prime, say, 1,000 and 50.

Well then, we just add this last vertex V sub n to that, we get an independent set

with weight 1,150 and the original graph G.

But that contradicts the fact that S was supposed to be off more with weight

nearly 1,100. So, notice that the reason were using the

graph G double prime in this argument is to make sure that no matter what S star

is, no matter what this independent set of G

double prime is. We can just add V into it blively and not

worry about feasibility, right?

So, the right-most vertex S star could possibly possess is the third to last

vertex Vn - 2. So, there's no worries about feasibility

when we extend it by adding in the right-most vertex V sub n.

So, to make sure you don't lose the forest for the trees, let me just point,

let me remind you what our high level plan was, and let me point out that we

actually just executed that plan quite successfully in this problem.

The plan was to narrow down the candidates for what the optimal solution

could be. To reason about the form of the optimal

solution and argue that it has to look in a particular way.

What did we just prove on the previous slide?

We said that the optimal solution actually can only be one of two things.

Either it excludes the final vertex and it is nothing more than the max weight

independent set of G prime, or if it includes the right-most vertex than it

must be, a maximum weight independent set frp, G double prime augmented with this

last vertex V sub n. There's only two possibilities for what

the optimal solution could possibly look like, in terms of optimal solutions of

smaller sub problems. So, a corollary of this is that if a

little birdie told us which case we were in, whether or not V sub n, V sub n was

in the optimal solution, we could just complete this by recursing on the

appropriate sub-problem. The little birdie tells us the optimal

solution doesn't have Vn we just recurse on G prime.

If the little birdie tells us v sub n is in the optimal solution, we recurse on G

double prime and then add V sub n to the result.

Now, of course, there is no little birdie and we have no idea whether this

right-most vertex is in the optimal solution or not.

But hey, there is only two possibilities, right?

Here is an idea. Maybe it seems crazy, but why not try

both possibilities and just return whichever one is better?

Why do I suggest that maybe this is crazy? Well, if you stare at this and you

think about it and you think about the ramifications of trying both

possibilities as you recursed down the graph, this may start feeling a little

bit like brute force search. And, in fact it is.

This is just a recursive organization of a brute force search.

Nevertheless, as we'll see in the next video, if we're smart about eliminating

redundancy, we can actually implement this idea in a linear time.

Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming

Destrezas que aprenderás

Revisiones

Impartido por:

Tim Roughgarden

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.