The greedy algorithm and implementation

问题:

Hello I've just started learning greedy algorithm and I've first looked at the classic coin changing problem. I could understand the greediness (i.e., choosing locally optimal solution towards a global optimum.) in the algorithm as I am choosing the highest value of coin such that the sum+{value of chosen coin}<=total value . Then I started to solve some greedy algorithm problem in some sites. I could solve most of the problems but couldn't figure out exactly where the greediness is applied in the problem. I coded the only solution i could think of, for the problems and got it accepted. The editorials also show the same way of solving problem but i could not understand the application of greedy paradigm in the algorithm.

Are greedy algorithms the only way of solving a particular range of problems? Or they are one way of solving problems which could be more efficient?

Could you give me pseudo codes of a same problem with and without the application of greedy paradigm?

回答1:

I think that there is always another way to solve a problem, but sometimes, as you've stated, it probably will be less efficient.

For example, you can always check all the options (coins permutations), store the results and choose the best, but of course the efficiency is terrible.

Hope it helps.

回答2:

Greedy algorithms are just a class of algorithms that iteratively construct/improve a solution.

Imagine the most famous problem - TSP. You can formulate it as Integer Linear Programming problem and give it to an ILP solver and it will give you globally optimal solution (if it has enought time). But you could do it in a greedy way. You can construct some solution (e.g. randomly) and then look for changes (e.g. switch an order of two cities) that improve your solution and you keep doing these changes until there is no such change possible.

So the bottom line is: greedy algorithms are only a method of solving hard problems efficiently (in time, but not necessary in the quality of solution), but there are other classes of algorithms for solving such problems.

回答3:

For coins, greedy algorithm is also the optimal one, therefore the "greediness" is not as visible as with some other problems.

In some cases you prefer solution, which is not the best one, but you can compute it much faster (computing the real best solution can takes years for example).

Then you choose heuristic, that should give you the best results - based on average input data, its structure and what you want to want to accomplish.

On wikipedia, there is good solution on finding the biggest sum of numbers in tree

Imagine that you have for example 2^1000 nodes in this tree. To find optimal solution, you have to visit each node once. Personal computer today is not able to do this in your lifetime, therefore you want some heuristic. Greedy alghoritm however find solution in just 1000 steps (which does not take more than one milisecond)

回答4:

There are lots of real life examples of greedy algorithms. One of the obvious is the coin changing problem, to make change in a certain currency, we repeatedly dispense the largest denomination, thus , to give out seventeen dollars and sixty one cents in change, we give out a ten-dollar bill, a five-dollar bill, two one-dollar bills, two quarters , one dime, and one penny. By doing this, we are guaranteed to minimize the number of bills and coins. This algorithm does not work in all monetary systems...more here