A greedy algorithm is an algorithm that always selects the optimal local choice. The greedy algorithms approach suggests constructing a solution through a sequence of steps, each expanding a partially constructed solution obtained until a complete solution to the problem is reached. It’s important to note that greedy algorithms can work for some problems but fail others.
A greedy algorithm is based on a problem-solving method involving making fundamental optimal decisions at each stage to achieve a global optimum. That means, at each stage, we choose a locally optimal value in the hopes of arriving at the optimum possible result.
This algorithm is an optimization technique that can find either minimum or maximum optimum results. The super best part about this algorithm is that it is simple to understand and implement; additionally, the runtime complexity for this algorithm is pretty reasonable.
For each stage, the choice made must be:
- feasible, meaning it only has to satisfy the problem’s constraints
- locally optimal, meaning it has to be the best local choice among all possible options available on that step
- irrevocable, meaning once made, it cannot be changed on subsequent algorithm steps.
For example, A typical example is a database query optimizer that is required to find the optimal access graph for a given query. It may have many millions of possibilities to estimate and evaluate as part of the query execution, but the question must be completed in a reasonable timescale (that is the whole point of query optimization, after all.)
Therefore, the optimizer may pick only a handful of the best possibilities so far for the subsequent evaluation stage at each evaluation stage. As a result, the optimal access graph may not have been chosen, but a good enough path will likely have been selected as quickly as possible.
Why do we need greedy algorithms?
We use algorithms to solve problems, so the need for a type of algorithm will depend on the issue. For instance, some techniques do not work for some situations. The ones that work best with this strategy have the so-called greedy choice property.
- Greedy algorithms are very nice when you can prove that the algorithm produces either a near-optimal solution (within some factor usually) or always guarantee an optimal solution. Greedy algorithms have an intuitive strategy that most could understand.
- Greedy algorithms also tend to be simple to implement and efficient.
- Greedy algorithm design is a prominent technique because plenty of classic optimization problems have the structure that permits this strategy to work well.
- Some examples (among many) are the minimum spanning tree problem, the coin-change problem (for certain denominations), and the shortest path problem.
- These algorithms don’t always work well, but sometimes you get lucky and can prove the problem has the structure that allows you to either find the exact optimum or a feasible solution whose value is within a particular optimum factor.
Steps for creating a greedy algorithm
Following these steps, you can find a greedy algorithm for any problem.
- In every big problem, find a subproblem or substructure.
- Observe what the solution will include (largest or shortest path)
- Create an interactive process for going through all minor problems with an effective solution.
For example, imagine that tomorrow morning you have your semester exams and haven’t studied anything. You are left with only 3 hours and have ten lessons to learn. What do you do? You shall decide to use these 3 hours to the full extent to get the maximum possible marks. What you do in these 3 hours is nothing but a Greedy algorithm because you are greedy about getting marks!
You cannot study all ten lessons in 3 hours, so you suddenly compute an average of 45 mins required for each lesson and plan to study 4 lessons. Now the actual task is to choose the four lessons and the order in which you will learn.
Since you have no idea of the syllabus, you call your topper friend and get a fair idea of which lessons are challenging and easy and start studying. And finally, you have studied 4 (random) lessons. Your way would be like choosing the next hardest lesson unstudied and learning it.
And in between, your friend asked you to solve some numerical problems, which you avoided by giving a fake excuse because you are greedy about getting marks.
Now, after you have given the exams, you discuss them with your friends and come to know that.
- There are some repeated topics (which you have skipped), so studying those topics is equivalent to studying two subjects.
- Some lessons require prerequisites of some other studies (which also you skipped and had a hard time understanding).
- You also find that there is a problem in the paper which is similar to the question that your friend has asked and you missed.
Finally, you regret that you could have studied more optimally and envy your friend who has reviewed more than you at the same time.
Applications of Greedy algorithm
Here are a few applications of the greedy algorithm:
- Used for constructing spanning trees: Prim’s and Kruskal’s algorithms are used to design minimum spanning trees which are greedy algorithms.
- Used to implement Huffman encoding: A greedy algorithm is used to build a Huffman tree connecting a given image which compresses a spreadsheet or video into a lossless compressed life.
- Used to solve optimization problems: Graphs, map coloring, vertex cover, Knapsack, job scheduling problem, and activity selection problem are classic problems used while solving a greedy algorithm.
Conclusion
In this greedy algorithm, you saw various stages, from knowing the meaning with examples to applications. The measure made the study work more quantity over quality time, which is needed. Simplilearn online learning is a platform that provides software development courses which is the right platform to master the art of software development.
The course is the perfect catalog to improve software development and be a better person tomorrow.
