A greedy algorithm is a problem-solving approach that builds a solution incrementally, step by step, always choosing the option that appears to offer the most immediate benefit or optimal solution at each step. This choice is made without considering the broader consequences or potential future outcomes.
Characteristics of Greedy Algorithms
1. Greedy Choice Property:
– A locally optimal choice at each step leads to a globally optimal solution.
2. Optimal Substructure:
– The problem can be broken down into smaller subproblems, and the solution to the entire problem can be constructed efficiently from the solutions to these subproblems.
Steps in a Greedy Algorithm
1. Initialization: Start with an empty solution set or a trivial initial state.
2. Selection: At each step, select the best option (greedy choice) based on a specific criterion.
3. Feasibility: Ensure the selected option satisfies the problem’s constraints.
4. Inclusion: Add the chosen option to the current solution.
5. Repeat: Continue until the solution is complete.
Examples of Problems Solved Using Greedy Algorithms
1. Activity Selection Problem
– Goal: Select the maximum number of activities that do not overlap.
– Greedy Choice: Always select the activity that ends the earliest.
2. Fractional Knapsack Problem
– Goal: Maximize the total value of items that can fit in a knapsack of limited capacity.
– Greedy Choice: Choose the item with the highest value-to-weight ratio.
3. Huffman Coding
– Goal: Create an optimal binary tree for data compression.
– Greedy Choice: Merge the two nodes with the smallest frequencies.
4. Prim’s Algorithm
– Goal: Find the minimum spanning tree of a graph.
– Greedy Choice: Add the smallest edge that connects a vertex to the growing tree.
5. Dijkstra’s Algorithm
– Goal: Find the shortest path from a source to all other vertices in a graph.
– Greedy Choice: Select the vertex with the smallest known distance.
Advantages
– Simple to implement.
– Efficient for problems with the greedy choice property and optimal substructure.
– Fast and uses less memory compared to other approaches like dynamic programming.
—
Disadvantages
– Not always optimal for all problems.
– Fails for problems that require considering future consequences of decisions.
—
When to Use Greedy Algorithms
Greedy algorithms work well when:
1. The problem has the greedy choice property.
2. The problem exhibits optimal substructure.
Example: Coin Change Problem
Find the minimum number of coins needed to make a given amount using denominations.
Greedy Solution:
python
def coin_change(coins, amount):
coins.sort(reverse=True) # Sort coins in descending order
count = 0
for coin in coins:
while amount >= coin:
amount -= coin
count += 1
return count
coins = [1, 5, 10, 25]
amount = 63
print(coin_change(coins, amount)) # Output: 6 (25+25+10+1+1+1)Note:
This works only if the denominations are suited for a greedy approach.
