Loading...

Car Fueling

Course video 20 of 60

In this module you will learn about seemingly naïve yet powerful class of algorithms called greedy algorithms. After you will learn the key idea behind the greedy algorithms, you may feel that they represent the algorithmic Swiss army knife that can be applied to solve nearly all programming challenges in this course. But be warned: with a few exceptions that we will cover, this intuitive idea rarely works in practice! For this reason, it is important to prove that a greedy algorithm always produces an optimal solution before using this algorithm. In the end of this module, we will test your intuition and taste for greedy algorithms by offering several programming challenges.

Algorithmic Toolbox

加州大学圣地亚哥分校

课程 1（共 6 门，数据结构与算法专项课程）

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second).

查看授课大纲

您将学习的技能

Dynamic Programming, Debugging, Software Testing, Algorithms, Computer Programming

教学方

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Neil Rhodes
Adjunct Faculty
Pavel Pevzner
Professor
Daniel M Kane
Assistant Professor

脚本

Hi.

In this video, we will consider the problem to find the minimum number of

refills during a long journey by a car.

You will see the similarities between this problem and

the largest number problem from the previous video.

By the end, you will be able to describe how greedy algorithms work in general and

define what is a safe move and a subproblem.

Consider the following problem.

You have a car such that if you fill it up to full tank,

you can travel with it up to 400 kilometers without refilling it.

And you need to get from point A to point B, and

the distance between them is 950 kilometers.

Of course, you need to refill on your way, and

luckily, there are a few gas stations on your way from A to B.

These are denoted by blue circles, and the numbers above them mean the distance from

A to the corresponding gas station along the way from A to B.

And you need to find the minimum number of refills to get from A to B.

One example of such route is to get from point A to the first gas station,

200 kilometers, then to get from first station to the third gas station,

350 kilometers distance.

Then from third gas station to the fourth gas station,

200 km, and then from the fourth gas station to B, 200 kilometers.

But that's not optimal.

We can do better.

Here is another route, which only uses two refills.

We get from A to the second gas station, less than 400 kilometers, then we get from

the second gas station to the fourth gas station, again less than 400 kilometers.

And then, from the fourth gas station to B, only 200 kilometers.

And this route uses only 2 refills, and

it turns out that in this problem, the minimum number of refills is exactly 2.

More formally, we have the following problem.

As the input, we have a car which can travel at most L kilometers,

where L is a parameter if it's filled up to full tank.

We have a source and destination, A and B, and we have n gas station at distances

from x1 to xn in kilometers, from A along the path from A to B.

And we need to output the minimum number of refills to get from A to B,

not counting the initial refill at A.

We want to solve this problem using a greedy strategy, and

greedy strategy in general is very easy.

You first make some greedy choice, then you reduce your problem to

a smaller subproblem, and then you iterate until there are no problems left.

There are a few different ways to make a greedy choice in this particular problem.

For example, you can always refill at the closest gas station to you.

Another way is to refill at the farthest reachable gas station, and by reachable,

I mean that you can get from your current position to this gas station

without refills.

Another way is, for example, to go until there is no fuel and

then just hope that there will be a gas station in there.

So what do you think is the correct strategy in this problem?

And of course, the third option is obviously wrong.

The first option is also wrong, if you think about it, but

the second option is actually correct.

It will give you the optimal number of refills.

We will prove it later.

For now, let's define our greedy algorithm as the whole algorithm.

So we start at A and we need to get to B with the minimum number of refills.

We go from A to the farthest reachable gas station G so

that we can get from A to G with full tank without any refills in the middle.

And now, we try to reduce this problem to a similar problem.

We make G the new A, and now our problem is to get from the new A to B,

again with the minimum number of refills.

And by definition, a subproblem is a similar problem of smaller size.

One example of subproblem is from the previous video.

When we need to construct the largest number out of a list of digits,

we first put the largest digits in front, and then we reduce our problem

to the problem of building the largest number out of the digits which are left.

In this problem, to find the minimum number of refills on the way from A to B,

the first refill at the farthest reachable gas station G.

And then solve a similar problem which is a subproblem to get

from G to B with the minimum number of refills.

Another important term is safe move.

We call a greedy choice a safe move if it is consistent with some optimal solution.

In other words, if there exists some optimal solution in which first move

is this greedy choice, then this greedy choice is called a safe move.

And we will prove a lemma that to refill at the farthest reachable gas station

is a safe move.

Let us first prove it visually.

Let's consider some optimal route from A to B,

and let the first stop on this route to refill B at point G1.

And let G be the farthest gas station reachable from A.

If G1 and G coincide, then our lemma is proved already.

Otherwise, G1 has to be closer to A than G,

because G is the farthest reachable from A, and G1 is reachable from A.

Now, let's consider the next stop on the optimal route, and that would be G2.

And the first case is that G is closer to A than G2,

then the route can look like this.

In this case, we can actually refill at G instead of G1,

and then we will have another optimal route

because it has the same number of refills and G is reachable from A.

And G2 is actually reachable from G,

because it was reachable from G1, but G is closer to G2 than G1.

So this is a correct route, and in this case, our lemma is proved.

And the second case is when G2 is actually closer to A than G, and

then the route can look like this.

But in this case we can avoid refilling at G1 at all and

refill at G2 or even refill at G in the first place.

And then we will reduce the number of refills of our optimal route,

which is impossible.

So the second case actually contradicts our statement

that we are looking at an optimal route, and we've proved our lemma.

To recap, we consider the optimal route R with a minimum number of refills.

We denote by G1 the position of the first refill in R, and by G2,

the next stop was R, which is either a refill or the destination B.

And by G we denote the farthest refill reachable from A, and

we considered two cases.

In the first case, if G is closer than G2 to A,

we can refill at G instead of G1, and it means that refill at G is a safe move.

Otherwise, we can avoid refill at G1.

So this case contradicts that the route R

is the route with the minimum number of refills.

So there is no such case, and we proved our lemma.

And in the next lecture, we will implement this algorithm in pseudocode and

analyze its running time.

关于 Coursera

课程、专项课程和在线学位均由全世界一流大学和教育机构的顶尖授课教师教授。

Join a community of 40 million learners from around the world

Earn a skill-based course certificate to apply your knowledge

Gain confidence in your skills and further your career

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2019 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取