Greedy Algorithm

An algorithm is a step-by-step recipe for solving a problem. A greedy algorithm might also be called a "single-minded" algorithm or an algorithm that gobbles up all of its favorites first. The idea behind a greedy algorithm is to perform a single procedure in the recipe over and over again until it can't be done any more and see what kind of results it will produce. It may not completely solve the problem, or, if it produces a solution, it may not be the very best one, but it is one way of approaching the problem and sometimes yields very good (or even the best possible) results.

Examples of greedy algorithms

Map Coloring: There is no algorithm that will produce a minimal coloring (a coloring using the fewest number of colors) for every single map, but often you can get good results by choosing one color, and coloring as many regions as possible with that color before going on to another color. You proceed with the next color in the same way, not going to a third color until there are no regions that can be colored with the second color.
If the map can be two-colored, this will always produce a two coloring. If using this procedure causes you to use four colors, you will have to look at your coloring and think about it to decide if it might be possible to use three colors instead. If you use more than four colors, you can be sure that your map can be colored with fewer colors, but your ingenuity (not the greedy algorithm) will have to show you how to do it.
Finding a dominating set or the Ice Cream Stands Problem: A dominating set is the group of vertices in a graph which have all the other vertices as neighbors, a greedy algorithm for selecting the vertices for the dominating set would be
- First, select the vertex (or vertices) with the most neighbors. (This will be the vertex (or vertices) which have the largest degree) If that makes a dominating set, stop, you are done.
- Otherwise, choose the vertices with the next largest degree, and check to see if you are done.
- Keep doing this, until you have found a dominating set, then stop.
This procedure will always produce a dominating set. Sometimes it is still possible to find a dominating set with fewer members, and sometimes it isn't. Each time that you use this greedy algorithm to find a dominating set, you will have to decide for yourself if you have found the smallest possible dominating set that can be found for that graph.