程序代写代做代考 AI algorithm CSC373H Lecture 4

CSC373H Lecture 4
Dan Zingaro
October 3, 2016

Back to Activity Scheduling
􏹩 Input:setofactivitiesa1,a2,…,an
􏹩 Each activity ai has a start time si , finish time fi , and
nonnegative profit (or worth) wi
􏹩 Output: subset of activities S such that no activities in S overlap and profit(S) is maximum

Greedy Strategies
This time, greedy by finish time doesn’t work.
Simplest counterexample:
[0, 4) with profit 1, [0, 5) with profit 3
Taking the 1-profit prevents us from taking the 3-profit.

Greedy Strategies…
Let’s try greedy by maximum unit profit (i.e. profit divided by duration).
Doesn’t work. Simplest counterexample:
[0, 4) with profit 1, [0, 20) with profit 3
The 1-profit has a better ratio, but it prevents us from taking the 3-profit!

Recursive Formulation
􏹩 Greedy strategies are not going to work here
􏹩 But we can come up with a recursive formulation of the
problem. Maybe that will help?
􏹩 Start by sorting activities by increasing finish time
􏹩 Consider optimal schedule S. There are two possibilities for activity an
􏹩 an∈S,or 􏹩 an̸∈S

Recursive Formulation…
􏹩 If an ∈ S, then the rest of S consists of optimally scheduling the activities that finish before an starts
􏹩 If an ̸∈ S, then S consists of optimally scheduling a1,a2,…,an−1
define p[i] to be the largest index j such that a_j
does not overlap a_i
# Return maximum possible profit from a_1,…,a_n
def rec_opt(n):
if n == 0:
return 0
else:
return max(rec_opt(n-1), w_n + rec_opt(p[n]))

Runtime of Recursive Version
􏹩 Consider a set of n activities where there is no overlap at all
􏹩 ThenT(n)=2T(n−1)+c
􏹩 This recurrence has an exponential closed-form, O(2n)!
􏹩 So, we’ve solved the problem, but in practice it is only useful for small instances or instances with lots of overlap

Solution 1: Memoization
􏹩 Observation: there are only n + 1 subproblems to solve 􏹩 rec_opt(0), rec_opt(1), …, rec_opt(n)
􏹩 So, since our recursive algorithm has exponential runtime, we must be solving those same n + 1 subproblems over and over
􏹩 memoization: store solutions to subproblems in an array so that they can be looked-up rather than recomputed

Solution 1: Memoization…
Let OPT[i] = max profit from scheduling {a_1,…,a_i}
OPT[0] = 0
OPT[1..n] = unknown
def mem_opt(n):
if OPT(n) is unknown:
OPT[n] = max(mem_opt(n-1), w_n + mem_opt(p[n]))
return OPT[n]

Solution 1: Memoization…
􏹩 Therearenowatmostn+1recursivecalls
􏹩 Each call does a constant amount of work before possibly
making a recursive call
􏹩 Ignoring the time for sorting, we have an O(n) algorithm now
􏹩 This is the best time complexity we can get, but not the best implementation
􏹩 Overhead of recursive calls
􏹩 With many activities, recursion depth limit might be reached
􏹩 Can we eliminate the recursion altogether?

Solution 2: Dynamic Programming
A bottom-up algorithm.
def dyn_opt(n):
OPT[0] = 0
for i in [1,2,…,n]:
OPT[i] = max(OPT[i-1], w_i + OPT[p[i]])
return OPT[n]

Recovering the Activities
􏹩 So far, our dynamic-programming algorithm gives us the maximum profit, but not the activities that give us this profit
􏹩 We can use the information in OPT to recover the set of activities
􏹩 If OPT[i] == OPT[i-1], then the profit using the first i − 1 activities is the same as the profit using the first i activities
􏹩 So, activity i is not included 􏹩 Otherwise, activity i is included
􏹩 . . . and we then continue checking with activity p[i]

Recovering the Activities…
S = {}
i=n
while i > 0:
if OPT[i] == OPT[i-1]: # i not included i=i-1
else: # i included
S = S + {i}
i = p[i]

Dynamic Programming
Dynamic programming applies to an optimization problem when we have
􏹩 Optimal substructure: an optimal solution to a problem consists of optimal solutions to subproblems
􏹩 Overlapping subproblems: subproblems are repeated many times in the recursive formulation of larger problems
􏹩 Independent subproblems: solution to one subproblem does not affect the solution of another subproblem

Dynamic Programming Steps
Step 1: describe recursive structure of problem
􏹩 How can problem be decomposed?
􏹩 How does the optimal solution to the problem relate to the optimal solutions of the subproblems?
Step 2: define array for the subproblems whose optimal values will be stored
􏹩 This can be a 1d array (e.g. profit scheduling) or a multi-dimensional array
Step 3: using step 1, describe how the array values from step 2 are related

Dynamic Programming Steps…
Step 4: write iterative algorithm using step 3
􏹩 The algorithm is bottom-up (no recursion)
􏹩 It calculates optimal values for each array element
Step 5: use the array to recover the solution that yielded the optimal
􏹩 This adds code to step 4
􏹩 It may require storing additional information in step 4

Knapsack Problem
􏹩 In the knapsack problem, we have n items, each with a value vi and a weight wi
􏹩 Assume that all wi are positive integers
􏹩 We also have a weight capacity W of the knapsack
􏹩 The goal is to maximize the value of items put in the knapsack with the constraint that the weights of the items add up to at most W

Knapsack: Greedy?
Here are two ideas for possible greedy algorithms: 􏹩 Sort from highest vi to lowest vi
􏹩 Sort from highest vi /wi to lowest vi /wi
Unfortunately these are not correct. 􏹩 Let’s find counterexamples

Knapsack: Step 1
On to dynamic programming!
􏹩 Order the items in some arbitrary way
􏹩 Consider an optimal solution S. Two possibilities for item n:
􏹩 ItisnotinS 􏹩 ItisinS
􏹩 We don’t know which option is correct, so we will have to try both
􏹩 We will then choose the one that gives us the better solution

Knapsack: Step 1…
Optimal substructure of Knapsack.
􏹩 Suppose that the optimal solution S does not contain item n
􏹩 Then S must contain within it an optimal solution to the Knapsack problem using only the first n − 1 items
􏹩 Why?
􏹩 Suppose that there were a better solution for the first n − 1
items than the one used in S
􏹩 Then we could use that as a better solution than S —
contradiction!

Knapsack: Step 1…
􏹩 Now suppose that the optimal solution S does contain item n
􏹩 We argue that S must contain within it an optimal solution to the Knapsack problem using the first n − 1 items with a knapsack capacity of W − wn
􏹩 Why?
􏹩 Suppose that there were a more valuable solution for the first
n − 1 items that fits in a knapsack of capacity W − wn
􏹩 Then we could take that solution, add item n, and have a
better solution than S — contradiction!

Knapsack: Step 2
􏹩 We have a 2d array this time
􏹩 One dimension indexes the allowable items
􏹩 The other dimension indexes the allowable weight
􏹩 N[i,j] is the most value that we can get from items 1 to i in knapsack of weight j

Knapsack: Step 3
􏹩 If number of allowed items or max allowable weight is 0, then optimal value is 0
􏹩 Otherwise, we try including and excluding item i and pick the best one
􏰎0, if i = 0 or j ≤ 0 max{N[i−1,j],N[i−1,j−wi]+vi} ifi>0andj>0
N[i,j] =

Knapsack: Step 4
􏹩 There are only nW subproblems, but they would be solved repeatedly by a naive recursive algorithm
􏹩 Instead, we use a bottom-up dynamic programming approach
􏹩 We must solve smaller subproblems before solving larger
subproblems
􏹩 i.e. We must fill-in the array in such a way that N[i − 1, j] and N[i −1,j −wi] are present before N[i,j] is computed

Knapsack: Step 4…
def knapsack(v, w, n, W):
for j in [1, 2, …, N]:
N[0, j] <- 0 for i in [1, 2, ..., n]: N[i, 0] <- 0 for i in [1, 2, ..., n]: for j in [1, 2, ..., N]: N[i, j] <- max(N[i-1, j], N[i-1, j - w[i]] + v[i]) return N[n, W] Knapsack: Step 5 def recover(N, w, n, W): i=n j=W result = [] while i > 0:
if N[i, j] == N[i-1, j]: i=i-1
else: result.append(i) j = j – w[i] i=i-1
return result