Usage examples of greedy algorithms?

问题:

What is the use of greedy algorithms? An real example?

回答1:

Minimum Spanning Tree - Prim's algorithm and Kruskal's algorithm

Shortest Path Calculation - Dijkstra's algorithm

More: (Fractional Knapsack Problem, Huffman Coding, Optimal Merging, Topological Sort).

回答2:

Some problems are such that a greedy solution will actually be optimal, and sometimes they're engineered that way. A fun example is that many countries' coin values are such that a greedy approach to returning change (i.e. always returning the largest-possible coin until you're done) works.

回答3:

Anything where an optimal solution would be impossible - or very very hard.

Greedy algorithms take the best solution at the current point, even if that's not the best solution if you examined all aternatives

回答4:

I'm surprised no one pointed out huffman / shannon encoding ...

回答5:

What is the use of greedy algorithms?

Greedy algorithms is choosing the best/optimal solution in each stage. Look at wikipedia article

An real example?

Minimum spanning tree algorithms are greedy algorithms

• Prim's algorithm
• Kruskal algorithm
• Reverse-Delete Algorithm

The famous Dijkstra's Algorithm is also greedy algorithm

回答6:

A real life example of Greedy Algorithm will be Interval Scheduling.

For example if you want to maximize the number of customers that can use a meeting room, you can use Interval Scheduling Algorithm.

回答7:

http://en.wikipedia.org/wiki/Greedy_algorithm

回答8:

Application of greedy method

Prim’s Algorithm , Kruskal Algorithm