Review of Greedy Algorithms

Loading...

來自 University of California San Diego 的課程

Algorithmic Toolbox

3381 個評分

University of California San Diego

Algorithmic Toolbox

3381 個評分

課程 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.

Fractional Knapsack - Implementation, Analysis and Optimization6:44

Review of Greedy Algorithms2:46

與講師見面

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 lesson, we will review what we saw in this module about greedy

algorithms and specify what is common and important to all greedy algorithms.

The main ingredients of any greedy algorithm are greedy choice and

reduction to a subproblem.

You have to prove that your greedy choice is a safe move.

And also, you have to check that the problem that is left after your safe move

is really a subproblem.

That is, a problem of the same kind but with fewer parameters.

After you have both, you have a greedy algorithm.

Then, you need to estimate its running time and

check that it's good enough for you.

Safe moves in different problems are different.

Basically, you have to invent something each time you have a new problem.

In the first problem it was, select the maximum digit and put it first.

In the last problem it was select the item with the maximum total value per weight.

And you see that in every safe move, there's something like maximum,

or minimum, or first, or leftmost, or rightmost.

So, always safe move is greedy, but not all greedy moves are safe.

So, you really have to prove every time

that the move that you invented is really safe.

Also, you can notice that sometimes we can

optimize our initial greedy algorithm if we sort our object somehow.

So, you can maybe try to solve problem,

assuming that everything is sorted in some convenient order.

And if you see that, because of that,

your greedy algorithm can be implemented asymptotically faster,

then you can just apply sorting first and then your greedy algorithm.

The general strategy is when I have a problem,

you can try to come up with some greedy choices, and then for some of them,

you'll be able to prove that they're really safe moves.

And if you've proven that this is a safe move,

then you've reduced your problem to something.

And then you have to check that this something is a subproblem.

That is, the problem about the same thing,

optimizing the same thing with the same restrictions.

And then, this is a subproblem.

And then you can solve it in the same way that you solved your initial problem.

And you have this loop from problem to subproblem and

back to the problem, always reducing it by the number of parameters.

And in the end of this loop, you will have a problem so

simple that you can solve it right away for one object or zero objects.

And then you have your greedy algorithm.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

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

通過 App Store 下載

通過 Google Play 獲取