Greedy Algorithms Part 1

A greedy algorithm, as the name suggests, always makes the choice that seems to be the best at that moment. Greedy algorithms works in phases, In each phase, a decision is made that appears to be good or the best at that point in time without regard for future consequences. Generally, this means that some local optimum is chosen (The best solution from a small subset of a larger dataset). This "take what you can get now" strategy is the source of the name for this class of algorithms. The local optimum may or may not be equal to the global optimum. If it is equal, then the greedy algorithm is the best approach to solving the problem. if the absolute best answer is not required, then simple greedy algorithms are sometimes used to generate approximate answers, rather than using the more complicated algorithms. Greedy algorithms mostly (but not always) fail to find the globally optimal solution, because they usually do not operate exhaustively on all the data, they can make commitments to certain choices too early which prevent them from finding the best overall solution later

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, but fortunately, we can prove that it does work in the American monetary system. Indeed, it works even if two-dollar bills and fifty-cent pieces are allowed.

Another real life application of greedy algorithm is scheduling problem, virtually all scheduling problems are either NP-complete ( or of similar difficult complexity) or are solvable by a greedy algorithm.

All known greedy coloring algorithms for the graph coloring problem and all other NP-complete problems do not consistently find optimum solutions. Nevertheless, they are useful because they are quick to think up and often give good approximations to the optimum. For example, a greedy strategy for the traveling salesman problem (which is of a high computational complexity) is the following heuristic: "At each stage visit an unvisited city nearest to the current city". This heuristic need not find a best solution, but terminates in a reasonable number of steps; finding an optimal solution typically requires unreasonably many steps. In mathematical optimization, greedy algorithms solve combinatorial problems having the properties of matroids.