A term used to describe a family of algorithms. Most algorithms try to reach some "good" configuration from some initial configuration, making only legal moves. There is often some measure of "goodness" of the solution (assuming one is found).

The greedy algorithm always tries to perform the best legal move it can. Note that this criterion is local: the greedy algorithm doesn't "think ahead", agreeing to perform some mediocre-looking move now, which will allow better moves later.

For instance, the greedy algorithm for egyptian fractions is trying to find a representation with small denominators. Instead of looking for a representation where the last denominator is small, it takes at each step the smallest legal denominator. In general, this leads to very large denominators at later steps.

The main advantage of the greedy algorithm is usually simplicity of analysis. It is usually also very easy to program. Unfortunately, it is often sub-optimal.

Log in or register to write something here or to contact authors.