The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

Loading...

En provenance du cours de Stanford University

Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming

488 notes

The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

À partir de la leçon

Week 1

Two motivating applications; selected review; introduction to greedy algorithms; a scheduling application; Prim's MST algorithm.

- Tim RoughgardenProfessor

Computer Science

So at this point we understand, Prim's algorithm and we also know why it's

correct. That is why it always computes the

minimum cost spanning tree of a graph. So in this video, we're going to turn to

implementation issues and running time analysis.

We'll begin by just analyzing the straightforward implementation of Prim's

algorithm. That's already reasonable.

It's polynomial running time, but not especially close to linear.

Then we'll see how a suitable deployment of heaps very much in the way that we did

for Dijkstra's algorithm leads to a blazingly fast, near linear running time.

So let's briefly review the pseudocode for Prim's algorithm.

Recall that Prim grows a tree one edge at a time spanning one new vertex at each

iteration. So it maintains two sets,

capital X, a set of vertices that have spanned so far,

and capital T, these are the edges we've committed to thus far.

They start out by just being some arbitrary vertex, little s, and the empty

set, and in each iteration of this main while-loop, we add one new edge to the

tree. And whatever new vertex that edge spans,

we add that to capital X. The algorithm terminates when we're

spanning all of the vertices and as we've seen, it halts not just with a spanning

tree but with a minimum cost spanning tree.

So suppose we just literally implemented this algorithm as is, what would be the

running time? Well, the initialization stick, step

takes only constant time, so let's ignore that.

So let me just have this one loop. So let's just ask how many iterations

does the loop take and how much time is needed to execute each iteration?

Well, the number of loop iterations is going to be exactly n - 1, so, where n is

the number of vertices. X starts out with one vertex and

terminates when it has all n vertices. How much work do we need to implement

each iteration? Well, essentially, what each iteration is

doing is a brute-force search through the edges.

It's looking for the edges that have one endpoint inside X and one endpoint

outside, and amongst those, it just remembers the

cheapest. And it's easy to see that you could

implement each iteration in O of m time, where M is the number of edges.

For example, you can just, with each vertex associate a Boolean variable that

keeps track of whether or not it's in this capital X, that way when you see an

edge, you know whether it's crossing the frontier or not in constant time.

So putting it together, O of m iterations with O of m works for each gives us a

running time of O of m times n. So this running time is already nothing

to sneeze at. As we discussed, graphs can have an

exponential number of spanning trees. So, this algorithm is doing far less work

than examining each of these spanning trees.

It's homing in in polynomial time, to the minimum cost point.

So that's pretty cool. But remember the mantra of any algorithm

designer worth their salts, confronted with a solution, you should

always ask but can we do better? And can we do better than running time O

of m times n? We can as we'll see in the rest of this

video. The big idea for speeding up Prim's

Algorithm is exactly the big idea we used in part 1 to speed up Dijkstra's

algorithm, namely we're going to deploy a suitable

data structure. So, what data structure seems like it

might be a good idea for making Prim run faster?

Well, what's happening in the main workhorse while-loop of Prim's algorithm?

Over and over again, we keep meaning to do a minimum computation amongst all

edges crossing the frontier, we need to find the cheapest one.

So, the question we should ask ourselves is what kind of data structure would

facilitate, would speed-up repeated minimum computations.

And if you recall from part 1, we have a data structure where that's exactly what

it's raison d'etre is, the heap, the meaning of life for a heap is to

speed-up repeated minimum computations, just like in Prim's algorithm.

So let me just remind you briefly, what are the operations exported by heap data

structure and what is the running time? So first recall that a heap contains a

bunch of objects, and each of those objects should have some key value from

some totally ordered set, like a number, like for example, an edge cost.

So what can you do with a heap? Well, the salient operations for our

purposes today are, first of all, you can insert new stuff into the heap with

their, whatever their key value is. You can extract the object with the

minimum key value. And you can also delete stuff from the

middle of the heap. And all of these can be done in

logarithmic time, logarithmic in a number of objects stored by the heap.

So it's not going to be important for us today to know how heaps are implemented

and what they look like under the hood. We're just going to be clients of them.

We're just going to make use of these operations and the fact that they run in

logarithmic time. But you know, just for those of you who

are curious, and/or want to have your memory jogged. Under the hood, heaps are

implemented logically as complete binary tree.

They're actually laid out in an array, but you sort of think of them

conceptually as being in a complete binary tree. And they, they, they satisfy

what's called the heap property. And the heap property is to make sure that you

know where the object with the minimum key value is.

So the actual definition is, every parent should have a key value which is less

than that of its children. So as you go up the tree, the key value

can only drop and that means you know where the minimum is got to be.

It's got to be at the root of this tree orr the front of the array.

So that's great. That's how you locate the minimum so

quickly in a heap. Now, what do you do when you want to

extract the minimum? So you rip off the root of this tree,

and now, you have to rearrange the tree to restore the heap property.

So you swap the last leaf up to where the root was, you bubble-down as needed to

restore the heap property. how do you insert?

You put the new object as the new last leaf and you bubble it up as needed to

restore the heap property. To delete from the middle of a heap, you

just sort of rip it out and then bubble things up or down as necessary to restore

the heap property. Again, that's not supposed to, if you're

hearing this for the first time, I know this is too fast,

this is just to jog your memory for those of you who already learned this in part 1

of the course. For more details, you can go review the

appropriate videos there. So now that I've reminded you about the

salient properties of heaps. Let's return to the question of how do we deploy them

cleverly to speed-up Prim's algorithm. So our intuition is that because we're

doing repeated minimum computations in Prim's algorithm, each time that it's

while-looped, compute the cheapest edge cross in your frontier, that's sort of in

the wheelhouse of heaps. So how should we use heaps? Well, the

first idea, which is a pretty good idea, is to use the heap to store edges, right?

Because our minimum computation should result in us choosing an edge, so when we

EXTRACT-MIN from a heap, we want it to hand us an edge on a silver platter. So

it would seem this would be your first thought,

that the heap should store edges and that the key value that you use should just be

the edge cost, because you want to find the cheapest edge.

So this already a quite good idea using heaps in this manner.

We'll already definitely speed-up Prim's algorithm relative to the naive

implementation. And in fact.

and I'll leave this as an exercise for you to work out.

using heaps in this way results in an implementation that has, that runs in

time big O of m log n. What I'm going to show you instead is not

that implementation, but an even cleverer implementation of Prim using heaps.

We're not going to see a benefit in the asymptotic running time.

This more sophisticated version will also give us m log n running time, but it

would give you better constants and it is the version you would want to implement

in practice. [SOUND] So, the one slightly tricky point

in this exercise is remembering Prim's algorithm, you don't just want the

cheapest edge overall [INAUDIBLE] You want the cheapest edge which crosses the

current cut that has one endpoint in each of x and v - x.

And, when you use heaps in this way, it might hand you in a silver platter and

edge which is cheap, but isn't necessarily crossing the frontier.

So, you need some extra checks to ensure that you're always finding the minimum

edge and that that edge crosses the frontier between x and v - x.

So I'll leave it to you to work out the details of this implementation in the

privacy of your own home. What I want to spend our time together on

instead is this somewhat more sophisticated, more practical way to use

heaps. And for those of you who remember our

fast implementation of Dijkstra, this will be very familiar to you.

It will be the same kinds of ideas that we used for Dijkstra,

and the keypoint is, instead of using the heap to store edges, were going to use it

to store vertices. So, in a bit more detail, our plan is

going to be to maintain two invariants. The first invariant is going to describe

what the heap contains. The second invariant is going to be what

the key values of those heap object are. So as I said, we're now going to be

starting at vertices in the heap, not edges.

Which vertices? Exactly the vertices that we don't yet

span. The vertices of v - x.

The motivation here is that rather than getting on a silver platter, the edge in

which to add next to the tree, we're going to get from a heap on a silver

platter, the vertex, that we're next going to add to capital X.

So the second invariant tells us what the key values of these vertices in v - x are

supposed to be. And we're going to define them to be the

cheapest cost of an edge incident of this vertex that crosses the current frontier.

So, I think a picture will make this definition clear.

So, consider some snapshot of Prim's algorithm at some iteration.

We have our vertices X that were already spanning.

We have our vertices v - x that were not spanning.

And remember, the elements of the heap by invariant 1 are exactly the vertices on

the right-hand side, the vertices of v - x.

So were trying to find the key value for some vertex in the heap.

So some vertex v, which is on the right side, which is not in x.

And so, what we do is we look at the edges incident on this vertex v that go

back to the left-hand side, so, edges incident to v that are crossing

the frontier and there may be of course be many such edges.

And the invariant we want to maintain is that the key value for this vertex V is

the cheapest of all the incident edges crossing their frontier or in this

picture the key should be equal to two. There is the niggling issue of how do you

define the key if there are no incident edges at all that are crossing the

frontier. So maybe you have a vertex w, which is

buried deep inside of v - x, and actually, none of the incident edges go

back to the left blob at all. So in that case we just define the key to be plus

infinity. So given this high level approach to

implementing Prim's algorithm using heaps, we now have a few things to think

through. So first of all we have to think about

how to initialize the heap so that these invariants are satisfied at the beginning

of Prim's algorithm. Second of all, we have to check that if

these invariants are satisfied, then we can faithfully simulate each iteration of

the while-loop in Prim's algorithm, hopefully very quickly.

And then third, we have to think about how do we make sure these invariants are

maintained throughout the course of Prim's algorithm,

so let's do those in turn. So the first thing is how do we set up the heap at the

beginning of Prim's algorithm and a preprocessing step, so that both of these

invariants are satisfied. Well, at the beginning,

X consists just of this single arbitrary star vertex S.

V minus X contains the other n - 1 vertices.

The key value of a vertex other than S at the beginning of Prim's algorithm, is

just the cheapest edge between that vertex and S if there is one, or plus

infinity otherwise. So, the thing to think through and make

sure you believe this, is that first of all, with a single scan through the

edges, so an O of m time, we can compute the key value for each vertex that needs

to go in the heap. And then, we just have to insert those n

- 1 vertices into the heap. So that's going to cost us O of m time for an edge

scan, and then, m log n for the inserts.

In fact, for those of you that really know heaps very well, you might know

about a heapify operation which allows you to do a batch of n inserts in O of n

time because we can do this even faster in linear time but we're not going to

need that in this lectures. And also, I claim that this expression m

+ n log n is bounded above by the expression m log n, at least an

asymptotic notation. To see that, remember two things. First

of all we're assuming that the input graph is connected, otherwise there's no

spanning trees and it's not interesting to talk about minimum spanning trees.

Second of all, in any connected graph, the number of edges m is at least n - 1.

So asymptotically, m is always at least as big as n and it can be bigger. So you

can always replace an n by an m and get a valid upper bound, so that's what we're

doing here. The second issue we need to think through

is how do we faithfully simulates each iteration of the while loop in Prim's

Algorithm, given that these two invariants halt.

So this issue is going to work out beautifully really, by construction.

We set up our heap and we set up our definition of keys,

so that extracting min from the heap and iteration is a faithful simulation of the

brute-force search in the naive implementation of Prim's alogrithm.

So specifically, assuming that these two invariants hold when we invoke

EXTRACT-MIN from this heap, what it provides to us on a silver platter is the

next vertex, not yet in X.

The next vertex that we should add to X in this iteration.

And moreover, the cheapest edge incident to that vertex crossing the frontier is

the one that we should be adding to the set T in this iteration.

And the way to think about this fact is to think of us as essentially simulating

the brute-force search and the naive implementation using a 2-round knockout

tournament. So, in the straightforward implementation

of Prim, the way we think of it is we just do a

scan through all the edges crossing the frontier and we remember the winner, we

remember the smallest cost of them all. Here,

with a heap, we're doing it in two steps. So first of all, for each vertex on the

right-hand side of the cut, for each vertex in v - x, it locally remembers

what is its best candidate so what is the cheapest edge incident on that vertex

crossing the frontier. So that's kind of round one, so for an

edge to be chosen as the winner, at the very least, it'd better be a local

winner. It'd better be the cheapest edge crossing

the cut that ends at this particular vertex on the right-hand side of the cut.

So that's just in a definition of the key of each vertex and encodes the value of

the winner localed in that vertex. And then this EXTRACT-MIN is envoking the

second round of this 2, 2-round elimination tournament.

It's saying, well, amongst all the proposals from the 1st round, amongst all

the crossing edges that are locally minimum given it's endpoint, which of

them is the cheapest overall? And that's going to be the cheapest edge

crossing this cut, the result of this exact min computation.

Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.