Data Structures and Algorithms Spring 2022
Instructor: Chunhao Wang
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 1 / 18
Copyright By PowCoder代写 加微信 powcoder
Greedy algorithms
Greedy algorithms Warm-up
Greedy algorithms
“Greedy . . . is good. Greedy is right. Greedy works.”
— Wall Street
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 2 / 18
Warm-up example: Dijkstra’s algorithm (I)
Chunhao Wang
CMPSC 465 Spring 2022
Mar 3, 2022
Warm-up example: Dijkstra’s algorithm (II)
AC B3 D6 E7
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 4 / 18
Warm-up example: Dijkstra’s algorithm (III)
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 5 / 18
Warm-up example: Dijkstra’s algorithm (IV)
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 6 / 18
How to design a greedy algorithm?
Key step (the greedy heuristic)
View the problem as one where a sequence of choices are made,
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 7 / 18
How to design a greedy algorithm?
Key step (the greedy heuristic)
View the problem as one where a sequence of choices are made, and each choice leaves a single subproblem to solve
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 7 / 18
How to design a greedy algorithm?
Key step (the greedy heuristic)
View the problem as one where a sequence of choices are made, and each choice leaves a single subproblem to solve
Question: do greedy algorithms always work?
i.e. do they always produce the optimal solution?
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 7 / 18
A failure example (I)
0-1 Knapsack Problem
A Thief has a backpack with certain capacity. There is a set of items with certain weight and value.
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 8 / 18
A failure example (I)
0-1 Knapsack Problem
A Thief has a backpack with certain capacity. There is a set of items with certain weight and value. Goal: pack the backpack with the largest value
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 8 / 18
A failure example (I)
0-1 Knapsack Problem
A Thief has a backpack with certain capacity. There is a set of items with certain weight and value. Goal: pack the backpack with the largest value
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 8 / 18
A failure example (II)
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 9 / 18
A failure example (II)
Greedy heuristic:
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 9 / 18
A failure example (II)
Greedy heuristic: always pick the item with the highest value/weight
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 9 / 18
A failure example (II)
Greedy heuristic: always pick the item with the highest value/weight Greedy solution:
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 9 / 18
A failure example (II)
Greedy heuristic: always pick the item with the highest value/weight Greedy solution: A, B total value: $160
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 9 / 18
A failure example (II)
Greedy heuristic: always pick the item with the highest value/weight Greedy solution: A, B total value: $160
Better solutions?
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 9 / 18
A failure example (II)
Greedy heuristic: always pick the item with the highest value/weight Greedy solution: A, B total value: $160
Better solutions?
• B, C total value: $220
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 9 / 18
A failure example (II)
Greedy heuristic: always pick the item with the highest value/weight Greedy solution: A, B total value: $160
Better solutions?
• B, C total value: $220 • A, C total value: $180
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 9 / 18
Greedy choice
In order for the greedy heuristic to work, the problem should have the following property
Greedy choice property
There exists an optimal solution that makes the greedy choice
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 10 / 18
Greedy choice
In order for the greedy heuristic to work, the problem should have the following property
Greedy choice property
There exists an optimal solution that makes the greedy choice
Or: the current greedy choice is contained in some optimal solution
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 10 / 18
Greedy choice
In order for the greedy heuristic to work, the problem should have the following property
Greedy choice property
There exists an optimal solution that makes the greedy choice
Or: the current greedy choice is contained in some optimal solution The greedy choice property shows that “the greedy choice is safe”
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 10 / 18
Greedy choice
In order for the greedy heuristic to work, the problem should have the following property
Greedy choice property
There exists an optimal solution that makes the greedy choice
Or: the current greedy choice is contained in some optimal solution The greedy choice property shows that “the greedy choice is safe”
However, it won’t guarantee that make a sequence of greedy choices leads to an optimal solution
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 10 / 18
Greedy choice
In order for the greedy heuristic to work, the problem should have the following property
Greedy choice property
There exists an optimal solution that makes the greedy choice
Or: the current greedy choice is contained in some optimal solution The greedy choice property shows that “the greedy choice is safe”
However, it won’t guarantee that make a sequence of greedy choices leads to an optimal solution
The 0-1 Knapsack problem fails in this property
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 10 / 18
Another failure example
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 11 / 18
Maximum weighted path
Given a graph with edge weights, and given two vertices. Find a path between them with the maximum total weight
Another failure example
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 11 / 18
Maximum weighted path
Given a graph with edge weights, and given two vertices. Find a path between them with the maximum total weight
Another failure example
MaxWeightedPath(A,C)=3 (A−D−E−C)
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 11 / 18
Maximum weighted path
Given a graph with edge weights, and given two vertices. Find a path between them with the maximum total weight
Another failure example
MaxWeightedPath(A,C)=3 (A−D−E−C) However, MaxWeightedPath(A, C ) ̸=
MaxWeightedPath(A,D)+MaxWeightedPath(D,C)
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 11 / 18
Maximum weighted path
Given a graph with edge weights, and given two vertices. Find a path between them with the maximum total weight
Another failure example
MaxWeightedPath(A,C)=3 (A−D−E−C) However, MaxWeightedPath(A, C ) ̸=
MaxWeightedPath(A,D)+MaxWeightedPath(D,C)
Global optimal cannot be obtained by combining local optima
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 11 / 18
Maximum weighted path
Given a graph with edge weights, and given two vertices. Find a path between them with the maximum total weight
Optimal substructure
In order for the greedy heuristic to work, the problem should also have the following property
Optimal substructure property
An optimal solution to the problem contains within it the optimal solutions to the subproblems
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 12 / 18
Optimal substructure
In order for the greedy heuristic to work, the problem should also have the following property
Optimal substructure property
An optimal solution to the problem contains within it the optimal solutions to the subproblems
Or: solutions to subproblems can be combined to the global optimal solution
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 12 / 18
Optimal substructure
In order for the greedy heuristic to work, the problem should also have the following property
Optimal substructure property
An optimal solution to the problem contains within it the optimal solutions to the subproblems
Or: solutions to subproblems can be combined to the global optimal solution
The maximum weighted path problem fails in this property
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 12 / 18
Summary of greedy algorithms
• Design a greedy algorithm: find a greedy heuristic
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 13 / 18
Summary of greedy algorithms
• Design a greedy algorithm: find a greedy heuristic
• View the problem as one where a sequence of choices are made, and
each choice leaves a single subproblem to solve
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 13 / 18
Summary of greedy algorithms
• Design a greedy algorithm: find a greedy heuristic
• View the problem as one where a sequence of choices are made, and
each choice leaves a single subproblem to solve
• To prove this greedy algorithm yields an optimal solution:
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 13 / 18
Summary of greedy algorithms
• Design a greedy algorithm: find a greedy heuristic
• View the problem as one where a sequence of choices are made, and
each choice leaves a single subproblem to solve
• To prove this greedy algorithm yields an optimal solution:
• Prove this problem has the greedy choice property w.r.t. the greedy heuristic
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 13 / 18
Summary of greedy algorithms
• Design a greedy algorithm: find a greedy heuristic
• View the problem as one where a sequence of choices are made, and
each choice leaves a single subproblem to solve
• To prove this greedy algorithm yields an optimal solution:
• Prove this problem has the greedy choice property w.r.t. the greedy heuristic
• Prove this problem has the optimal substructure property
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 13 / 18
Greedy algorithms
Minimum Spanning Tree
Minimum Spanning Tree (MST)
The Minimum Spanning Tree Problem (MST)
Input: undirected graph G = (V,E) with edge weights we ∈ R,∀e ∈ E.
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 14 / 18
Minimum Spanning Tree (MST)
The Minimum Spanning Tree Problem (MST)
Input: undirected graph G = (V,E) with edge weights we ∈ R,∀e ∈ E. Output: A tree T = (V,E′) s.t.
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 14 / 18
Minimum Spanning Tree (MST)
The Minimum Spanning Tree Problem (MST)
Input: undirected graph G = (V,E) with edge weights we ∈ R,∀e ∈ E. Output: A tree T = (V,E′) s.t.
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 14 / 18
Minimum Spanning Tree (MST)
The Minimum Spanning Tree Problem (MST)
Input: undirected graph G = (V,E) with edge weights we ∈ R,∀e ∈ E. Output: A tree T = (V,E′) s.t.
2. E′ minimizes weight(T) = e∈E′ we
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 14 / 18
Greedy approach for MST
View the problem as one where a sequence of choices are made, and each choice leaves a single subproblem to solve
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 15 / 18
Greedy approach for MST
View the problem as one where a sequence of choices are made, and each choice leaves a single subproblem to solve
Greedy heuristic: add the lightest edge that doesn’t induce a cycle
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 15 / 18
Greedy approach for MST
View the problem as one where a sequence of choices are made, and each choice leaves a single subproblem to solve
Greedy heuristic: add the lightest edge that doesn’t induce a cycle Example:
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 15 / 18
Greedy approach for MST
View the problem as one where a sequence of choices are made, and each choice leaves a single subproblem to solve
Greedy heuristic: add the lightest edge that doesn’t induce a cycle Example:
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 15 / 18
Greedy approach for MST
View the problem as one where a sequence of choices are made, and each choice leaves a single subproblem to solve
Greedy heuristic: add the lightest edge that doesn’t induce a cycle Example:
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 15 / 18
Greedy approach for MST
View the problem as one where a sequence of choices are made, and each choice leaves a single subproblem to solve
Greedy heuristic: add the lightest edge that doesn’t induce a cycle Example:
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 15 / 18
Greedy approach for MST
View the problem as one where a sequence of choices are made, and each choice leaves a single subproblem to solve
Greedy heuristic: add the lightest edge that doesn’t induce a cycle Example:
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 15 / 18
Greedy approach for MST
View the problem as one where a sequence of choices are made, and each choice leaves a single subproblem to solve
Greedy heuristic: add the lightest edge that doesn’t induce a cycle Example:
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 15 / 18
Greedy approach for MST
View the problem as one where a sequence of choices are made, and each choice leaves a single subproblem to solve
Greedy heuristic: add the lightest edge that doesn’t induce a cycle Example:
weight(T ) = 14
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 15 / 18
Greedy approach for MST
View the problem as one where a sequence of choices are made, and each choice leaves a single subproblem to solve
Greedy heuristic: add the lightest edge that doesn’t induce a cycle Example:
weight(T ) = 14 Optimality?
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 15 / 18
Greedy approach for MST
View the problem as one where a sequence of choices are made, and each choice leaves a single subproblem to solve
Greedy heuristic: add the lightest edge that doesn’t induce a cycle Example:
weight(T ) = 14
Optimality?
We need to show greedy choice and optimal substructure
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 15 / 18
Optimality of greedy (I)
Some technical preliminaries
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 16 / 18
Optimality of greedy (I)
Some technical preliminaries
Definition
ApartitionofasetV isintheform(A,B)whereA∪B=V and A∩B=∅
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 16 / 18
Optimality of greedy (I)
Some technical preliminaries
Definition
ApartitionofasetV isintheform(A,B)whereA∪B=V and A∩B=∅
Definition
For an undirected graph G = (V,E), a cut is a partition of V
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 16 / 18
Optimality of greedy (I)
Some technical preliminaries
Definition
ApartitionofasetV isintheform(A,B)whereA∪B=V and A∩B=∅
Definition
For an undirected graph G = (V,E), a cut is a partition of V
({A,B,C},{D,E})
({A,B},{D,E})
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 16 / 18
Optimality of greedy (I)
Some technical preliminaries
Definition
ApartitionofasetV isintheform(A,B)whereA∪B=V and A∩B=∅
Definition
For an undirected graph G = (V,E), a cut is a partition of V
({A,B,C},{D,E}) is a cut
({A,B},{D,E})
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 16 / 18
Optimality of greedy (I)
Some technical preliminaries
Definition
ApartitionofasetV isintheform(A,B)whereA∪B=V and A∩B=∅
Definition
For an undirected graph G = (V,E), a cut is a partition of V
({A,B,C},{D,E}) is a cut
({A,B},{D,E}) is a not a cut
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 16 / 18
Optimality of greedy (II)
Definition
A cut (S, V − S) respects A ⊆ E if ∀(u, v) ∈ A, either u, v ∈ S or u, v ∈ V − S
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 17 / 18
Optimality of greedy (II)
Definition
A cut (S, V − S) respects A ⊆ E if ∀(u, v) ∈ A, either u, v ∈ S or u, v ∈ V − S
A: red edges
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 17 / 18
Optimality of greedy (II)
Definition
A cut (S, V − S) respects A ⊆ E if ∀(u, v) ∈ A, either u, v ∈ S or u, v ∈ V − S
A: red edges
cut ({b, d}, {a, c, e}) cut ({e}, {a, b, c, d})
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 17 / 18
Optimality of greedy (II)
Definition
A cut (S, V − S) respects A ⊆ E if ∀(u, v) ∈ A, either u, v ∈ S or u, v ∈ V − S
A: red edges
cut({b,d},{a,c,e}) doesn’trespectA cut ({e}, {a, b, c, d})
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 17 / 18
Optimality of greedy (II)
Definition
A cut (S, V − S) respects A ⊆ E if ∀(u, v) ∈ A, either u, v ∈ S or u, v ∈ V − S
A: red edges
cut({b,d},{a,c,e}) doesn’trespectA cut ({e}, {a, b, c, d}) respects A
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 17 / 18
Optimality of greedy (III)
Theorem (The cut property)
Let A be a subset of edges of some MST of G = (V,E).
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 18 / 18
Optimality of greedy (III)
Theorem (The cut property)
LetAbeasubsetofedgesofsomeMSTofG=(V,E). Let(S,V−S) be a cut that respects A.
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 18 / 18
Optimality of greedy (III)
Theorem (The cut property)
LetAbeasubsetofedgesofsomeMSTofG=(V,E). Let(S,V−S) be a cut that respects A. Let e be the lightest edge across the cut.
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 18 / 18
Optimality of greedy (III)
Theorem (The cut property)
LetAbeasubsetofedgesofsomeMSTofG=(V,E). Let(S,V−S) be a cut that respects A. Let e be the lightest edge across the cut. Then A ∪ {e} is part of some MST
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 18 / 18
Optimality of greedy (III)
Theorem (The cut property)
LetAbeasubsetofedgesofsomeMSTofG=(V,E). Let(S,V−S) be a cut that respects A. Let e be the lightest edge across the cut. Then A ∪ {e} is part of some MST
How does this help?
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 18 / 18
Optimality of greedy (III)
Theorem (The cut property)
LetAbeasubsetofedgesofsomeMSTofG=(V,E). Let(S,V−S) be a cut that respects A. Let e be the lightest edge across the cut. Then A ∪ {e} is part of some MST
How does this help?
• It shows the greedy choice property:
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 18 / 18
Optimality of greedy (III)
Theorem (The cut property)
LetAbeasubsetofedgesofsomeMSTofG=(V,E). Let(S,V−S) be a cut that respects A. Let e be the lightest edge across the cut. Then A ∪ {e} is part of some MST
How does this help?
• It shows the greedy choice property:
there exists an optimal solution that makes the greedy choice
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 18 / 18
Optimality of greedy (III)
Theorem (The cut property)
LetAbeasubsetofedgesofsomeMSTofG=(V,E). Let(S,V−S) be a cut that respects A. Let e be the lightest edge across the cut. Then A ∪ {e} is part of some MST
How does this help?
• It shows the greedy choice property:
there exists an optimal solution that makes the greedy choice
• It also demonstrates the optimal substructure property
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 18 / 18
Optimality of greedy (III)
Theorem (The cut property)
LetAbeasubsetofedgesofsomeMSTofG=(V,E). Let(S,V−S) be a cut that respects A. Let e be the lightest edge across the cut. Then A ∪ {e} is part of some MST
How does this help?
• It shows the greedy choice property:
there exists an optimal solution that makes the greedy choice
• It also demonstrates the optimal substructure property by applying this theorem multiple times until you can’t
Chunhao MPSC 465 Spring 2022 Mar 3, 2022 18 / 18
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com