15

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

Nathan Osman
  • 71,149
  • 71
  • 256
  • 361
Antonio Barra
  • 249
  • 1
  • 3
  • 7

10 Answers10

20

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

Sonny Saluja
  • 7,193
  • 2
  • 25
  • 39
8

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

Martin Beckett
  • 94,801
  • 28
  • 188
  • 263
  • 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. – IVlad Feb 01 '11 at 21:05
  • 1
    You could use a greedy algorithm for TSP if you just went to the next nearest unvisited city at each step. – Martin Beckett Feb 01 '11 at 21:30
  • 1
    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. – IVlad Feb 01 '11 at 21:35
  • 1
    Well it's the algorithm I use for the TSP when shopping in a supermarket! – Martin Beckett Feb 01 '11 at 23:22
  • @IVlad 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. – Vlad the Impala Dec 22 '14 at 22:22
8

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.

Ulrich Schwarz
  • 7,598
  • 1
  • 36
  • 48
  • In hogwarts -- sorry, someone had to make the observation – Foo Bah Feb 02 '11 at 01:37
  • @drvitex: Phew, the old British system might work. 4,3,1 would be an example of a coin system that fails for 6. – Ulrich Schwarz Feb 02 '11 at 05:29
  • 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 – vonbrand Apr 26 '19 at 19:24
7

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

Foo Bah
  • 25,660
  • 5
  • 55
  • 79
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

The famous Dijkstra's Algorithm is also greedy algorithm

2

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.

skndmx
  • 381
  • 1
  • 3
  • 4
1

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

Sarangan
  • 868
  • 1
  • 8
  • 24
0

Application of greedy method

Prim’s Algorithm , Kruskal Algorithm

LittleGirl
  • 658
  • 6
  • 26
0

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

Mikhail
  • 8,692
  • 8
  • 56
  • 82
0

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.

Kavishka Gamage
  • 102
  • 2
  • 10