tags: ADA 7.1 Greedy Algorithms

ADA 7.1: Greedy Algorithms

Textbook Chapter 16 - Greedy Algorithms
Textbook Chapter 16.2 - Elements of the greedy strategy

What is Greedy Algorithms?

• Always makes the choice that looks best at the moment
• Makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution
• DP v.s Greedy

  Dynamic Programming	Greedy Algorithms
  has optimal substructure	has optimal substructure
  make an informed choice after getting optimal solutions to subproblems	make a greedy choice before solving the subproblem
  dependent or overlapping subproblems	no overlapping subproblems

Greedy Algorithms

To yield an optimal solution, the problem should exhibit:

1. Optimal Substructure: an optimal solution to the problem contains within its optimal solutions to subproblems
2. Greedy-Choice Property: making locally optimal (greedy) choices leads to a globally optimal solution

Proof of Correctness Skills

1. Optimal Substructure:

   台大資訊 演算法 | ADA 5.1: Dynamic Programming 動態規劃

2. Greedy-Choice Property:

   • Show that it exists an optimal solution that “contains” the greedy choice using exchange argument
   • For any optimal solution OPT, the greedy choice g has two cases
     • g is in OPT: done
     • g not in OPT: modify
       $OPT$ to
       $OP{T}^{\prime }$,
       $OP{T}^{\prime }$ contains g and is at least as good as
       $OPT$