Greedy Algorithm
Greedy Algorithm"Definition: An algorithm which always takes the best immediate, or local, solution while finding an answer. Greedy algorithms will always find the overall, or globally, optimal solution for some optimization problems, but may find less-than-optimal solutions for some instances of other problems."
(from http://www.nist.gov/dads/HTML/greedyalgo.html)
It is sometimes insisted that the 'local' solution is 'extended' rather than wholly revamped by a greedy algorithm as it progresses towards a global solution.
A classic example is the minimum spanning tree problem in GraphTheory.
For some problems, a local maximum is sufficient, so a "hill climbing" algorithm will suffice. Wherever you are, test your neighborhood, go to the neighboring position with the highest value, and repeat.
For some problems, the response surface can be proven to have no local maxima other than global maxima. Imagine if you draped an entire mountain range with a blanket, then pulled the hem down evenly everywhere. The Hill Climbing Algorithm will now take you up the blanket to the highest peak.
For some problems, finding a local maximum is a good first step to finding the global maximum. The allegory here is carrying an ultralight up to the local peak. Or carrying a canoe to the local maximum, then flooding the entire world to make this maximum the new sea level.
So Greed Is Good. -- PhlIp
Sometimes, yes. Others you can't improve your situation using greed.
Examples of GreedyAlgorithms:
EditText of this page
(last edited September 6, 2007)
or FindPage with title or text search