Car Fueling - Implementation and Analysis

Loading...

来自 University of California San Diego 的课程

Algorithmic Toolbox

3141 个评分

University of California San Diego

Algorithmic Toolbox

3141 个评分

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

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).

从本节课中

Greedy Algorithms

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.

Largest Number2:42

Car Fueling7:27

Car Fueling - Implementation and Analysis9:14

Main Ingredients of Greedy Algorithms2:40

与讲师见面

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering
Pavel Pevzner
Professor
Department of Computer Science and Engineering
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics

Hi, in this video you will learn to implement the greedy algorithm

from the previous video, and analyze its running time.

Here we have the pseudocode for this algorithm, and

the procedure is called MinRefills.

And the main input to this procedure is array x.

From the problems statement, we know that

the positions of the gas stations are given by numbers from x1 to xn.

And those are measured in kilometers in terms of distance from

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

For convenience, we actually add to array x positions of point

A which is x0 and is the smallest value in the array.

And point B, which is Xn plus 1, and it is the largest value in the array x.

Along our route from A to B, we will visit some points.

Of course we will start from point A.

And then we'll probably go to some gas station, refilll there.

And then go to another gas station and to another gas station and then to another

and then at some point we will get to the point B or point x n plus 1.

So we see that we only need to store the positions in the array x.

We don't need to consider any positions between the elements of array x.

And so, we will store in the variable currentRefill,

the position in the array x where we're currently standing.

And we will initialize it with 0.

Because we start from point A, which is the same as x0,

and has index 0 in the array x.

And later currentRefill will store the index in the array x,

where we're currently standing.

We'll also store the answer to our problem in the variable numRefills.

At each point in the execution of the algorithm,

it will contain the number of refills we have already made.

And we initialize it with zero because the problem statement asks us

to count the minimum number of refills we need to do.

Not counting the initial refill at point A.

So when we are standing at point A,

we consider that we haven't made any refills yet.

Then the main external while loop goes.

And it goes on while we're still to the left from point B,

because then we need to go right to reach our destination B.

And we check this condition with this inequality,

that currentRefill is at most n.

This means that the position or index in the array x is at most n, and so

we're to the left from point B currently.

In this case we still need to go to the right.

And first we save our current position in the array x in the variable lastRefill.

This means that we made our lastRefill in the position currentRefill.

And now we need to go to the right from there, and either get to destination

B or get to the rightmost reachable gas station and refill there.

And the next internal while loop does exactly that.

It gradually increases our currentRefill position in the array x until it reaches

the rightmost point in the array x which is reachable from the lastRefill position.

So first we check that currentRefill position is at most n because

if it is n plus 1 already it means that we reached our destination B.

And there is no point increasing it further.

If it's still to the left from B,

then we'll look at the next position to the right, x currentRefill plus 1.

We need to check whether it's reachable from lastRefill position or not.

And first we can build the distance from the lastRefill position to

the currentRefill plus one position by subtracting the values of the array x.

And if this distance is at most L, then it means that we can travel this

distance with full tank, without any refills.

And of course, at the lastRefill position,

we could fill our tank up to the full capacity.

And then we'll be able to travel for L kilometers.

So, this inequality checks if actually position currentRefill plus 1 is

reachable from the lastRefill position.

If it is, we increase the value of currentRefill and

go on with our internal while loop.

When we exit this internal while loop we're already maybe in the point B,

or we may be in some point which is the farthest reachable gas station.

Now we compare it with our lastRefill position.

And if it turns out that it is the same, it means that we couldn't go to the right.

We don't have enough fuel even to get to the next gas station.

And then, we cannot return the minimum number of refills that we need to do

on the way from A to B, because it is impossible to get from A to B at all.

And so we return this result IMPOSSIBLE.

Otherwise, we moved at least a bit to the right, and then we need to see.

If we are already in the point B, we don't need to do anything else.

Otherwise, we need to refill there.

So, we check that we're to the left from point B with this inequality.

And if it's true then we're at some gas station and we need to refuel.

So we increase the numRefills variable by one.

And then we return to the start of our external while loop.

And there we again check if we're to the left from point B

we need another iteration.

And if currentRefill is already n plus 1, then we've reached point B and

we need to exit the external while loop.

And in that case,

we just return the answer which is number of refills we've made so far.

We've implemented the greedy algorithm from the previous lecture.

Now let's analyze its running time.

From the first look it can seem that it works in n squared time because

we have the external while loop which can make n iterations and

internal loop which can make n iterations.

So, n by n is n squared, but actually we will show that

it only makes O of n actions for the whole algorithm.

To prove that let's first look at the currentRefill variable.

We see that it only changes one by one here.

And it starts from zero.

And what is the largest value that it can attain?

Of course, the largest value is n plus 1 because this

is the largest index in the array x, and currentRefil is index in the array x.

So, variable currentRefil starts from zero, changes one by one.

And the largest value it can have is n plus 1.

It means that it is increased at most n plus 1 times which is Big-O of n.

But that's not all we do.

Also, we increase variable numRefills here.

But we also increase it always one by one.

It also starts from zero.

And what is the largest number that this variable can attain?

Well, of course, it is n because when we have n gas stations.

There is no point to refuel twice at the same gas station.

So we can refuel at most n times.

So variable numRefills goes from 0 to n and changes one by one.

So it is only changed at most n times.

And so, it is also linear in terms of n.

And so, we have at most n plus 1 iterations of the external while loop.

Everything but the internal while loop takes there constant time.

This assignment, this if, and this if with assignment.

And the external loop and

internal loop combined also spend at most linear time of iterations.

Because they change variable currentRefill and

it changes at most linear number of times.

So all in all our algorithm works in Big-O n time.

Let's go through this proof once again.

The Lemma says that the running time of the whole algorithm is big O of n.

And we prove this by first noticing that the currentRefill

variable changes only from zero to at most n plus 1.

And the change is always one by one.

That the numRefills variable changes from zero to at most n.

And it also changes one by one.

So, both these variables are changed Big-O of n times.

And everything else that happens is constant time.

Each iteration of the external loop, and

there are at most n plus 1 iterations of the external loop.

Thus, our algorithm works in linear time.

In the next video,

we will review what we've learned about greedy algorithms in general.

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

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

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

通过 App Store 下载

通过 Google Play 获取