Greedy Algorithms

What is a Greedy Algorithm?

A greedy algorithm is an algorithmic technique that follows the problem-solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum.

An algorithm is designed to achieve the optimum solution for a given problem. In greedy algorithm approach, decisions are made from the given solution domain. As being greedy, the closest solution that seems to provide an optimum solution is chosen.

Greedy algorithms try to find a localized optimum solution, which may eventually lead to globally optimized solutions.

General Strategy for Greedy Algorithms

• Make a greedy choice to solve a problem.
• Prove that it is a safe move.
• Reduce to a subproblem.
• Solve the subproblem

What's a Safe Move: A greedy choice is a safe move if there is an optimal solution consistent with this first move.

What's a subproblem: It is a similar problem of smaller size.

Examples of Greedy Algorithms

Largest Number problem:

Given a list of digits (0-9), make the largest possible number using these digits. For instance List = [9, 2, 6, 3]. Largest Number = 9632.

Greedy Strategy to solve the problem:

• Find the max digit.
• Append it to the number.
• Remove it from the list of digits.
• Repeat while there are digits in the list.

Safe Move: Put max digit first is a safe greedy choice as there exists an optimal solution consistent with this move.

Solution: Initially Largest Number is " ".

1. List = [9, 2, 6, 3]. Max Digit = 9. Largest Number = 9.
2. List = [2, 6, 3]. Max Digit = 6, Largest Number = 96.
3. List = [2, 3]. Max Digit = 3. Largest Numer = 963.
4. List = [2]. Max Digit = 2. Largest Number = 9632.

Car Fuel Problem

You are traveling from point A to point B. There are a number of gas-stations from A to B. You want to reach the destination B with a minimum number of refills.

Greedy Strategy to solve the problem:

• Start at A
• Refill at the farthest reachable gas-station G from A.
• Make G the new A.
• Get from new A to B with a minimum number of refills.

Fractional Knapsack Problem

Given a set of items, each with a weight and a value, determine a subset of items to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

For Instance: Knapsack Weight = 60

Greedy Strategy to solve the problem:

• While knapsack is not full.
• Choose item i with max Vi/Wi
• If the item fits into the knapsack take all of it.
• Otherwise, take so much as to fill the knapsack
• Return total value and the amount taken.

Safe Move: Choosing the item with max Vi/Wi is a safe greedy choice as there exists an optimal solution consistent with this move.

Solution:

1. Item B is chosen as its Vi/Wi value is max = 10. Knapsack Weight becomes 60-10 = 50.
2. Item A is chosen as its Vi/Wi value is max = 7. Knapsack Weight becomes 50-40 = 10
3. Item C is chosen as its Vi/Wi value is max = 6. Cant use whole C as knapsack weight left is 10. So using only 10 units of C. Knapsack Weight becomes 10-10 = 0.
4. Knapsack is full and total value gained = 100(B) + 280(A) + 60(C) = 440.

Review of Greedy Algorithms

Main Ingredients:

• Safe Move
• Prove Safety
• Solve Subproblem
• Estimate Running Time

Note: Always safe move is greedy but not all greedy moves are safe.

Optimization:

• Assume everything is somehow sorted.
• Choose the most convenient sort order.
• Greedy moves can be faster after sorting.