What is Greedy Algorithm?
A greedy algorithm is an algorithmic strategy that makes the best choice at every small level in order to ultimately lead to a globally optimal solution. This means that the algorithm chooses the best solution at the moment regardless of the consequences. It picks the best immediate output but doesn't consider the bigger picture, so it's considered greedy.
A greedy algorithm works by choosing the best possible answer in each step and then moving on to the next step until it reaches the end, regardless of the overall solution. It just hopes that the path it takes is the globally optimal one, but as has been proven time and again, this method is not always a globally optimal solution. Indeed, it is entirely possible that the most optimal short-term solutions will lead to the worst possible global outcome.
Imagine that there are many acronyms in a manufacturing company: In the short term, large quantities of Manufacturing costs saved, but this eventually leads to decline as quality is compromised, resulting in product returns and low sales when customers become familiar with the 'cheap' product. But that's not always the case. There are many applications in which the greedy algorithm works best to find or approximate the globally optimal solution, such as when building a Huffman tree or a decision learning tree.
For example: take the path with the largest total. A greedy algorithm would take the blue path due to myopia instead of the orange path which gives the greatest sum.
- A candidate set of data that needs a solution
- A selection function that selects the best contribution to the final solution
- A feasibility function that supports the selection function by determining whether a candidate can contribute to the solution
- An objective function that assigns a value to a partial solution
- A solution function that indicates that the optimal solution has been found