Greedy Algorithm

The greedy algorithm is simple and very intuitive and is very successful in solving optimization and minimization problems. The greedy algorithm makes the optimal choice in each step of the solution and thereby making the result more optimized.

Let’s discuss the working of the greedy algorithm. The greedy algorithm involves three sets – the candidate set which contains all the elements, the selection set in which the elements are placed when they are selected from the candidate set on basis of the criteria, and the rejection set which contains the elements from the candidate set that was not able to fulfill the criteria.

The elements of the candidate set will either go in the selection set or the rejection set.

When the choices are optimal and the elements that are selected form the candidate set may lead to the results we form the solution and the set of these selections becomes the selection set.

Both selection and the rejection set contains some of the elements of the candidate set but not all the elements.

When all the elements are categorized in either the rejection or the selection set then we have to stop the procedure of categorization because at that time it may have exhausted the candidate set.

When we add all the elements of the selection and rejection set, therefore, the union of the selection and the rejection set will give us the candidate set. And their intersection will form the null set.

The most important set in the above three sets is the selection set.

To form the selection set we have to follow a particular formation, this is done with the help of some function that is the selection function and the feasibility function.

Selection Function selects an optimal value in every step which exhibits greedy choice property,  the selection function gives the element from the candidate set which is of the highest value.

The feasibility function checks whether the chosen value can become part of the solution or not.

With the selection set, we select the elements which are of the highest value with the greedy choice property.  And with the feasibility function, we can determine whether the solution we have opted with the help of the selection set can form the solution that is taken care by the feasibility function, if the element that came from the selection set passes the feasibility function it becomes the part of the selection set and if the value does not cohere with the solution than the elements will be placed in the rejection set.

When all the elements have passed these two functions and the elements have been put in either of the rejection set or the selection set, the process is then put to the end.

Uses of the greedy method

The problem is we do not have any particular and definite algorithm. The greedy method can help us find out the approximate solution only but not the perfect solution.

Various places were greedy algorithms that come into use.

Minimum spanning tree – to convert a graph into a tree or removing the loops from the graphs which make it into the tree the two best algorithms which are used is the Krushkal and the prisms algorithm.

Single-source shortest paths like the Dijkstra algorithm which help to find the fastest and the shortest path from one node to another node these are much used in the routing the data packets in the network, devising the single-source shortest path helps to reduce the metric or find the minimum metric which will help to reduce the resources used.

Simple scheduling problems, where like say for example the doctor’s clinic the doctor wants to maximize the patient that he can see per day,  with the increased patients the doctor can maximize the profits.

Knapsack problem, here we maximize the profit earned, there is no particular algorithm that is not good enough therefore the greedy approach is applied here.

What makes greedy algorithms better than other algorithms?

The lesser number of tradeoffs that occur in the solution makes it more suitable for the optimization problem.

The other reason for using the greedy algorithm is its approach of dividing the problem recursively and with no requirement to combine the problem.

Also, it can achieve a solution immediately. In greedy algorithms, if more solutions can be done before the finishing of the main solution, then the side activities can be performed at the same time.

There are some places where the greedy algorithm approach can lead to the worst-case possible. The problem involves division of the main problem into simpler subproblems like those in sorting and then combining those subproblem solutions to form the main solution. In such a case scenario the greedy problem approach can even lead to a non-optimal solution.

 

Leave a Reply

Your email address will not be published. Required fields are marked *