Those who cannot remember the past are doomed to repeat it.
— , The Life of Reason, Book I:
Introduction and Reason in Common Sense (1905)
Copyright By PowCoder代写 加微信 powcoder
The 1950s were not good years for mathematical research. We had a very interesting gentleman
in Washington named Wilson. He was secretary of Defense, and he actually had a pathological
fear and hatred of the word ‘research’. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term ‘research’ in his presence. You can imagine how he felt, then, about the term ‘mathematical’. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose?
— , on the origin of his term ‘dynamic programming’ (1984)
STUDY MATERIAL:
• [CLRS] chapter 15
• Lecture Note 9
• Algorithmics Animation Workshop:
Optimum Static Binary Search Tree
Recursion Tree Pruning by Memoization Recursive Back-Tracking
Dynamic Programming
Problems:
Fibonacci Numbers
Shortest Paths in a Layered Network
Weighted Event Scheduling
Knapsack
Longest Common Subsequence
Matrix Chain Multiplication
Optimum Static Binary Search Tree
Optimum Polygon Triangulation
More Graph Optimization problems considered later
Memoization
We have done this sub-instance already, haven’t we?
Did you take any memo of its solution? Let’s re-use that solution and save time by not re-doing it.
That’s a great time saver, since we have many many repetitions of such sub-instances!
Recursion Tree
Re-occurring Sub-instances
In divide-&-conquer algorithms such as MergeSort,
an instance is typically partitioned into “non-overlapping” sub-instances (e.g., two disjoint sub-arrays). That results in the following property:
For any two (sub) sub-instances, either one is a sub-instance of the other (a descendant in the recursion tree), or the two are disjoint & independent from each other.
We never encounter the same sub-instance again during the entire recursion. If the sub-instances “overlap”, further down the recursion tree we may encounter
repeated (sub) sub-instances that are in their “common intersection”.
Example 1: The Fibonacci Recursion tree (see next slide). Example 2: Overlapping sub-arrays as sub-instances.
Fibonacci Recursion Tree
Algorithm F(n)
if n{0,1} then return n
return F(n-1) + F(n-2) end
But only n+1 distinct sub-instances are ever called:
T ( n ) T ( n 1 ) T ( n 2 ) ( 1 ) n 2 (1) n 0,1
T(n) (F ) (φn ). n
F(0), F(1), …, F(n-2), F(n-1), F(n).
Why is it taking time exponential in n?
F(97) F(97) F(96) F(96) F(95) F(96)
F(96) F(95) F(95) F(94)
F(95) F(95) F(94) F(94) F(93)
F(95) F(94)
Pruning by Memoization
Algorithm Fib(n)
for t 0 .. 1 do Memo[t] t
for t 2 .. n do Memo[t] null
return F(n) end
Function F(n)
if Memo[n] = null then Memo[n] F(n-1) + F(n-2)
return Memo[n] end
Recursion tree evaluated in post-order. Now all right sub-trees are pruned. Instead of re-solving a sub-instance, fetch its solution from
§ initialize Memo[0..n] table
§ recursion structure kept § memo feature added
F(n-1) F(n-2)
the memo table Memo[0..n].
T(n) = (n). Time-space trade off.
F(n-4) F(n-4) F(n-5)
F(2) F(n-6) F(0)
Memoization: Recursive vs Iterative
Algorithm Fib(n)
for t 0 .. 1 do Memo[t] t
for t 2 .. n do Memo[t] null
return F(n) end
Function F(n)
if Memo[n] = null
§ recursive top-down F(n) F(n-1)
F(n-2) F(n-3)
F(n-3) F(n-4)
F(n-5) F(2) F(n-6)
then Memo[n] F(n-1) + F(n-2) return Memo[n]
Algorithm Fib(n) § iterative bottom-up (from smallest to largest) for t 0 .. 1 do Memo[t] t
for t 2 .. n do Memo[t] Memo[t-1] + Memo[t-2]
return Memo[n]
Compact Memoization
We want compact memos to save both time and space.
Fibonacci case is simple; memoize a single number per instance.
What if the solution to a sub-instance is a more elaborate structure? Examples:
1. Sub-instance solution is subarray A[i..j]: Just store (i,j), its first and last index.
2. Sub-matrix A[i..j][k..t]: Just store the 4 indices (i,j,k,t).
3. Solutions to sub-instances are sequences. Furthermore, any prefix of such a
sequence is also a solution to some “smaller” sub-instance.
Then, instead of memoizing the entire solution sequence, we can memoize its next-to-last (as well as first and last) elements.
We can recover the entire solution á posteriori by using the prefix property.
4. Single-source shortest paths.
If the last edge on the shortest path SP(s,v) from vertex s to v is edge (u,v), then memo s,u,v (and path length) for the solution to that sub-instance. We can consult the solution to sub-instance SP(s,u) to find “its” last edge, and so on. Á posteriori, working backwards, we can recover the entire sequence of vertices on the path from s to v.
Back-Tracking
I know my options for the first step. Can you show me the rest of the way?
OK. For each first step option, I will show you the best way to finish the rest of the way.
Thank you. Then I can choose the option that leads me to the overall best complete solution.
Solving Combinatorial Optimization Problems
Any combinatorial problem is a combinatorial optimization problem: For each solution (valid or not) assign an objective value:
1 if the solution is valid, 0 otherwise.
Now ask for a solution that maximizes the objective value.
Sorting: find a permutation of the input with minimum inversion count.
Greedy Method:
Fast & simple, but has limited scope of applicability to obtain exact optimum solutions.
Exhaustive Search:
A systematic brute-force method that explores the entire solution space. Wide range of applicability, but typically has exponential time complexity.
The Optimum Sub-Structure Property
(repeated from “Greedy” Slide, p. 33)
We just noticed an important property that will be used many times later:
The optimum sub-structure property: any sub-structure of an optimum structure is itself an optimum
structure (for the corresponding sub-instance).
Problems with this property are usually amenable to more efficient algorithmic solutions than brute-force or exhaustive search methods.
This property is usually shown by a “cut-&-paste” argument (see below).
Example 1: The Coin Change Making Problem.
Consider an optimum solution Sol OPT(S). Let G1 be a group of coins in Sol.
Suppose G1 FEAS(U). Then we must have G1 OPT(U). Why?
Because if G1 OPT(U), then we could cut G1 from Sol, and paste in the optimum sub-structure G2 OPT(U) instead. By doing so, we would get a new solution Sol’ FEAS(S) that has an even better objective value than Sol. But that would contradict Sol OPT(S).
Example 2: The Shortest Path Problem.
Let P be a shortest path from vertex A to vertex B in the given graph G.
Let P’ be any (contiguous) sub-path of P. Suppose P’ goes from vertex C to D.
Then P’ must be a shortest path from C to D. If it were not, then there must be an even shorter path P’’ that goes from C to D. But then, we could replace P’ portion of P by
P’’ and get an even shorter path than P that goes from A to B.
That would contradict the optimality of P.
Solving COP by Recursive Back-Tracking
Recursive Back-Tracking (RecBT):
a) Divide the solution space for a given instance into a number of sub-spaces. b) These sub-spaces must themselves correspond to one or a group of sub-
instances of the same structure as the main instance. c) Requirement: the optimum sub-structure property.
d) Recursively find the optimum solution to the sub-instances corresponding to
each sub-space.
e) Pick the best among the resulting sub-space solutions.
This best of the best is the overall optimum structure solution for the main instance.
Divide-&-Conquer and Recursive BT vastly differ on what they divide.
D&C divides an instance in one fixed way into a number of sub-instances.
RecBT divides the solution space into sub-spaces.
• This is done based on one or more sub-division options.
• Each option corresponds to one of the said sub-spaces.
• Each option generates one or more sub-instances whose complete
solution corresponds to the solution within the corresponding sub-space.
RecBT Solution Sub-Spaces Take best of these best solutions within each solution subspace
RecBT Recursion Tree
How should we divide the entire solution space into sub-spaces, so that each sub-space corresponds to a (smaller) instance or a group of (smaller) instances of the same type as the main problem we are trying to solve?
Recursion tree:
Its root corresponds to the main instance given.
There are two types of nodes:
• Sub-instance nodes appear at even depths of the recursion tree,
• Sub-division option nodes appear at odd depths of the recursion tree.
For a specific (sub-) instance node, we may have a number of options on how to further divide it into groups of (sub-) sub-instances.
For each such option, we have a sub-division option node as a child. Each option node has a group of children, each of which is a sub-instance node.
The leaves of the tree correspond to base case instances.
Examples follow ……………………………………………………… P.T.O.
Example 1: RecBT Recursion Tree 0/1 binary decision on a sequence X = x1, x2, … , xm.
A simple situation: each division option node generates a single sub-instance child.
x1, x2, … , xm, …
sub-division option level xm = 1
Instance level
x1, x2, … , xm-1, …
Instance level x1, x2, … , xm-1, …
Example 1: RecBT Recursion Tree 0/1 binary decision on a sequence X = x1, x2, … , xm.
A simple situation: each division option node generates a single sub-instance child. x1, x2, … , xm, …
x1, x2, … , xm-1, …
x1, x2, … , xm-1, …
Example 2: RecBT Recursion Tree Find optimum full parenthesization of (X1 X2 … Xk Xk+1 … Xn),
where is an associative binary operator and Xk’s are operands.
First, let’s see what a feasible solution looks like: It can be viewed by the full parenthesization,
or by its parse tree.
((X1 1 X2 )2 ((X3 3 X4 )4 X5))
(Note: parse tree recursion tree.) (((X1 1 (X2 2 X3))3 (X4 4 X5))
3 X5 X1 2 X4
X3 X4 X2 X3
Example 2: RecBT Recursion Tree
Find optimum full parenthesization of (X1 1 X2 2 … Xk k Xk+1 … n-1 Xn).
Decision: which of 1 , … , k , … , n-1 should be performed LAST, i.e, form the root of the parse tree?
Induces n-1 top level sub-division option nodes. (X1 1 …Xk k Xk+1 …n-1 Xn)
1 k (X1 1 … k-1 Xk)
(Xk+1 k+1 … n-1 Xn)
SHORTEST PATHS
LAYERED NETWORKS
Shortest s-t path in Layered Network
a1 8 a2 7 a3 4 a4 3 a5
b1 3 b2 2 b3 5 b4 6 b5
Layers 0..n in graph G. s = starting vertex at layer 0, t = terminal vertex at layer n. For now assume O(1) vertices per layer.
w(u,v) = weight (or length) of edge (u,v) in G.
SP(u,v) = shortest path in G from vertex u to v (as a sequence of vertices).
CostSP(u,v) = cost (or length) of SP(u,v).
Example: SP(a1,b4) = a1, b2, a3, b4
CostSP(a1,b4) = w(a1,b2) + w(b2,a3) + w(a3,b4) = 1+3+2 = 6.
3 algorithmic solutions:
Recursive Back-Tracking without Pruning
Recursive Back-Tracking with Memoized Pruning
Iterative Memoized Algorithm 22
Shortest s-t path in Layered Network
a1 8 a2 7 a3 4 a4 3 a5
b1 3 b2 2 b3 5 b4 6 b5
Optimum sub-structure property:
Any sub-path of a shortest path is a shortest path.
More specifically, removing the last edge of a shortest path results
in a prefix path with one less edge that is itself a shortest path. Last edge on SP(s,t) is either (a5, t) or (b5, t).
Option 1. (a5, t): The rest of SP(s, t) must be SP(s, a5). Option 2. (b5, t): The rest of SP(s, t) must be SP(s, b5).
SP(s, t) = best of { SP(s, a5), (a5, t) , SP(s, b5), (b5, t) }
CostSP(s, t) = min{ CostSP(s, a5) + w(a5, t), CostSP(s, b5) + w(b5, t) }
All sub-instances are of the form SP(s, u), where u is any vertex of G.
Shortest s-t path in Layered Network
Short-hand notation:
SP(u) = SP(s,u), for any vertex u of G. (Starting vertex is always s.)
CostSP(u) = CostSP(s,u)
p(u) = predecessor of vertex u on the shortest path from s to u. SP(u) = SP(p(u)), u by the optimum sub-structure property.
s p(u) u
FACT: SP(u) = SP(p(u)), u , where
p(u) { v | (v,u) is an edge in G }
p(u) = argmin v { CostSP(v) + w(v,u) | (v,u) is an edge in G } CostSP(u) = min v { CostSP(v) + w(v,u) | (v,u) is an edge in G }
= CostSP(p(u)) + w(p(u) ,u)
Recursive Back-Tracking without Pruning
a1 8 a2 7 a3 4 a4 3 a5
b1 3 b2 2 b3 5 b4 6 b5
Algorithm ShortestPath(G, s, u)
Pre-Cond: G = a weighted layered digraph, u = a vertex of G, s = source vertex. Post-Cond: output is SP(u), CostSP(u)
if u = s then return s, 0 § base case
§ CostSP(u) = min v { CostSP(v) + w(v,u) | (v,u) is an edge in G }
for each vertex vV(G) : (v,u)E(G) do
prefixSP, prefixCost ShortestPath(G, s, v)
if cost > prefixCost + w(v,u) then cost prefixCost + w(v,u);
return SP , cost end
SP prefixSP, u
2O(n) time.
Á Posteriori Print Shortest s-t Path a1 8 a2 7 a3 4 a4 3 a5
b1 3 b2 2 b3 5 b4 6 b5
SP , cost ShortestPath(G, s, t) 2O(n) time.
O(n) time.
Recursive Back-Tracking with Memoized Pruning Memo[V(G)] = an array indexed by V(G).
u V(G): Memo[u] = Memo.p[u] , Memo.CostSP[u] .
Algorithm ShortestPath(G, s, t) § G = a layered graph …
for each vertex u V(G) do Memo[u] nil,
Memo[s] nil, 0 SP(G, s, t) PrintSP(G, s, t)
Procedure SP(G, s, u)
if u = s then return
for each vertex vV(G) : (v,u)E(G) do
if Memo.CostSP[v] = then SP(G, s, v)
if Memo.CostSP[u] > Memo.CostSP[v] + w(v,u)
then Memo.CostSP[u] Memo.CostSP[v] + w(v,u); Memo.p[u] v
end-for end
§ Initialize memo table
§ base case
§ compute shortest paths § print shortest s-t path
§ base case
Recursive Back-Tracking with Memoized Pruning Memo[V(G)] = an array indexed by V(G).
u V(G): Memo[u] = Memo.p[u] , Memo.CostSP[u] .
Algorithm ShortestPath(G, s, t) § G = a layered graph …
for each vertex u V(G) do Memo[u] nil,
Memo[s] nil, 0 SP(G, s, t) PrintSP(G, s, t)
§ Initialize memo table
§ base case
§ compute shortest paths § print shortest s-t path
Procedure PrintSP(G, s, u)
Pre-Cond: G = a weighted layered digraph, u = a vertex of G, s = source vertex. Post-Cond: output is SP(u), the shortest path from s to u in G.
if u = nil then return § base case PrintSP(G, s, Memo.p[u])
Iterative Memoized Algorithm
The closer the layer of u is to s, the “lower” the sub-instance is in the recursion tree, the earlier we need to solve it iteratively “bottom-up”.
Solutions to larger sub-instances depend on the smaller ones.
Algorithm ShortestPath(G, s, t) for each vertex u V(G) do
p[u], Cost[u] nil, Cost[s] 0
for layer 1 .. n do
for each vertex u in layer do
§ G = a layered graph … § Initialize memo table
§ base case first
§ in a reverse order of dependency
PrintSP(G, t) end
for each vertex vV(G) : (v,u)E(G) do if Cost[u] > Cost[v] + w(v,u) then Cost[u] Cost[v] + w(v,u);
Procedure PrintSP(G, u)
if u = nil then return
PrintSP(G, p[u]); print u end
§ O(n) time § base case
PrintSP(G, t) end
(n) time a1 8 a2 7 a3 4 a4 3 a5
An Example Run
Algorithm ShortestPath(G, s, t) for each vertex u V(G) do
p[u], Cost[u] nil, Cost[s] 0
for layer 1 .. n do
for each vertex u in layer do
§ G = a layered graph … § Initialize memo table
§ in a reverse order of dependency
for each vertex vV(G) : (v,u)E(G) do if Cost[u] > Cost[v] + w(v,u) then Cost[u] Cost[v] + w(v,u);
2 10 6 10 9
a 6 = 1t 3
b1 3 b2 2 b3 5 b4 6 b5
9 3 5 8 12
The Optimum Sub-Structure Property (OSSP) is vital.
Example: Optimum simple paths in a given positively weighted graph G.
1. Longest Simple Paths. (simplicity excludes cycles on the path) 2. Shortest Simple Paths.
The 1st one does NOT have the OSSP, but the 2nd does! Path(s,t) = Path(s,u) , Path(u,t) (u is an intermediate vertex on the path)
Path(s,t) is longest s-t path does NOT imply that Path(s,u) is longest s-u path, nor that Path(u,t) is longest u-t path.
Path(s,t) is shortest s-t path does imply that Path(s,u) is shortest s-u path, and that Path(u,t) is shortest u-t path.
Explain the discrepancy!
In the 1st case, sub-instances interfere with each other (not independent). 31
s, u, v, t is the longest simple s-t path,
but the sub-path s, u is not the longest simple s-u path! Longest simple s-u path is s, v, u. Replacing s, u by s, v, u in s, u, v, t results in the non-simple path s, v, u, v, t.
WITHOUT CYCLES IN G, THIS WON’T HAPPEN!
EVENT SCHEDULING
A banquet hall manager has received a list of reservation requests for the exclusive use of her hall for specified time intervals. Each reservation also indicates how much they are willing to pay.
She wishes to make the most profit by granting a number of reservation requests that have no time overlap conflicts.
Help her select the maximum profitable conflict free time intervals.
Weighted Event Scheduling
Input: A set S = { I1, I2, ···, In} of n weighted event time-intervals Ik = sk , fk , wk , k =1..n, where sk < fk are start and finishing times, and wk > 0 is the weight of Ik.
Feasible Solutions: Any subset C S with no overlapping pair of intervals.
Objective Value: W(C) = sum of the weights of intervals in C.
Goal: Output a feasible solution C with maximum W(C).
Reminder: We studied a greedy solution for the un-weighted case, i.e., wk = 1, for k=1..n.
S = the weighted intervals shown below,
C = the set of blue intervals W(C) = 6 + 8 + 5 = 19.
(happens to be the unique optimum), (Note: the greedy strategy fails here.)
w2=6 w1= 2
w7= 10 w5= 8
w9= 2 w10= 5
w4= 7 w3= 3
w8= 5 w6= 4
w2=6 w1= 2
w7= 10 w5= 8
w9= 2 w6= 4 w10= 5
w4= 7 w3= 3
Implicit reduction to a special graph path problem:
fk 0 sm ignore transitive edges
sk wk fk fk sm Find longest path from f- to s+ :
Ik =sk ,fk,wk
w1s4 w4f4s8w8f8 f1
w3 f3 s6w6
Longest path in the graph
The digraph is acyclic OSSP holds for longest paths.
LP(u) = Longest path from source to node u.
W(u) = weight (or length) of LP(u) [ W(f- ) = 0 ] p(u) = predecessor of node u on LP(u).
FACT: LP(u) = LP(p(u)), u , where
sk fk0smwmfm
p(m) = k W(m) = W(k)+wm
Memo(Im) = p(m) , W(m) = p(sm) , W(fm) .
argmax k { W(fk) | (fk, sm) is an edge in G } W(p(sm)) = max k { W(fk) | (fk, sm) is an edge in G }
W(sm) + wm
Scan Order: Sort starting & finish
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com