Greedy Algorithm

A greedy algorithm is a method for solving problems by selecting the best option available at each step without considering if this choice will lead to the optimal overall solution.

The algorithm doesn’t revisit or reverse previous decisions, even if they prove to be incorrect, and it operates in a top-down manner.

This approach may not yield the best result for all problems because it focuses on making the locally optimal choice at each step in hopes of finding the global optimum.

To determine if a greedy algorithm is suitable for a problem, the problem must exhibit the following properties:

1. Greedy Choice Property

The greedy choice property refers to the ability to find an optimal solution to a problem by selecting the best option at each step, without needing to revisit or reconsider previous choices. This enables the problem to be solved using a greedy approach.

2. Optimal Substructure

The property of optimal substructure means that if the optimal solution to a problem can be derived from the optimal solutions to its subproblems, then the problem can be effectively solved using a greedy approach.

Advantages of the Greedy Approach

1. Simplicity: Greedy algorithms are usually straightforward to understand and implement.
2. Efficiency: They often have lower time complexity compared to other approaches like dynamic programming, making them faster for certain problems.
3. Local Optimality: They make locally optimal choices at each step, which can be more intuitive and easier to manage.
4. Practicality: In many cases, greedy algorithms provide sufficiently good solutions that are close to optimal, making them useful in real-world applications.
5. Reduced Memory Usage: Greedy algorithms generally use less memory since they do not need to store and revisit previous states or decisions.
6. Versatility: They can be applied to a wide range of problems, particularly those that exhibit the greedy choice property and optimal substructure.
7. Immediate Feedback: As they build the solution step by step, it’s easier to get immediate feedback on the progress and correctness of the solution.

Drawbacks of the Greedy Approach

1. Lack of Global Optimality: Greedy algorithms do not always guarantee the globally optimal solution, as they make locally optimal choices without considering the bigger picture.
2. Limited Applicability: They can only be applied to problems that exhibit the greedy choice property and optimal substructure, which limits their use.
3. Solution Quality: In some cases, the solutions provided by greedy algorithms may be far from optimal, particularly for complex or non-trivial problems.
4. Oversimplification: The simplicity of the approach can sometimes lead to oversimplified solutions that do not account for all aspects or constraints of the problem.
5. No Backtracking: Once a choice is made, greedy algorithms do not revisit or reconsider previous decisions, which can lead to suboptimal solutions if an early choice was incorrect.
6. Problem-Specific Design: Designing a greedy algorithm often requires deep insight into the problem, as the greedy choice must be carefully defined to ensure correctness.

Greedy Approach

Greedy Approach

1. Begin with the root node, which has a value of 20. The right child has a weight of 3, and the left child has a weight of 2.
2. Our objective is to find the path with the largest sum. The current best choice, according to the greedy algorithm, is 3, so we select the right child.
3. The weight of the only child of node 3 is 1, resulting in a total path weight of 20 + 3 + 1 = 24.

However, this is not the optimal solution. A different path yields a higher total weight (20 + 2 + 10 = 32), as illustrated in the image below.

Therefore, greedy algorithms do not always give an optimal/feasible solution.

Greedy Algorithm

1. Initially, the solution set (which contains the answers) is empty.
2. At each step, an item is added to the solution set until a complete solution is formed.
3. If the solution set remains feasible with the addition of the current item, the item is retained.
4. If the solution set becomes infeasible, the item is discarded and will not be reconsidered.

Now, let’s apply this algorithm to solve a problem.

Example – Greedy Approach

1. Problem Definition: Suppose we want to maximize the total value of items that can fit into a knapsack with a fixed capacity.
2. Step 1: Start with an empty knapsack (solution set).
3. Step 2: At each step, consider adding the item with the highest value-to-weight ratio that still fits into the knapsack.
4. Step 3: If adding the current item keeps the knapsack within its capacity, include the item in the solution set.
5. Step 4: If adding the current item exceeds the knapsack’s capacity, discard the item and do not consider it again.
6. Step 5: Repeat steps 2-4 until no more items can be added without exceeding the capacity.

Example Application:

• Given items with weights and values: [(2, 10), (3, 5), (5, 15)], and a knapsack capacity of 5.
• Sort items by value-to-weight ratio: [(2, 10), (5, 15), (3, 5)].
• Add the first item (2, 10): Current weight = 2, Current value = 10.
• Add the second item (5, 15): Exceeds capacity, discard.
• Add the third item (3, 5): Current weight = 5, Current value = 15.
• The optimal solution using the greedy approach is a total value of 15 with items (2, 10) and (3, 5).

This demonstrates the greedy approach, where locally optimal choices lead to a feasible solution, although not always the globally optimal one.

Different Types of Greedy Algorithms

1. Activity Selection Problem:

• Objective: Select the maximum number of activities that don’t overlap.
• Greedy Choice: Always pick the next activity that finishes the earliest.

1. Fractional Knapsack Problem:

• Objective: Maximize the total value of items that can fit into a knapsack with a fixed capacity.
• Greedy Choice: Choose the item with the highest value-to-weight ratio first, and take as much as possible of it.

1. Huffman Coding:

• Objective: Compress data by creating a prefix-free binary code with minimum length.
• Greedy Choice: Build the tree by always combining the two nodes with the lowest frequency.

1. Prim’s Algorithm:

• Objective: Find the minimum spanning tree of a graph.
• Greedy Choice: Always add the smallest edge that connects a new vertex to the growing spanning tree.

1. Kruskal’s Algorithm:

• Objective: Find the minimum spanning tree of a graph.
• Greedy Choice: Always add the smallest edge that doesn’t form a cycle with the already included edges.

1. Dijkstra’s Algorithm:

• Objective: Find the shortest path from a source node to all other nodes in a weighted graph.
• Greedy Choice: Always expand the shortest known path to a new vertex.

1. Job Sequencing Problem:

• Objective: Maximize profit from a set of jobs with deadlines and profits.
• Greedy Choice: Always schedule the job with the highest profit first if it can be completed within its deadline.

1. Interval Scheduling Maximization:

• Objective: Select the maximum number of non-overlapping intervals.
• Greedy Choice: Always pick the interval that ends the earliest.

1. Coin Change Problem:

• Objective: Make a certain amount using the least number of coins.
• Greedy Choice: Always pick the highest denomination coin that is less than or equal to the remaining amount.

1. Set Cover Problem:
   • Objective: Cover all elements with the minimum number of subsets.
   • Greedy Choice: Always pick the subset that covers the largest number of uncovered elements.

Each of these problems leverages a greedy strategy to build up a solution incrementally, ensuring that each step is locally optimal.

Read More…

Heap and Hash : An Overview – https://kamleshsingad.com/heap-and-hash-an-overview/

Understanding SQL Joins: A Comprehensive Guide – https://kamleshsingad.com/understanding-sql-joins-a-comprehensive-guide/

Top 10 SQL Programming Tips for Beginners – https://kamleshsingad.com/top-10-sql-programming-tips-for-beginners/