Greedy Algorithms

Advertisemen

I can't find a pen, so I'm going to have to write notes here!

Properties of a greedy algorithm:

• Makes the choice that looks best at the current time - this is a locally optimal choice in the hope that this leads to a globally optimal choice.
• They do not always yield optimal solutions, but for many problems they do.

The greedy method involves creating a solution through a sequence of steps.

On each step the choice made must be:

• Feasible - it has a satisfy the problem constraints
• Optimal (at least locally) - it has to be the best choice among all the feasible choices
• Irrevocable - once a choice has been made, it cannot be changed in the later steps of the algorithm

This greedy method works best when it is applied to problem with the greedy-choice property:
"a globally optimal solution can be obtained by from a series of local improvements from starting solution set."

That is, the greedy method suggests that one can devise an algorithm which works in stages, considering one input at a time. At each stage the locally optimal choice is made, which, when the problem is solved, create a globally optimal solution.

A more formal definition of the greedy method is:

• Given n inputs, choose a subset that satisfies the problem's constraints
• A subset that satisfies the constraints is feasible solution 
• A feasible solution that maximises or minimises a function is optimal

Often a feasible solution can be found easily but the optimal solution is difficult to find

(Adapted from M. Manjunathaiah SE2EA11 lecture notes, Introduction to Algorithms 1997, Fundamentals of Computer Algorithms 1978)

Advertisemen