Tech Corner
How will facial recognition systems & algorithms work in 2023?
Facial Recognition Systems first detect faces. They then get into feature extraction, next, they classify faces. Learn how these systems and algorithms work!
Greedy algorithms are algorithms that take the best, immediate, or local, solution while looking for an answer. They identify the globally (overall) optimal solution for certain optimization problems but might identify less-than-optimal solutions for certain instances of other problems. It follows the problem-solving heuristic of making the locally optimal choice at every stage.
It is essentially a mathematical process that, by deciding which next step will provide the most obvious benefit, hunts for simple solutions (which are easy to implement) to complicated, multi-step problems.
They are known as greedy algorithms because even though finding an optimal solution for every smaller instance will give you an instant output, the algorithm does not take the larger problem into account. It never reconsiders any decisions after they are made.
These greedy algorithms function by constructing a set of objects from the smallest possible constituent parts in a recursive manner. In recursion, the solution to a specific problem depends on the solutions to smaller instances of the same problem.
One major benefit of employing a greedy algorithm is that solutions to smaller instances of the problem tend to be straightforward and rather easily understandable.
There are two conditions that define the greedy paradigm:
Every stepwise solution needs to structure a problem towards its best-accepted solution.
It is sufficient if the structuring of the problem could stop in a finite number of greedy steps.
%20(1)%20(1)-min.jpg)
Greedy algorithms tend to be made up of five components. These components include:
Greedy algorithms find optimal solutions for some mathematical problems but not for some others. Here are the properties that the problems for which they do work tend to have.
This involves making the choice that seems the most appropriate at the time and then solving the subproblems that surface later. The choice made by a greedy algorithm could depend on choices made up to that point, but it will not depend on future choices or on all the solutions to the subproblem.
The algorithm iteratively makes greedy choice after greedy choice, thus shrinking each given problem into a smaller one. Basically, as mentioned earlier, a greedy algorithm will never reconsider its choices.
This is the biggest way in which it is different from dynamic programming which happens to be exhaustive and will definitely find the solution. After each stage, dynamic programming makes decisions based on all the decisions that were taken in the previous stage and it might reconsider the previous stage's algorithmic path to the solution.
A problem has an optimal substructure in a case where an optimal solution to the problem contains optimal solutions to the sub-problems. This implies that it is possible to solve subproblems and build up the solutions to solve larger problems.
Get your WhatsApp chatbot at just $5 a day
Start nowThe characteristics of greedy algorithm are:
As an example, in the fractional knapsack problem, the maximum value or weight is taken first according to the capacity that is available.
Greedy algorithms can be used to find optimal solutions in problems like Activity selection, Fractional Knapsack, Job Sequencing, and Huffman Coding. It can also be used to find ‘close to optimal’ solutions in N-P Hard problems like the Traveling Salesman Problem (TSP).
Here are some reasons why you would want to use the greedy approach:
The most significant advantages of using greedy algorithms are:
The biggest drawback involved with making use of greedy algorithms is that it is very possible that the local optimal solution might not always be the global optimal solution.
There are two ways to prove that a greedy algorithm is optimal. They are:
Using a ‘Greedy stays ahead’ argument is one of the simplest methods to prove that a greedy algorithm is correct. It shows that according to some measure, the greedy algorithm always is at least as far ahead as the optimal solution during each iteration of the algorithm. This fact can be used to prove that the greedy algorithm is optimal.
This is a rather versatile technique. It essentially shows you that it is possible for you to iteratively transform any optimal solution into the solution produced by the greedy algorithm without making any change to the cost of the optimal solution, thus proving that the greedy solution is optimal.