COMP3711(H): Design and Analysis of Algorithms
Tutorial 6: Greedy
COMP3711(H): Design and Analysis of Algorithms
Copyright By PowCoder代写 加微信 powcoder
Greedy Interval Covering
A unit-length closed interval on the real line is an interval 𝑥, 𝑥 + 1 . Describe an O(n) algorithm that, given input set
𝑋= 𝑥1,𝑥2,…,𝑥𝑛
determines the smallest set of unit-length closed intervals that contains all of the given points.
Argue that your algorithm is correct. You should assume that
𝑥1 <𝑥2 <⋯<𝑥𝑛
As an example the points above are given on a line and you are given the length of a 1-unit interval.
Show how to place a minimum number of such intervals to cover the points.
Since each point is seen only once, this is an O(n) algorithm.
The diagram above is the solution for the points on the previous page
Keep the points in an array. Walk through the array as follows.
1. Set𝑥=𝑥1
2. Walk through the points in increasing order
until finding the first 𝑗 such that 𝑥 > 𝑥 + 1 𝑗
4. If there was no such 𝑗 in (2) then stop. Otherwise, set 𝑥 = 𝑥 𝑗
5. Go to Step (2)
Keep the points in an array. Walk through the array as follows.
1. Set𝑥=𝑥1
2. Walk through the points in increasing order
until finding the first 𝑗 such that 𝑥 > 𝑥 + 1 𝑗
4. If there was no such 𝑗 in (2) then stop. Otherwise, set 𝑥 = 𝑥 𝑗
5. Go to Step (2)
We must now prove correctness.
Let Greedy(i,k) be the algorithm run on the Array 𝑖 … 𝑘 . Note that this can be rewritten
1. Output𝑥𝑖,𝑥𝑖+1
2. Findmin 𝑗 suchthat𝑥>𝑥 +1
3. If such a 𝑗 does not exist, stop, else return Greedy(j,k)
We will prove correctness by induction on number of points 𝑿 .
1. Output𝑥𝑖,𝑥𝑖+1
2. Findmin 𝑗 suchthat𝑥>𝑥 +1
3. If such a 𝑗 does not exist, stop, else return Greedy(j,k)
We will prove correctness by induction on number of points 𝑋 .
(i) If 𝑋 = 1 (only one point) then algorithm is obviously correct.
Otherwise, suppose 𝑋 = 𝑛 and that we know (induction hypotheses) that the algorithm is correct for all problems with size 𝑋 < 𝑛.
(ii) 𝑋 = 𝑛 and we know that the algorithm is correct for all problems with 𝑋 < 𝑛.
𝑥1, 𝑥1 + 1 Greedy solution for {𝑥𝑗′, ... , 𝑥𝑛}
1. Output𝑥𝑖,𝑥𝑖+1
2. Findmin 𝑗 suchthat𝑥>𝑥 +1
3. If such a 𝑗 does not exist, stop, else return Greedy(j,k)
Proving correctness by induction on number of points 𝑋 .
(ii) 𝑋 = 𝑛 and we know that the algorithm is correct for all problems with 𝑋 < 𝑛.
𝑂(𝑖, 𝑗) = 𝑚𝑖𝑛𝑖𝑚𝑢𝑚 # 𝑜𝑓 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠 𝑛𝑒𝑒𝑑𝑒𝑑 𝑡𝑜 𝑐𝑜𝑣𝑒𝑟 {𝑥 , ... , 𝑥 } 𝑖𝑗
𝐺(𝑖,𝑗) = # 𝑜𝑓 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠 𝐺𝑟𝑒𝑒𝑑𝑦 𝑢𝑠𝑒𝑠 𝑡𝑜 𝑐𝑜𝑣𝑒𝑟 {𝑥 ,...,𝑥 } 𝑖𝑗
Assume 𝑥1, 𝑥1 + 1 does not cover all of 𝑋 because, if it did,
Greedy would return that same one interval solution which is optimal.
Let 𝑗′ be the smallest index such that 𝑥 > 𝑥 + 1 𝑗′ 1
Greedy returns 𝑥1, 𝑥1 + 1 concatenated with the greedy solution for {𝑥𝑗′, … , 𝑥𝑛} => Greedy uses 1 + 𝐺 𝑗′, 𝑛 intervals
1. Output𝑥𝑖,𝑥𝑖+1
2. Findmin 𝑗 suchthat𝑥>𝑥 +1
3. If such a 𝑗 does not exist, stop, else return Greedy(j,k)
Proving correctness by induction on number of points 𝑋 .
(ii) 𝑋 = 𝑛 and we know that the algorithm is correct for all problems with 𝑋 < 𝑛.
𝑂(𝑖, 𝑗) = 𝑚𝑖𝑛𝑖𝑚𝑢𝑚 # 𝑜𝑓 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠 𝑛𝑒𝑒𝑑𝑒𝑑 𝑡𝑜 𝑐𝑜𝑣𝑒𝑟 {𝑥 , ... , 𝑥 } 𝑖𝑗
𝐺(𝑖,𝑗) = # 𝑜𝑓 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠 𝐺𝑟𝑒𝑒𝑑𝑦 𝑢𝑠𝑒𝑠 𝑡𝑜 𝑐𝑜𝑣𝑒𝑟 {𝑥 ,...,𝑥 } 𝑖𝑗
Assume 𝑥1, 𝑥1 + 1 does not cover all of 𝑋 because, if it did,
Greedy would return that same one interval solution which is optimal.
Let 𝑗′ be the smallest index such that 𝑥 > 𝑥 + 1 𝑗′ 1
Greedy returns 𝑥1, 𝑥1 + 1 concatenated with the greedy solution for {𝑥𝑗′, … , 𝑥𝑛}
=> Greedy uses 1 + 𝐺 𝑗′, 𝑛 intervals
Since 𝑗 > 1, Induction Hypothesis implies that 𝐺 𝑗′, 𝑛 = 𝑂(𝑗′, 𝑛)
=> Greedy uses 1 + 𝐺 𝑗′,𝑛 = 1 + 𝑂(𝑗′,𝑛) intervals
𝑂(𝑖, 𝑗) = 𝑚𝑖𝑛𝑖𝑚𝑢𝑚 # 𝑜𝑓 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠 𝑛𝑒𝑒𝑑𝑒𝑑 𝑡𝑜 𝑐𝑜𝑣𝑒𝑟 {𝑥 , … , 𝑥 } 𝑖𝑗
𝐺(𝑖,𝑗) = # 𝑜𝑓 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠 𝐺𝑟𝑒𝑒𝑑𝑦 𝑢𝑠𝑒𝑠 𝑡𝑜 𝑐𝑜𝑣𝑒𝑟 {𝑥 ,…,𝑥 } 𝑖𝑗
=> Greedy uses 1 + 𝑂(𝑗′, 𝑛) intervals
Will now use this fact to prove G 1, 𝑛 ≤ 𝑂 1, 𝑛 . Since, by definition of optimal, 𝑂 1, 𝑛 ≤ 𝐺 1, 𝑛 ,
this implies that G 1, 𝑛 = 𝑂 1, 𝑛 , i.e., that Greedy is Optimal.
1. Output𝑥𝑖,𝑥𝑖+1
2. Findmin 𝑗 suchthat𝑥>𝑥 +1
3. If such a 𝑗 does not exist, stop, else return Greedy(j,k)
𝑗′=smallestindexsuchthat 𝑥 >𝑥 +1 𝑗′ 1
1. Output𝑥𝑖,𝑥𝑖+1
2. Findmin 𝑗 suchthat𝑥>𝑥 +1
3. If such a 𝑗 does not exist, stop, else return Greedy(j,k)
𝑂(𝑖, 𝑗) = 𝑚𝑖𝑛𝑖𝑚𝑢𝑚 # 𝑜𝑓 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠 𝑛𝑒𝑒𝑑𝑒𝑑 𝑡𝑜 𝑐𝑜𝑣𝑒𝑟 {𝑥 , … , 𝑥 } 𝑖𝑗
𝐺(𝑖,𝑗) = # 𝑜𝑓 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠 𝐺𝑟𝑒𝑒𝑑𝑦 𝑢𝑠𝑒𝑠 𝑡𝑜 𝑐𝑜𝑣𝑒𝑟 {𝑥 ,…,𝑥 } 𝑖𝑗
=> Greedy uses 1 + 𝑂(𝑗′, 𝑛) intervals
Suppose there exists optimal solution OPT different from Greedy.
Let 𝑥, 𝑥 + 1 be interval in OPT with the leftmost starting point.
𝑥 ≤ 𝑥1 because otherwise 𝑥1 would not be covered by any interval in OPT.
𝑗′=smallestindexsuchthat 𝑥 >𝑥 +1 𝑗′ 1
1. Output𝑥𝑖,𝑥𝑖+1
2. Findmin 𝑗 suchthat𝑥>𝑥 +1
3. If such a 𝑗 does not exist, stop, else return Greedy(j,k)
𝑂(𝑖, 𝑗) = 𝑚𝑖𝑛𝑖𝑚𝑢𝑚 # 𝑜𝑓 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠 𝑛𝑒𝑒𝑑𝑒𝑑 𝑡𝑜 𝑐𝑜𝑣𝑒𝑟 {𝑥 , … , 𝑥 } 𝑖𝑗
𝐺(𝑖,𝑗) = # 𝑜𝑓 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠 𝐺𝑟𝑒𝑒𝑑𝑦 𝑢𝑠𝑒𝑠 𝑡𝑜 𝑐𝑜𝑣𝑒𝑟 {𝑥 ,…,𝑥 } 𝑖𝑗
=> Greedy uses 1 + 𝑂(𝑗′, 𝑛) intervals
Suppose there exists optimal solution OPT different from Greedy.
Let 𝑥, 𝑥 + 1 be interval in OPT with the leftmost starting point.
𝑥 ≤ 𝑥1 because otherwise 𝑥1 would not be covered by any interval in OPT.
Let 𝑘 be the minimum index such that 𝑥𝑘> 𝑥 + 1
After removing 𝑥, 𝑥 + 1 , remaining intervals in OPT must form optimal solution for {𝑥𝑘 , … , 𝑥𝑛 }, otherwise we could build better solution using fewer intervals.
=> Optimal uses 1 + 𝑂(𝑘, 𝑛) intervals
𝑗′=smallestindexsuchthat 𝑥 >𝑥 +1 𝑗′ 1
=>𝑂 𝑗′,𝑛 ≤𝑂 𝑘,𝑛 =>
G(1, 𝑛) = 1 + G(𝑗′, 𝑛) = 1 + O(𝑗′, 𝑛) ≤ 1 + O(𝑘, 𝑛)
1. Output𝑥𝑖,𝑥𝑖+1
2. Findmin 𝑗 suchthat𝑥>𝑥 +1
3. If such a 𝑗 does not exist, stop, else return Greedy(j,k)
𝑂(𝑖, 𝑗) = 𝑚𝑖𝑛𝑖𝑚𝑢𝑚 # 𝑜𝑓 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠 𝑛𝑒𝑒𝑑𝑒𝑑 𝑡𝑜 𝑐𝑜𝑣𝑒𝑟 {𝑥 , … , 𝑥 } 𝑖𝑗
G 𝑖,𝑗 = 𝑚𝑖𝑛𝑖𝑚𝑢𝑚 # 𝑜𝑓 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠 𝐺𝑟𝑒𝑒𝑑𝑦 𝑢𝑠𝑒𝑠 𝑡𝑜 𝑐𝑜𝑣𝑒𝑟 {𝑥 ,…,𝑥 } 𝑖𝑗
Greedyuses 1+𝑂(𝑗′,𝑛)intervals Optimaluses 1+𝑂(𝑘,𝑛)intervals
Because 𝑥 ≤ 𝑥1, 𝑘 ≤ 𝑗′ (Why?)
=> the optimal solution for {𝑥𝑘, … , 𝑥𝑛} is SOME solution for {𝑥𝑗′, … , 𝑥𝑛}
𝑗′=smallestindexsuchthat 𝑥 >𝑥 +1 𝑗′ 1
𝑥, 𝑥 + 1 is leftmost interval in OPT
𝑘 = smallest index such that 𝑥𝑘> 𝑥 + 1
Induction hypothesis!
Final Result!
COMP3711(H): Design and Analysis of Algorithms
GY 3 Greedy Driving
(CLRS-16.2-4) Professor Midas drives an automobile from Newark to Reno along Interstate 80.
His car’s gas tank, when full, holds enough gas to travel 𝑚 miles, and his map gives the distance between gas stations on his route. The professor wishes to make as few gas stops as possible along the way.
Give an efficient method by which Professor Midas can determine at which gas stations he should stop and prove that your algorithm yields an optimal solution.
Solution (i)
We prove that the simple greedy algorithm is optimal. This is to drive to the furthest possible city that one can reach with the current gas in the car, fill up the tank and then continue, until reaching 𝑥𝑛−1.
Input to the problem is 𝑚 and locations 𝑥0 < 𝑥1 < ⋯ < 𝑥𝑛−1. 𝑥0 is the starting location and 𝑥𝑛−1 is destination.
Note that a sequence 𝑆 = 𝑠1,𝑠2,...,𝑠𝑘 is a solution if
𝑖 0=𝑠 <𝑠 <𝑠 <⋯𝑠 <𝑠
0 1 2 𝑘 𝑘+1
𝑖𝑖 ∀𝑖≤𝑘, 𝑥𝑠𝑖+1−𝑥𝑠𝑖 ≤𝑚
𝑆 = 𝑘 denotes the size of 𝑆.
The problem is to find the smallest (optimal) solution.
Solution (ii)
Consider the input 𝑋 on 𝑛 points: 𝑥0 < 𝑥1 < ⋯ < 𝑥𝑛−1
𝐺 denotes greedy solution; 𝑂 denotes an optimal solution. Let 𝑔𝑖 and 𝑜𝑖 be the stops the two algorithms make, in order.
𝐺=𝑔 ,𝑔 ,...,𝑔 and 𝑂=𝑜 ,𝑜 ,...,𝑜 ′ 12𝑘 12𝑘
Observation 1: 𝑔 ,...,𝑔 is the Greedy solution for input 𝑥 ,𝑥 ,...,𝑥 . 2 𝑘 𝑔1 𝑔1+1 𝑛−1
To see this, note that Greedy can be viewed as a recursive algorithm. After filling up at the first chosen station, Greedy runs itself starting from that station.
Solution (iii)
Consider the input 𝑋 on 𝑛 points: 𝑥0 < 𝑥1 < ⋯ < 𝑥𝑛−1
𝐺 denotes greedy solution; 𝑂 denotes an optimal solution. Let 𝑔𝑖 and 𝑜𝑖 be the stops the two algorithms make, in order.
𝐺=𝑔 ,𝑔 ,...,𝑔 and 𝑂=𝑜 ,𝑜 ,...,𝑜 ′ 12𝑘 12𝑘
Observation 1: 𝑔 ,...,𝑔 is the Greedy solution for input 𝑥 ,𝑥 ,...,𝑥 . 2 𝑘 𝑔1 𝑔1+1 𝑛−1
Observation 2: 𝑂′ = 𝑔 ,𝑜 ,𝑜 ,...,𝑜 ′ is also an optimal solution for 𝑋.
⇒𝑥 −𝑥 ≤𝑥 −𝑥 ≤𝑚 𝑜2 𝑔1 𝑜2 𝑜1
⇒ 𝑂′ is a solution for 𝑋
⇒ Since 𝑂′ = 𝑘′ = 𝑂 , 𝑂′ is also optimal.
(*) By the definition of Greedy, 𝑜 ≤ 𝑔 . 11
𝑔1 = max 𝑖 ∶ 𝑥𝑖 − 𝑥0 ≤ 𝑚 𝑥𝑜𝑖 − 𝑥0 ≤ 𝑚
Solution (iv)
Consider the input 𝑋 on 𝑛 points: 𝑥0 < 𝑥1 < ⋯ < 𝑥𝑛−1
𝐺 denotes greedy solution; 𝑂 denotes an optimal solution. Let 𝑔𝑖 and 𝑜𝑖 be the stops the two algorithms make, in order.
𝐺=𝑔 ,𝑔 ,...,𝑔 and 𝑂=𝑜 ,𝑜 ,...,𝑜 ′ 12𝑘 12𝑘
Observation 1: 𝑔 ,...,𝑔 is the Greedy solution for input 𝑥 ,𝑥 ,...,𝑥 . 2 𝑘 𝑔1 𝑔1+1 𝑛−1
Observation 2: 𝑂′ = 𝑔 ,𝑜 ,𝑜 ,...,𝑜 ′ is also an optimal solution for 𝑋.
Observation 3’: If 𝑆 = 𝑖1, 𝑖2, 𝑖3 ... , 𝑖𝑡 is an optimal solution for 𝑋 then
𝑆′ = 𝑖2,𝑖3 ...,𝑖𝑡 is an optimal solution for 𝑋′ = 𝑥𝑖1,𝑥𝑖1+1,...,𝑥𝑛−1. First note that 𝑆′ is a solution for 𝑋′ since ∀𝑗, 𝑥𝑖𝑗+1 − 𝑥𝑖𝑗 ≤ 𝑚.
Suppose 𝑆′ was not optimal for 𝑋′. Then 𝑋′ would have another solution 𝑈′ =𝑢1,𝑢2...,𝑢𝑡′ with𝑡′ <𝑡−1.
Since 𝑥𝑢1 − 𝑥𝑖1 ≤ 𝑚, 𝑆′′ = 𝑖1, 𝑢1, 𝑢2 ... , 𝑢𝑡′ would be a length 𝑡′ + 1 < 𝑡 solution for 𝑋, contradicting the optimality of 𝑆! ⇒ 𝑆′ is optimal.
Solution (iv)
Consider the input 𝑋 on 𝑛 points: 𝑥0 < 𝑥1 < ⋯ < 𝑥𝑛−1
𝐺 denotes greedy solution; 𝑂 denotes an optimal solution. Let 𝑔𝑖 and 𝑜𝑖 be the stops the two algorithms make, in order.
𝐺=𝑔 ,𝑔 ,...,𝑔 and 𝑂=𝑜 ,𝑜 ,...,𝑜 ′ 12𝑘 12𝑘
Observation 1: 𝑔 ,...,𝑔 is the Greedy solution for input 𝑥 ,𝑥 ,...,𝑥 . 2 𝑘 𝑔1 𝑔1+1 𝑛−1
Observation 2: 𝑂′ = 𝑔 ,𝑜 ,𝑜 ,...,𝑜 ′ is also an optimal solution for 𝑋.
Observation 3’: If 𝑆 = 𝑖1, 𝑖2, 𝑖3 ... , 𝑖𝑡 is an optimal solution for 𝑋 then
𝑆′ = 𝑖2,𝑖3 ...,𝑖𝑡 is an optimal solution for 𝑋′ = 𝑥𝑖1,𝑥𝑖1+1,...,𝑥𝑛−1. Observation 3: 𝑂′′ = 𝑜 ,𝑜 ,...,𝑜 ′ is an optimal solution for 𝑥 ,𝑥 ,...,𝑥
2 3 𝑘 𝑔1 𝑔1+1 𝑛−1 Combine Observations 2 and 3’.
Solution (v)
Consider the input 𝑋 on 𝑛 points: 𝑥0 < 𝑥1 < ⋯ < 𝑥𝑛−1
𝐺 denotes greedy solution; 𝑂 denotes an optimal solution. Let 𝑔𝑖 and 𝑜𝑖 be the stops the two algorithms make, in order.
𝐺=𝑔 ,𝑔 ,...,𝑔 and 𝑂=𝑜 ,𝑜 ,...,𝑜 ′ 12𝑘 12𝑘
Observation 1: 𝑔 ,...,𝑔 is the Greedy solution for input 𝑥 ,𝑥 ,...,𝑥 . 2 𝑘 𝑔1 𝑔1+1 𝑛−1
Observation 2: 𝑂′ = 𝑔 ,𝑜 ,𝑜 ,...,𝑜 ′ is also an optimal solution for 𝑋.
Observation 3: 𝑜 ,𝑜 ,...,𝑜 ′ is an optimal solution for 𝑥 ,𝑥 ,...,𝑥 . 2 3 𝑘 𝑔1 𝑔1+1 𝑛−1
We will prove optimality of Greedy by induction on 𝑛.
We assume that Greedy is optimal on all problems on set size < 𝑛.
(Basis: this is obviously true on sets of size 1 and 2.)
Solution (vi)
Consider the input 𝑋 on 𝑛 points: 𝑥0 < 𝑥1 < ⋯ < 𝑥𝑛−1
𝐺 denotes greedy solution; 𝑂 denotes an optimal solution. Let 𝑔𝑖 and 𝑜𝑖 be the stops the two algorithms make, in order.
𝐺=𝑔 ,𝑔 ,...,𝑔 and 𝑂=𝑜 ,𝑜 ,...,𝑜 ′ 12𝑘 12𝑘
Observation 1: 𝑔 ,...,𝑔 is the Greedy solution for input 𝑥 ,𝑥 ,...,𝑥 . 2 𝑘 𝑔1 𝑔1+1 𝑛−1
Observation 2: 𝑂′ = 𝑔 ,𝑜 ,𝑜 ,...,𝑜 ′ is also an optimal solution for 𝑋.
Observation 3: 𝑜 ,𝑜 ,...,𝑜 ′ is an optimal solution for 𝑥 ,𝑥 ,...,𝑥 . 2 3 𝑘 𝑔1 𝑔1+1 𝑛−1
We will prove optimality of Greedy by induction on 𝑛.
We assume that Greedy is optimal on all problems on set size < 𝑛.
Now consider any problem of size 𝑛.
𝐺 is Greedy solution; 𝑂 is any optimal solution.
Solution (vii)
We assume that Greedy is optimal on all problems on set size < 𝑛.
𝐺=𝑔 ,𝑔 ,...,𝑔 and 𝑂=𝑜 ,𝑜 ,...,𝑜 ′ 12𝑘 12𝑘
Observation 1: 𝑔 ,...,𝑔 is the Greedy solution for input 𝑥 ,𝑥 ,...,𝑥 . 2 𝑘 𝑔1 𝑔1+1 𝑛−1
Observation 2: 𝑂′ = 𝑔 ,𝑜 ,𝑜 ,...,𝑜 ′ is also an optimal solution for 𝑋. 123 𝑘
Observation 3: 𝑜 ,𝑜 ,...,𝑜 ′ is an optimal solution for 𝑥 ,𝑥 ,...,𝑥 . 2 3 𝑘 𝑔1 𝑔1+1 𝑛−1
Observation 4: 𝑔 ,...,𝑔 is an optimal solution for 𝑥 ,𝑥 ,...,𝑥
2 𝑘 𝑔1 𝑔1+1 𝑛−1
From Observation 1 and induction hypothesis on Greedy correctness.
Observation 5: 𝑘 − 1 = 𝑘′ − 1 From Observations 3 and 4.
⇒ 𝑘 = 𝑘′ ⇒ greedy is optimal for our original set!
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com