Problem Definition

Loading...

En provenance du cours de Stanford University

Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming

738 notes

Stanford University

Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming

738 notes

Cours 3 sur 4 dans Specialization Algorithms

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.

Problem Definition5:48

A Greedy Algorithm12:57

Correctness Proof - Part I6:57

Correctness Proof - Part II4:40

Handling Ties [Advanced - Optional]7:14

Rencontrer les enseignants

Tim Roughgarden
Professor
Computer Science

For our next case study of how to use greedy algorithms, we're going to turn to

the application domain of scheduling. That is how do you schedule jobs on

shared resources in order to accomplish some objective.

So, the domain of scheduling there's lots of different applications of greedy

algorithms. We'll see two in this course.

we'll start for today just with the following simple scenario.

So, we'll assume, for today, that there's just one shared resource.

This resource could represent any number of things.

For concreteness, you can think of it as a computer processor.

And then, there's a lot of different things that got to get done.

So, for example, there's a lot of processes that have to be handled by this

processor. In the algprithmic question, we are going

to study, is, in what order should we sequence these jobs?

Which one should we do first, which one should we do second, and so on, all the

way up to which one should we do last. So, obviously to answer this question, we

need to pin down the mathematical model a little bit more precisely.

And lets start with just, you know, what is the characteristics of jobs, what

information do we have that might lead us to prefer one job over another.

But for this problem, we're going to assume that each job comes with two known

parameters. So, first of all, job j has what we're

going to call a weight w sub j. That's a non-negative real number.

And you should think of the weight of a job as quantifying its importance.

That is, jobs with a higher weight, in some sense, deserve to be processed

earlier than those with a lower weight. And secondly, each job j is going to come

with a non negative length l sub j. Depending on the application, you may or

may not have a good estimate of how long jobs are going to take, but for today to

keep things simple, let's assume we know what the length of every job is, and

that's l sub j, it's part of the input to are problem.

So. we have now defined the input to this

computational problem. We get n jobs each specified by a weight

and a length. And we know that the output is going to

be a sequence of these n jobs in some order.

So, what we have to understand now is what criterion do we want to optimize?

What are we trying to accomplish with this sequence?

To explain that, I need to tell you about completion times of jobs.

So, the completion time of a job is defined hopefully in exactly the way

you'd think. So, for the job which is scheduled first,

it's just the length of the job because that's how long it takes to process that

job. For whatever job gets scheduled second,

its completion time is the length of the first job and then, the length of that

job itself. So, in other words, it's just the total

time which elapses before that job gets completed,

okay? So, in general, the completion time of a

job is just the sum of the lengths of the jobs scheduled to before that job plus

the length of that job itself. To make sure this is clear, let's go

through a quick example. So, suppose there are three jobs with

lengths one, two, and three. I'm not going to tell you the job weights

because they're irrelevant for the purposes of computing the completion

time. And let's suppose we do the schedule

where we just schedule job one first, the job two, then job three.

So, pictorially, I'm going to represent that schedule just by stacking the jobs

on top of each other with the interpretation that time starts at the

bottom. So, time zero is where we schedule job

one. And then, time increases as we go from

the bottom to the top of the diagram. And the question then is, what are the

completion times of these three jobs? Okay.

So, the correct answer is answer C. So, for the first job, it gets scheduled

first so it's very happy and it just takes one unit of time to complete, so

its completion time is one. The second job, well, it has to wait for

the first job to complete so one unit of time elapses and then, it itself has to

complete so that's two more units so it gets to the completion time of three.

For the third job, it has to wait for the first two to complete, so that adds three

to the clock, and then plus it takes three units of time for a total of six.

So, that's the definition of job completion times. In some sense, we

obviously want completion times to be as small as possible.

But it's not so simple. In any given schedule, the jobs that are

give early on are going to have small completion times and the jobs towards the

end are going to have big completion times. So inevitably, we're going be have

to trading off the completion times between different jobs.

So, what is the optimal way to so that? Well, that depends on our objective

function, and in scheduling, there's many different objective functions you might

want to use. today, I'm just going to tell you about

one. It's not the only natural objective

function, but it's one of several most natural objective functions.

It's called minimizing the weighted sum of completion times.

You translate this English phrase into mathematics in the obvious way.

What you want to do is you want to minimize the sum over all n jobs of their

completion time, but then multiplied by their weight of [UNKNOWN] j.

Okay. So, the sum over j of w j times c j.

The w j is the weight and c j is the completion time as defined on the

previous slot. If you think about it for a second,

you'll realize this is equivalent to minimizing the weighted average of the

completion times with the weights given as in the input.

So, just to make sure this makes sense, let's go back to the example that we saw.

In that example, we had jobs with lengths one, two, and three, and we thought about

to schedule or we scheduled them in that order.

To evaluate the subjective function, I'd have to tell you their weights, so let's

suppose their weights are three, two, and one, respectively.

In this case, the weighted sum of completion times in the schedule,

in the previous slide, well first, we begin with a, the first

job, which has weight three. Its completion time, remember, was one.

Then, we have the second job with weight two, its completion time is three.

Then, we have the third job with weight one, its completion time was six.

So, we sum up the weighted completion times and we get a total of fifteen.

And I'll let you verify that, in fact, all of the three factorial or six

schedules in that example, this is, in fact, the schedule that minimizes the

weighted sum of completion times. And the algorithmic question we're going

to study next, is how do we do this in general?

Given arbitrary input in jobs, weights, and lengths, what is the sequence that

minimizes this sum over all n factorial sequences you might consider?

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

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.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play