You are reading the third segment of our algorithm design patterns series. We have successfully covered the backtracking and divide-and-conquer techniques. In this article we will cover the so-called Greedy Strategy. Greedy algorithms often, but not always, yield the optimal solution in record time since they approach problem solving from a metaheuristic point of view. Thus, it is critical to master greediness.
Greedy Strategy as an Algorithm Technique - Taking a Break (Page 4 of 4 )
We’ve come to the end of this segment. Throughout this article we covered the greedy algorithm design pattern. It is one of those algorithm techniques that are definitely useful to know, whether you're a student or an experienced software developer. You cannot know in advance when it will save your day.
As a summary of everything we have learned, it is especially important to realize that the collage of local optimums does not guarantee a global optimal solution. As a result, even if you do get a solution, you need to prove (mathematically) whether or not it’s optimal. Try more than a few input sources, with the hope that you won’t get a counter-example.
There are those algorithms that cannot be solved with a simple greedy algorithm. We call these heuristic solutions because they do not stand for a global, optimal, and perfect solution which could be found with an exhaustive backtracking algorithm or with dynamic programming (we are going to cover this later in this series).
But as we discussed earlier, sometimes we settle for heuristic greedy solutions because the resource requirements for a thorough and exhaustive algorithm might be huge. In these cases it is still worthwhile to implement and code a greedy algorithm because it runs fast and is highly resource efficient. We end up with a result as quickly as possible which is usually somewhat good. It may not be the best, but hey, we don't live in a perfect world.
Knowing all of this, we know when and how to use greedy algorithms. There are particular scenarios and as always, we need to fine-tune and customize everything to our needs. There is no general rule of thumb that applies to every problem. It all comes down to software requirements. You, as a programmer, need to know the alternatives and all of the possible solutions; then you pick the one that meets your needs!
I’d like to invite you to join our experienced community of technology professionals on all areas of IT&C starting from software and hardware up to consumer electronics at Dev Hardware Forums. As well, be sure to check out the community of our sister site at Dev Shed Forums. We are friendly and we’ll do our best to help you.
DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware.