Dynamic Programming
We already talked about dynamic programming and how MergeSort and QuickSort and even BinarySearch and RandomizedSelect are examples of that kind of algorithms: divide into pieces, solve each one, then merge the solutions.
Ch.15 is a little different version of the same thing. The algorithms are not recursive in the same way we saw before. The structure of divide-conquer-merge is still there, but the DIVIDE is not a "clean" one-cut divide like we saw before. MergeSort divides exactly in half, always. QuickSort divides into two "halves" exactly at the point where Partition calculates the cut to be.
But Ch.15 algorithms do not have such a clean cut... Instead, they TRY EVERY POSSIBLE CUT, and then pick the best one. That's where the "minimum out of many numbers" algorithm was needed for the Review Homework. We will use it here.
The consequence of trying every possible cut is that different cuts can overlap. Therefore, the issue that makes dynamic programming problems a special case of divide-and-conquer problems is that the divide is so variable, and leads to overlapping subproblems.
The reason why Ch.15 algorithms work in that way is because they are optimization algorithms. Therefore, they have to find the best solution.
When you read the assembly line problem, try to visualize all different possibilities for going from start to end. Dynamic programming algorithm is really an intelligent brute force method that will try all possible paths to find the shortest one.
Therefore, the first part of solving a dynamic programming problem is to come up with a formula that describes the subproblems. In this class, we are not too interested in becoming extremely proficient with discerning what the formula should be.
The interesting part about Ch.15 is going from formulating problems in math notation to coding. You will notice that the math formula can be coded in two ways: recursively (assembly line recursive code is in the notes on the web) and iteratively (in the book). This part is of great interest to us in this class, and we will focus a lot of attention on it. Why? Because there are tremendous consequences if we code the formula one way or the other.
Recursive code can be “plain” recursive where everything is calculated “as needed” and then discarded (think of it as “use once and throw away”), versus recursive code where returned results are stored for future use. That kind of code is called “memoized.” Mini quiz: what issue is the memoized code trying to solve?
Dynamic Programming Example: Assembly Line
Goal: assembly a car as fast as possible, using two “identical” assembly lines, each with n machines.
ei: time to enter a line i=1, 2
xi: time to exit a line
aij : time to process a job at station Sij i=1, 2 j= 1, …, n
tik: time to transfer from line i after having gone through station Sik i=1, 2 k= 1, …, n-1
f*: fastest time through the whole factory
f[i, j]: fastest time through station j on line i i=1,2 j = 1, 2, …., n.
lineij: line whose station j-1 was used in a fastest way through Sij i=1, 2 j= 2, …, n
l*: line whose station n was used in the fastest way through the whole factory
Dynamic programming solution: decide beforehand how to split the problem into independent (and most likely related and overlapping) optimal subproblems. Then solve the subproblems bottom-up, remembering the intermediate solutions.
Steps:
- Define the structure of the optimal solution
- Write recursive formula describing the optimal solution
- Compute the formula bottom-up
- Construct the optimal solution from computed information
In the case of assembly line:
- write the formula for the fastest way through station Sij
- using formula from 1, write recursive formula to calculate the fastest time through the whole factory
- write pseudocode to calculate the fastest time through factory is (e.g. 10 hours)
- calculate the fastest route through the factory (e.g. for n=3, through stations S11, S12, andS23).
Greedy algorithm solution: at each decision point, make a choice that looks the best at the moment, hoping that the final solution will be optimal. Solve the resulting subproblems top-down, and do not remember them.
So, we have to write the algorithm to calculate the fastest time through the factory.
FastestTimeTruFactory
a[2][n]
t[2][n-1]
e[2]f*, l*,
x[2]list of stations in the shortest path (n long)
n
There are several ways in which we can write this algorithm. We can write it recursively top-down, or we can write it iteratively bottom-up. It is usually easier to start recursively, because it matches the informal human way of thinking.
Recursive call should return f*.
f* = min(f[1,n] + x1 , f[2,n] + x2 ) // we either come off line 1 or line 2
f[1, n] = min(f[1, n-1] + a1,n , f[2, n-1] + t2,n-1 + a1,n ) // we either come directly from the previous
//station on line1, or we come from the //previous station from line 2 and transfer from //line 2 to line 1.
So we have to keep on “unwrapping” backwards. In general, we write a recursive function:
f[1, j] = min(f[1, j-1] + a1,j , f[2, j-1] + t2,j-1 + a1,j )
f[1,1] = e1 + a1,1
And call it with the initial call of f[1,n].
How to map math into code:
Calcf*(a,t,x,e,n) {
return min(Calcf(a,t,x,e,n, 1, n) + x[1], Calcf(a,t,x,e,n, 2, n) + x[2])
}
Calcf(a,t,x,e,n, 1, j) {
If j==1
Return a[1][1]+e[1]
.
return min(Calcf(a,t,x,e,n, 1, j-1) + a[1][j], Calcf(a,t,x,e,n, 2, j-1) + t[2][j-1] + a[1][j])
}
Calcf* = min(CalcfWITHSTORAGE(…,1,n) +x[1] , CalcfWITHSTORAGE(…,2,n) + x[2])
CalfWITHSTORAGE(….) {
Check if we have it
If yes, return it
Else calculate, store, return
}
MainCalcWITHSTORAGE (…) {
Initialize f[ ][ ] to _____
}
CalfWITHSTORAGE() {
If f[ ] [ ] is not empty, we already have the solution
Return f[ ] []
Else
If j==1
f[1,1] = a[1][1]+e[1]
Return f[1,1]
f[1,j-1] = .CalcfWITHSTORAGE(a,t,x,e,n, 1, j-1)
f[2, j-1] = CalcfWITHSTORAGE(a,t,x,e,n, 2, j-1)
return min(f[1, j-1] + a[1][j], f[2, j-1] + t[2][j-1] + a[1][j])
}
Then of course we have to write function Calcf(a, t, x, e,n, 2, j) which is a mirror image of
Calcf(a,t,x,e,n, 1, j).
BTW, It is also possible to write the algorithm using functions Calcf1(a, t, x, e,n, j) and Calcf2(a, t, x, e,n, j).
So far so good; this code will return the fastest time through the factory, for example 5 hours. But we will not know which stations to go though to achieve this fastest time. So, we have to modify the code to make sure to remember which stations we passed through. Therefore, we cannot use the min function “out of the box”, we have to write min from scratch and remember which side gave us the minimum.
//assume line[][] and l* are globals
Calcf*(a,t,x,e,n) {
if (Calcf(a,t,x,e,n, 1, n) + x[1] <= Calcf(a,t,x,e,n, 2, n) + x[2]) {
f* = Calcf(a,t,x,e,n, 1, n) + x[1]
l* = 1 // the car came off line 1
}
else {
f* = Calcf(a,t,x,e,n, 2, n) + x[2]
l* = 2 // the car came off line 2
}
return f*
}
Calcf(a,t,x,e,n, 1, j)
if (Calcf(a,t,x,e,n, 1, j-1) + a[1][j] <= Calcf(a,t,x,e,n, 2, j-1) + t[2][j-1] + a[1][j]) {
line[1, j] = 1
f[1,j] = Calcf(a,t,x,e,n, 1, j-1) + a[1][j]
}
else {
line[1, j] = 2
f[1,j] = Calcf(a,t,x,e,n, 2, j-1) + t[2][j-1] + a[1][j])
}
return f[1,j]
}
This code works, however it is going to be very slow, because it keeps on calculating the same quantities over and over again. As soon as a quantity is calculated, it is discarded – we do not store it anywhere - so when we need it the next time, we have to calculate it again.
A remedy for that is to save everything we calculate, and when we need it the next time, just pull it out of the storage. This approach is called “memoized.” Memoized approach is the recursive approach with the storage.
The algorithm is:
Initialize storage
Make the initial call
MemoizedCalcf( …, 1, j) {
if f[1,j] is not empty, return it
else calculate it recursively (watch out, the recursive call will be to MemoizedCalcf)
}
The third way is to calculate it iteratively, using bottom up approach. That code is in the book.
// Iterative version
//The fastest way through a factory with 2 assembly lines
// From the textbook, p.329
//Input:
//matrices a and t; a is of size 2xn, t is of size 2xn-1.
//vectors e and x, of size 2
//integer n (number of stations)
//
//Output:
//real number f*, the fastest time through the whole factory
//integer l*, the line whose station was used to pass through nth station
//matrix f[ , ] of size 2xn; or vectors f1[] and f2[] of size n, containing fastest times through each station
//matrix line[ , ] of size 2xn-1 or vectors line1[] and line2[] of size n-1, containing the fastest path through each station
FASTEST-WAY(a, t, e, x, n) {
f1,1 = e1 + a1,1//can be coded as: f[1,1] = e[1] + a[1,1]
//or:f1[1] = e[1] + a[1,1]
f2,1 = e2 + a2,1
for j = 2, n
if ( f1,j-1 + a1,j ≤ f2,j-1 + t2,j-1 + a1,j ) //line 1 is faster
f1j = f1,j-1 + a1j
line1j = 1//code as: line[1,j] or line1[j]
else//line 2 is faster
f1,j = f2,j-1 + t2,j-1 + a1,j
line1,j = 2
if ( f2,j-1 + a2,j ≤ f1,j-1 + t1,j-1 + a2,j ) // line 2 is faster
f2,j = f2,j-1 + a2,j
line2,j = 1
else//line 1 is faster
f2,j = f1,j-1 + t1,j-1 + a2,j
line2,j = 2
if (f1,n + x1 ≤ f2,n + x2 )
f* = f1,n + x1
l* = 1
else
f* = f2,n + x2
l* = 2
}
How do we know which stations are in the shortest path? Again, we have to use a recursive approach.
l* tells what line was used for station n.
l[i,j] tells what line was used for station j-1 when getting to station j on line i.
So, we need:
l* // this is line for station n
l[l*, n]//this is line for station n-1
l[l[l*,n], n-1] //this is line for station n-2
…
How do we read that from line[][] matrix?
l* tells us which line to read for station n-1, etc. keep on backtracking.
For example:
l*=2, n=3
line = NIL 2 2 //NIL means that line[1,1] and line[2,1] don’t exist
NIL 1 1
l*=2 means that we got off station S2,3
So we look up l[2,3] which is 1, which means we came through S1,2
So we look up l[1, 2], which is 2, which means we came through S2,1
So the shortest path through factory is S2,1 S1,2 S2,3
This is a very important approach that we will use for the majority of algorithms for the rest of the semester.
PRINT-STATIONS(line, n) {
i = l*
print “line “ i “, station “ n
for (j = n, j ≥ 2, j—)
i = linei,j
print “line “ i “, station “ j-1
}