Usage examples of greedy algorithms?

Question

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

Mapel

en.wikipedia.org/wiki/Algorithm#By_design_paradigm – Erinaceous

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

Oppidan

Answer 2

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

Tillotson

Optimal solutions for travelling salesman are not impossible. In fact, there are some efficient algorithms that give exact solutions for large number of cities. And there's nothing stopping a greedy algorithm from giving an optimal solution to a problem. I think your answer is a little misleading. Greedy algorithms aren't even used for the travelling salesman problem. For sub-optimal solutions you would use an approximation algorithm. -1 until you improve this. – Digestant

You could use a greedy algorithm for TSP if you just went to the next nearest unvisited city at each step. – Tillotson

but why would you do that? It can easily give the worst possible solution in the end. TSP is the perfect example of where not to use a greedy algorithm. I still disagree with your first line - if the optimal solution is very hard, I think it's better to say you would use an approximation algorithm and not a greedy algorithm. You would use greedy algorithms for problems where you can prove that they always give the optimal solution. But in any case, it was the TSP example that bugged me, so I removed the -1. – Digestant

Well it's the algorithm I use for the TSP when shopping in a supermarket! – Tillotson

@Digestant can you explain how an algorithm would give a fast and exact solution for traveling salesman? I thought the traveling salesman problem is NP-Complete. – Customary

Answer 3

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.

Helvetia

In hogwarts -- sorry, someone had to make the observation – Rheo

@drvitex: Phew, the old British system might work. 4,3,1 would be an example of a coin system that fails for 6. – Helvetia

Surprisingly, it is hard to find the optimal number of coins in general (it is NP-hard), but a polynomial algorithm exists to check if the greedy approach works. Pearson, "A polynomial-time algorithm for the change-making problem", Op. Res. Let. 33:3 (2005), pp. 231-234. DOI 10.1016/j.orl.2004.06.001 – Kacikacie

Answer 4

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

Rheo

Also, I believe LZW encryption is also greedy – Rheo

Answer 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

Set

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

Ramulose

Answer 7

Here i have listed some Greedy algorithms and their potential real world use cases.

Dijkstra's Algorithm

• IP routing to find Open shortest Path First.
• Networkrouting protocols

Find more about the real world applications of Dijkstra's algorithm here

Prim's Minimal Spanning Tree Algorithm

• Cluster Analysis.

• Real-time face tracking and verification (i.e. locating human faces in a video stream).

• Protocols in computer science to avoid network cycles.

• Entropy based image registration

• Max bottleneck paths.

• Dithering (adding white noise to a digital recording in order to reduce distortion).

Travelling Salesman Problem

• Job shop scheduling with no intermediate storage

• Clustering a data array

• Vehicle routing

Graph - Map Coloring

• Making schedule /Time table

• Sudoku

• Mobile radio Frequency Assignment

You can read about this more in this paper

Kruskal's Minimal Spanning Tree Algorithm

• TV network formation

• Tour operations

Knapsack Problem

• Used in Internet Download managers

• Real world usage of deciding what to carry in a limited package trips

Rufescent

Answer 8

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

Fieldwork

Answer 9

Application of greedy method

Prim’s Algorithm , Kruskal Algorithm

Bahaism

Answer 10

What is the use of greedy algorithms?

We use Greedy Algorithm for to get optimal solution.But all problems can't solve using greedy algorithm.

Optimal substructure property and greedy choice property are key ingredients.if we can demonstrate that the problem has these properties, then we are well on the way to developing a greedy algorithm for it.

Real examples?

• Activity sheduling problem
• Huffman code
• Coin denomination
• Single source shortest path problem (Dijkstra)
• Minimum spanning tree (Prim's algoritnm ,Kruskal's algorithm)
• Fractional Knapsack problem.

Almost all problems that can solve using Dynamic approach can be solve by greedy approach.

Spradling