[Algorithm] Topic 9: Greedy Search

Authored by Tony Feng

Created on April 9th, 2022

Last Modified on April 9th, 2022

Understanding Greedy Search

Intro

A greedy algorithm is an approach for solving a problem by selecting the best option available at the moment.
It works in a top-down approach. It doesn’t guarantee whether the current best result will bring the overall optimal result.
We can determine if the algorithm can be used with any problem if the problem has the following properties:
- Greedy Choice Property
- Optimal Substructure

Characteristics

Advantages of Greedy Approach
- The algorithm is easier to describe.
Drawback of Greedy Approach
- The greedy algorithm doesn’t always produce the optimal solution.
- The difficult part is that for greedy algorithms you have to work much harder to understand correctness issues.
- Optimization problems (Dijkstra’s Algorithm) with negative graph edges cannot be solved using a greedy algorithm.

Steps

To begin with, the solution set (containing answers) is empty.
At each step, an item is added to the solution set until a solution is reached.
If the solution set is feasible, the current item is kept.
Else, the item is rejected and never considered again.

Template

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


# Pseudocode
Greedy(input I):
begin 
    while (solution is not complete) do
        Select the best element x in the 
            remaining input I; 
        Put x next in the output;
        Remove x from the remaining input;
    endwhile
end  

Examples

Leetcode 55 Jump Game

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        reach = 0
        for i, num in enumerate(nums):
            if i > reach:
                return False
            reach = max(reach, i + num)
        return True

Understanding Greedy Search

Intro

Characteristics

Steps

Template

Examples

Leetcode 55 Jump Game

Reference