Greedy Algorithms

Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored.

The greedy algorithm is a type of searching algorithm that is used for solving optimization problems. A locally optimum solution is found and then we hope to find the optimal solution at the global level. However, this method does not guarantee that we will be able to find an optimal solution. This method has 5 components: A candidate set, a selection function, a feasibility function, an objective function and a solution function.

A greedy algorithm requires two conditions that need to be satisfied in order for a greedy algorithm to solve the problem. They are:

1. Greedy choice property - if a global/overall optimal solution can be reached by choosing the optimal choice at each step.

2. Optimal substructure - A problem will have an optimal substructure if an optimal solution to the entire problem contains the optimal solutions to the sub-problems.

In order to make a greedy algorithm, an optimal substructure or sub-problem needs to be identified. Then, the optimal solution needs to be outlined and what it will include needs to be determined. Finally, an iterative way to go through all of the sub-problems and build a solution needs to be created.

Greedy algorithms can be 'short sighted', and also non-recoverable. They are ideal for problems that have optimal substructure. Despite this, for many simple problems, the best-suited algorithms are greedy algorithms. The greedy algorithm can be used as a selection algorithm to prioritize options within a search, or branch-and-bound algorithm.

There are variations to the greedy algorithm which are as follows:

1. Orthogonal greedy algorithms

2. Pure greedy algorithms

3. Relaxed greedy algorithms

Examples of greedy algorithms include:

1. Machine scheduling

2. Fractional Knapsack Problem

3. Huffman Code

4. Activity Selection Problem

These are the steps that a programmer needs to follow to achieve a Greedy Algorithm:

1. Feasibility: To check whether it satisfies all the possible requirements or not so that there is at least one possible solution to the problem

2. Local Optimal Choice: The choice should be optimum and is selected from the available choices

3. Inalterability: Once the decision is made, at any subsequent step, that option is not altered.

Greedy algorithms have five components:

1. A candidate set, from which a solution is created

2. A selection function, which chooses the best candidate to be added to the solution

3. A feasibility function, that is used to determine if a candidate can be used to contribute to a solution

4. An objective function, which assigns a value to a solution, or a partial solution, and

5. A solution function, which will indicate when we have discovered a complete solution

Article was written for CyberClubNPSi