CS代考 Lecture 11: Greedy Algorithms

Lecture 11: Greedy Algorithms
A greedy algorithm always makes the choice that looks best at the moment and adds it to the current partial solution.
Greedy algorithms don’t always yield optimal solutions, but when they do, they’re usually the simplest and most efficient algorithms available.

1. Intro and Simple Problems 2.Interval Scheduling
3. Knapsack
4.Interval Partitioning

General Idea
Greedy algorithms generate a solution to an optimization problem through a sequence of choices that are:
• Feasible, i.e. satisfying given constraints
• Locally optimal (make the choice that looks best at
the moment, without considering the future) • Irrevocable (no backtracking)
For some problems, greedy algorithms provide globally optimal solutions for every instance. For other problems, they generate fast approximate solutions.
Often, they involve a sorting step that dominates the total cost.

Exercise on Minimum number of Coins Input: Amount n, and coins of denominations d1 > … > dm
Output: Minimum number of coins for amount n Example:n=48c d1=25c, d2=10c, d3=5c, d4=1c
Greedy solution: Give as many coins as possible from the largest coin, then as many as possible from second largest and so on.
48=1×25+2X10+3X1
Greedy solution may not be optimal for arbitrary coin denominations
n = 30c, d1 = 25c, d2 = 10c, d3 = 1c

Exercise on of Non-Adjacent Elements
Given an array of n positive numbers A[1], A[2], . . . , A[n]. Our goal is to pick out a subset of non-adjacent elements whose sum is maximized.
For example, if the array is (1, 8, 6, 3, 6), then the elements chosen should be A[2] and A[5], whose sum is 14.
Describe a greedy algorithm and discuss whether it is optimal or not
Start with S equal to the empty set While some elements remain in A
Pick the largest A[i]
Add A[i] to S
Mark A[i] and its neighbors as deleted
End while Return S
Counter-example of optimality. Input: (1, 4, 6, 4). The above algorithm returns S={1, 6} with sum=7. The optimal solution is S={4, 4} with sum=8.

Exercise on Hiking Problem
Suppose you are going on a hiking trip over multiple days. For safety reasons you can only hike during daytime. You can travel at most d kilometers per day, and there are n camping sites along the hiking trail where you can make stops at night.
Assuming the starting point of the trail is at position x0 = 0, the camping sites are atlocationsx1,…,xn,withx1 d then curloc = xi-1;
camping sites.insert(xi-1); return camping sites
In the previous example x1=4, x2=5, x3=6, x4=9, x5=12 the algorithm outputs camping sites = [x2, x4].

Proof of Correctness (Optimality) for Hiking Problem
• Let G be the solution returned by this greedy algorithm, and let O be an optimal solution.
In the previous example G= [x2, x4], O= [x1, x4]
• Consider the first camping site where O is different from G. Suppose the camping site in G is located at x and the one in O is located at x’.
In the previous example x= x2, x’= x1
• By the greedy choice, we must have x > x’ because greedy always selects the furthest site within distance d from previous stop. Now replace x’ with x in O. The resulting O* must still satisfy the requirement (travel at most d kilometers per day) and contains the same number of stops as O. Thus, it is also optimal.
• Repeatedly applying this transformation will convert O into G. Thus, G is also an optimal solution.
last common stop in G and O

Interval scheduling.
Interval Scheduling
Job starts at 𝑗 and finishes at 𝑗.
 Two jobs are compatible if they don’t overlap.
 Goal: find maximum size subset of mutually compatible jobs.
0 1 2 3 4 5 6 7 8 9 10 11

Interval Scheduling: Greedy Algorithms
Greedy template. Consider jobs in some order.
Take a job provided it’s compatible with the ones already taken.
Usually, many compatible jobs can co-exist.
Need to choose a rule specifying which job to choose next. Three possible rules are:
 [Earliest start time]
Consider jobs in increasing order of start time 􏰙.
 [Shortest interval]
Consider jobs in increasing order of interval length 􏰙 􏰙.
 [Fewest conflicts]
For each job, count the number of conflicting jobs 􏰙. Schedule in ascending order of conflicts 􏰙.

Interval Scheduling: Greedy Algorithms
Greedy template. Consider jobs in some order.
Take a job provided it’s compatible with the ones already taken.
Order on earliest start time
Chooses {e} instead of {a,b,c,d}
Order on shortest interval
Chooses {c} instead of {a,b}
Order on fewest conflicts
Chooses {f} which forces choosing {a,f,d} instead of {a,b,c,d}
Examples above provide counterexamples for the three proposed rules. For each, there is an input for which the rule yields a non-optimal (i.e., non max-size) schedule.

Interval Scheduling: Greedy Algorithm
Greedy algorithm. Consider jobs in increasing order of finish time. Take each job provided it’s compatible with the ones already taken
0 1 2 3 4 5 6 7 8 9 10 11

Interval Scheduling: Greedy Algorithm
Greedy algorithm. Consider jobs in increasing order of finish time. Take each job provided it’s compatible with the ones already taken.
Intuition: leaves maximum interval for scheduling the rest of the jobs.
Sort jobs by finish times so that 𝑓􏰆 𝑓􏰈  … 𝑓􏰀 𝐴←∅, 𝑙𝑎𝑠𝑡←0
for 𝑗←1 to 𝑛
if 𝑠􏰙 ≥𝑙𝑎𝑠𝑡 then 𝐴←𝐴∪{𝑗}, 𝑙𝑎𝑠𝑡←𝑓􏰙 return 𝐴
Running time dominated by cost of sorting: .
 Remember the finish time of the last job added to .
Job is compatible with if 𝑗  .
Correctness (optimality) of greedy algorithms is usually not obvious.
Need to prove!

Find largest value of such that
Interval Scheduling: Correctness
Theorem. Greedy algorithm is optimal.
 Assume that the solution G of Greedy is different from O, the optimal solution.
Let 1 2 𝑘 denote the set of jobs selected by greedy. Let 1 2 𝑚 denote set of jobs in the optimal solution.
By definition of Greedy, job 𝑖􏰢􏰑􏰆 finishes before 𝑗􏰢􏰑􏰆

Assume G is different from O.
Choose largest r such that 􏰨 􏰨 for and 􏰢􏰑􏰆 􏰢􏰑􏰆. Create O* from O by replacing 􏰢􏰑􏰆 with 􏰢􏰑􏰆.
O* is still a legal solution and has same size as O. O* is also Optimal
Interval Scheduling: Correctness
Theorem. Greedy algorithm is optimal. Proof (Continued)
job 𝑖􏰢􏰑􏰆 finishes before 𝑗􏰢􏰑􏰆
must still be compatible with remainder of O

Proof. So far
Interval Scheduling: Correctness
 AssumedG O.
 Let r be such that O shares first r items with G.
 Process creates new Optimal solution O*, which shares first r+1 items
with Greedy Greedy:
Can repeat this process starting with Greedy and (optimal) O*
Continue repeating this process until O becomes the same as greedy.
Important: Since cost remains the same, final Greedy solution we’ve created is

The Fractional Knapsack Problem
Optimal 0/1
Optimal Fractional
Input: Set of items: item has weight 􏰌 and value 􏰌, and a knapsack with capacity .
Goal: Find 􏰆 􏰀 such that 􏰀􏰌􏰍􏰆 􏰌 􏰌 and 􏰀􏰌􏰍􏰆 􏰌 􏰌 is maximized.
There are two different versions of this problem:
The 􏰌’s must be or : The 0/1 knapsack problem.
The 􏰌’s can take fractional values: The fractional knapsack problem

The Greedy Algorithm for Fractional Knapsack
Sort items so that 􏰾􏰉 ≥ 􏰾􏰊 ≥⋯≥ 􏰾􏰔
for 𝑖←1 to 𝑛
if 𝑤􏰌 ≤ 𝑤 then 𝑥􏰌 ← 1
𝑤 ← 𝑤 − 𝑤􏰌
 Sort all items by value-per-pound
 For each item, take as much as possible
Running time:
Note: This algorithm cannot solve the 0/1 version optimally.

Greedy Algorithm: Correctness
Theorem: The greedy algorithm is optimal.
Proof: We assume that 􏰀􏰌􏰍􏰆 􏰌 so knapsack is fully packed.
Otherwise the algorithm is trivially optimal.
Let the greedy solution be
Note:for􏰌for􏰌 􏰋.
Consider any optimal solution
 Note: Since both and must fully pack the knapsack,
∑ 􏰋􏰌 􏰍 􏰆 𝑥 􏰌 𝑤 􏰌 = 𝑊 = ∑ 􏰀􏰌 􏰍 􏰆 𝑦 􏰌 𝑤 􏰌
Look at the first item where the two solutions differ.
By definition of greedy,
􏰆 􏰈 􏰏 … 􏰌􏰓􏰆 􏰌… 􏰋
􏰆 􏰈 􏰏 … 􏰌􏰓􏰆 􏰌 … 􏰋 􏰀􏰓􏰆 􏰀

Greedy Algorithm: Correctness (continued)
We now modify as follows:
Set 􏰌 􏰌 and remove amount of some items in to
of total weight
 This is always doable because in both and , the used total weight of items to is the same. (∑􏰋􏰌􏰍􏰆 𝑥􏰌 𝑤􏰌 = 𝑊 = ∑􏰀􏰌􏰍􏰆 𝑦􏰌 𝑤􏰌)
After the modification:
 The total value of this new has not decreased, since all the items
to have lesser or equal value-per-pound than item
 This new ’s value can not be greater than before,
since was already an optimal solution,
 => ’s value stays the same => is still an optimal solution
 ’s first index that differs from is now at least
Repeating this process will eventually convert into
(1st index that differs always increases so the process must stop). Note that process keeps solution value of invariant (and optimal).
at end Greedy is optimal

Interval partitioning.
Interval Partitioning
Lecture starts at 􏰙 and finishes at 􏰙.
lectures so that no two occur at the same time in the same room.
Ex: This schedule uses 4 classrooms to schedule 10 lectures.
 Goal: find the minimum number of classrooms to schedule all
Room3c d g
Room 2 Room 1
9 9:30 10 10:30 11 11:30 12 12:30 1 1:30 2 2:30 3 3:30 4 4:30

Interval partitioning.
Interval Partitioning
Lecture starts at 􏰙 and finishes at 􏰙.
lectures so that no two occur at the same time in the same room.
Ex: This schedule uses only 3.
Room3c d f j Room2 b g i Room 1 a
9 9:30 10 10:30 11 11:30 12 12:30 1 1:30 2 2:30 3 3:30 4 4:30
 Goal: find the minimum number of classrooms to schedule all

Interval Partitioning: Greedy Algorithm
Greedy algorithm. Consider lectures in increasing order of start time: assign lecture to any compatible classroom.
Sort intervals by starting time so that 𝑠1  𝑠2  …  𝑠𝑛.
𝑑 ← 0 // # classrooms used so far
for 𝑗←1 to 𝑛
if lecture 𝒋 is compatible with some classroom 𝒌 then
schedule lecture 𝑗 in classroom 𝑘 else
allocate a new classroom 𝑑+1 schedule lecture 𝑗 in classroom 𝑑 + 1 𝑑←𝑑+1
Greedy! It only opens a new classroom if it is needed.
Need to prove optimality.
More specifically, need to show that processing the lectures
ordered by starting time implies optimality.
Convince yourself that processing by finishing time does NOT yield optimal solution!

Interval partitioning.
Interval Partitioning
Lecture starts at 􏰙 and finishes at 􏰙.
 Goal: find the minimum number of classrooms to schedule all lectures so
that no two occur at the same time in the same room.
ALG: Sort by start time. Insert in order, opening new classroom when needed
3 5 7 10 269
9 9:30 10 10:30 11 11:30 12 12:30 1 1:30 2 2:30 3 3:30 4 4:30

Interval Partitioning: Lower Bound on Optimal Solution
Def. The depth of a set of open intervals is the maximum number that exist at any instant of time.
Intuition: At each second of the day keep track of how many simultaneous classes are being taught at that time. The depth is the maximum number you have seen.
Key observation. Minimum number of classrooms needed  depth.
Ex: Depth of schedule below = 3  this schedule is optimal.
We will show: The # classrooms used by the greedy algorithm = depth.
9 9:30 10 10:30 11 11:30 12 12:30 1 1:30 2 2:30 3 3:30 4 4:30

Interval Partitioning: Correctness
Theorem. Greedy algorithm is optimal.
 Let = number of classrooms opened by greedy algorithm .
Classroom is opened because we needed to schedule a lecture, say , that is incompatible with all other classrooms.
Since we sorted by start time, all these incompatibilities are caused by lectures that all start no later than 𝑗 and finish later than 𝑗.
Every algorithm uses at least depth classrooms  Greedy is optimal.

Interval Partitioning: Running Time
Sort intervals by starting time so that 𝑠1  𝑠2  …  𝑠𝑛. 𝑑 ← 0 // # classrooms used so far
for 𝑗←1 to 𝑛
if lecture 𝒋 is compatible with some classroom 𝒌 then (*) schedule lecture 𝑗 in classroom 𝑘 (**)
allocate a new classroom 𝑑+1
schedule lecture 𝑗 in classroom 𝑑 + 1 (***) 𝑑←𝑑+1
 To implement line (*) the algorithm maintains, for each classroom, the finishing time of the last item placed in the classroom.
It then compares 𝑗 to those finishing times. If 𝑗 one of those finishing times, it places lecture j in the associated classroom
 A Brute-force implementation of line (*) uses time
 Observation: If is not compatible with the classroom with the earliest
finish time, then is not compatible with any other classroom

𝑐𝑜𝑠𝑡 𝑂(log 𝑛)
To implement line (*) we can keep the classrooms in a min heap using the finishing times of the last class in the room as the key of each classroom
To check whether there is a compatible classroom we find min finishing time 𝑓􏰦􏰌􏰀 at the top of the min heap and check whether 𝑓􏰦􏰌􏰀 ≤ 𝑠􏰙
Let k be classroom with 𝑓􏰦􏰌􏰀 (𝑓􏰦􏰌􏰀 ≤ 𝑠􏰙). To implement (**), we perform extract- min and insert classroom k with new finishing time 𝑓𝑗 to min heap
To implement (***) insert the new classroom j with finishing time 𝑓𝑗 to min heap
𝑂(log 𝑛) 
Interval Partitioning: Running Time
Sort intervals by starting time so that 𝑠1  𝑠2  …  𝑠𝑛. 𝑑 ← 0 // # classrooms used so far
for 𝑗←1 to 𝑛
if lecture 𝒋 is compatible with some classroom 𝑘 then (*) schedule lecture 𝑗 in classroom 𝒌 (**)
allocate a new classroom 𝑑+1
schedule lecture 𝒋 in classroom 𝑑 + 1 (***) 𝑑←𝑑+1
Running time: Θ(𝑛 log 𝑛)

Exercise on Placement of Base Stations
Consider a long river, along which n houses are scattered. You can think of this river as an axis, and the houses are given by their coordinates on this axis in a sorted order. You must place cell phone base stations at certain points along the river, so that every house is within d kilometers of one of the base stations (d is an input).
Give an O(n)-time algorithm that minimizes the number of base stations used, and show that it indeed yields the optimal solution.
base stations

Put the first base station at x + d where x is the coordinate of the first house. Remove all the houses that are covered and then repeat if there are still houses not covered.
Correctness: Let G be the solution returned by this greedy algorithm, and let O be an optimal solution.
Consider the first base station where O is different from G. Suppose the base station in G is located at x and the one in O is located at x’. By the greedy choice, we must have x > x’ because greedy selects the furthest point possible (at distance d) from the first non-covered house.
Now replace x’ with x in O . The resulting O* must still cover all houses. Repeatedly applying this transformation will convert O into G. Thus, G is also an optimal solution.

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts