Dynamic Programming DAG Shortest Path
2021-01-27 CSC373 Winter 2021 – Sam Toueg 1
DAG Problem
• FindshortestpathfromtheroottoanyleafinthisweightedDAG:
9 277
4469 321 583
11 12
!”# = 3 + 1 + 3 + 2 = 9 *+,,-. = 1 + 5 + 3 + 2 = 11
1552 1339
5
8 10
13 14
96
38
4 15
• IdeaI—SimpleGreedyAlgorithm
• Startattherootandateachlevelfollowtheedgewithlowestcost
2021-01-27 CSC373 Winter 2021 – Sam Toueg 2
DAG Problem
• FindshortestpathfromtheroottoanyleafinthisweightedDAG:
*=4 *=3 *=2 *=1 *=0
•T0=2
!”#$%&# 9 11 • Τ4 =25T4−1 +c
2 7 7 12 !4469
=2(25T4−2 +2)+2 =2!5T4−2 +252+2
=2″5T0 +2″#$52+⋯+252+2 = 2 (2″ + 2″#$ + ⋯ + 2 + 1)
3 2 1 3
5 8 3
5 2 13
3 9 !”#$'()! #5
1
1 5
3 14
968 !!”##$”%$”
810
height 4 = 4 4 15 •
=2!#$=252 −1=Θ(2)
• IdeaII—Naïverecursion
• !”#$ % : length of shortest path from % to a leaf.
There are 2″ different paths
• The algorithm looks at all of them!
Compute it recursively: • +,-. / = min{+,-. 23/456 / + 89:456(/), +,-. 23/4>9?2 / + 89:4>9?2(/)}
• +,-. 1 = min{+,-.(2) + 3, +,-.(3) + 1}
2021-01-27 CSC373 Winter 2021 – Sam Toueg 3
Time complexity?
DAG Problem
• FindshortestpathfromtheroottoanyleafinthisweightedDAG: *=4 *=3 *=2 *=1 *=0
0
9 11 •Τ”=”+1+”+&&&+2+1&c 92770 •Τ”=Θ”1
7
64 46 39 12
9 3 2 1 5 5 8 3 0
•DAGhasΘ”1nodes
• Sothetimecomplexityisnowlinear
10 5 5 2 2 13 137390
1
4 15
• Idea III — Dynamic Programming
• Avoid re-solving the same subproblems multiple times! How? One way: compute B!C#(D) bottom-up instead of top-down
inthesizeoftheproblem! 9 6 5 4 38 14 4+1=5leafs
810 0
height 4 = 4
ForD ←15FG11HG +,-.(D)←0 For D ← 10 FG 1 HG
+,-.(D) ← min{+,-. 23/456 D
2021-01-27
{*thesearetheleafnodes}
{* these are the internal nodes in bottom up order}
+ 89:456 D , +,-. 23/4>9?2(D) + 89:4>9?2(D)}
CSC373 Winter 2021 – Sam Toueg 4
Dynamic Programing
2021-01-27 CSC373 Winter 2021 – Sam Toueg 1
Overview
• Dynamic Programming (DP) works on problems that have optimal substructure property
Ø Optimal solution to a problem can be computed easily from optimal solution to subproblems.
• DP method:
Ø Break the problem down into subproblems, solve each
subproblem just once, and store their solutions.
Ø When solving a subproblem, another subproblem that we already solved may reoccur. If this happens, instead of recomputing its solution, simply look up its previously computed solution.
Ø This may save a lot of computation at the cost of a modest increase in storage space.
Ø Storing subproblem solutions is called “memoization” 2021-01-27 CSC373 Winter 2021 – Sam Toueg 2
How is DP method different from Divide & Conquer?
ØDivide & Conquer can be thought as a special case of DP where the subproblems that are solved never “overlap”
ØSo there’s no need for memoization to avoid recomputing some previously solved subproblems
CSC373 Winter 2021 – Sam Toueg 3
Dynamic Programming Weighted Interval Scheduling
2021-01-27 CSC373 Winter 2021 – Sam Toueg 4
Recall: Interval Scheduling
Problem
ØInput: ! intervals (“jobs’’), interval ” starts at time #! and finishes at time $! ØOutput: maximum-size set of intervals that do not overlap
!!
“!
Compatible
(i.e., that are “compatible’’)
2021-01-27
CSC373 Winter 2021 – Sam Toueg
5
!$
!”
“”
“$
!#
!%
“%
Not Compatible
“#
time
Weighted Interval Scheduling Problem
ØInput: ! intervals (“jobs’’), interval ” starts at time #! and finishes at time $! Each interval # has a weight $&
Ø Output: subset % of compatible intervals with maximum total weight ∑!∈# ‘! If all $& are equal, then this is simply the interval scheduling problem
Ø Greedy algorithm with earliest finish time ordering is optimal for this case If the $& are not equal, can we still use the greedy approach?
!! $ =1 “! !
!” $”=1 “” $$ =999 “$
!$
!% $%=1″% !# $# =1
“#
time
2021-01-27
CSC373 Winter 2021 – Sam Toueg
6
Weighted Interval Scheduling
Problem
ØInput: ! intervals (“jobs’’), interval ” starts at time #! and finishes at time $! Each interval # has a weight $&
Ø Output: subset % of compatible intervals with maximum total weight ∑!∈# ‘! If all $& are the same, then this is simply the interval scheduling problem
Ø Greedy algorithm based on earliest finish time ordering is optimal for this case If all $& are not the same, can we use the greedy approach again? ❌ no
!! $ =1 “! !
!$
!” $”=1 “” $$ =999 “$
!#
!%
$%=1 “% $# =1
ttottallweiightt=12000
“#
time
2021-01-27
CSC373 Winter 2021 – Sam Toueg
7
Weighted Interval Scheduling
What if we use another ordering?
ØBy weight: choose jobs with highest ‘! first
❌ no
!! $!=2 “!
!”$”=1″”!%$%=1″%!$ $$=1″$!#$#=1″#
• None of the above orderings work!
ØThey’re arbitrarily worse than the optimal solution
ØIn fact, under a certain formalization, “no greedy algorithm” can produce any “decent approximation” in the worst case (beyond this course!)
2021-01-27 CSC373 Winter 2021 – Sam Toueg 8
Weighted Interval Scheduling
• Convention
Ø Intervals are sorted by ascending finish time: $$ ≤ $% ≤ ⋯ ≤ $&
2021-01-27 CSC373 Winter 2021 – Sam Toueg 10
Weighted Interval Scheduling
• Convention
Ø Intervals are sorted by ascending finish time: $$ ≤ $% ≤ ⋯ ≤ $&
Ø*” =largestindex+<"suchthatinterval+iscompatiblewithinterval" (i.e., such that interval + finishes before interval " starts)
%1=0 %2=1 %3=1
%4=2 %5=1
!! $! "!
increasing finish time
2021-01-27
CSC373 Winter 2021 - Sam Toueg
11
!"
$" ""
!% $%
"%
!$ $$ "$
!# $# "#
Weighted Interval Scheduling
• The DP approach
Ø Let % be an optimal set of intervals (a ``solution’’) for intervals {1, ... , !}
ØTwo cases regarding the last interval !: oCase 1: Interval - is not in .
(in Fig, this is interval 5)
• . = optimal subset of intervals for intervals {1, ... , - − 1} oCase 2: Interval - is in .
• . does not contain incompatible intervals % - + 1, ... , - − 1
• . = {-} ∪ optimal subset of intervals for intervals {1, ... , % - }
Ø% is best of both
Ø Note: if we know the solution for every prefix {1, ... , "} of our ordering then we can solve the problem for {1, ... , !}
!! $! "!
Incompatible with 5
!" $" ""
Interval 5
2021-01-27
CSC373 Winter 2021 - Sam Toueg 13
!% $%
"%
!$ $$ "$
!# $# "#
Weighted Interval Scheduling
• The DP approach Ø234(")=maximumtotalweightofcompatibleintervalsin 1,...," ØBasecase"=0:234 0 =0
Ø Two cases regarding interval " > 0:
oInterval # is not selected: 678(#) = 678(# − 1) oInterval # is selected: 678(#) = $& + 678(% # )
Ø234(“)isbestofbothcases,i.e.,max 234 “−1 ,’! +234 * ” ØBellman equation:
678# =9 0
max 678 # − 1 , $& + 678 % #
if#=0 if # > 0
2021-01-27
CSC373 Winter 2021 – Sam Toueg
15
Weighted Interval Scheduling
Bellman equation:
678# =9 0 if#=0 max 678 # − 1 , $& + 678 % # if # > 0
Recursive algorithm:
sort intervals by ascending finish time: $$ ≤ $% ≤ ⋯ ≤ $& compute * 1 ,* 2 ,…,* ! (using binary search for each * + ) return R-OPT(!)
R-OPT(“): if ” = 0 do
return 0 else
return max{R-OPT(” − 1), ‘! + R-OPT(* ” )} Worst-case running time of R-OPT(!)?
maximumweightofcompatibleintervalsin 1,…,”
2021-01-27 CSC373 Winter 2020 16
Weighted Interval Scheduling
R-OPT(“):
if # = 0 do return 0
else
return max{R-OPT(# − 1), $& + R-OPT(% # )}
ØItispossiblethat% # =#−1foreach#
Ø Then, we call R-OPT(# − 1) twice in R-OPT # Ø So this might take 2′ steps
R-OPT(!)
R-OPT(! − 2)
⋮ R-OPT(0)
R-OPT(! − 2)
R-OPT(! − 2)
R-OPT(! − 2)
⋮
R-OPT(0)
– + 1
R-OPT(! − 1)
R-OPT(! − 1)
2021-01-27
CSC373 Winter 2021 – Sam Toueg
17
⋯
Weighted Interval Scheduling
R-OPT(“):
if # = 0 do return 0
else
return max{R-OPT(# − 1), $& + R-OPT(% # )}
ØItispossiblethat% # =#−1foreach#
Ø Then, we call R-OPT(# − 1) twice in R-OPT # Ø So this might take 2′ steps
ØBut we can avoid this bad case: if % # = # − 1 then algo only needs to compute $& + R-OPT(% # ) which is surely the max.
Ø Does this modification make the algo efficient?
ØNo: because it is possible that % # = # − 2 for each #, and in that case: ØRunningtime:8 – =8 -−1 +8 -−2
o Fibonacci, golden ratio, … J o& ! = ((*!), where * ≈ 1.618
2021-01-27 CSC373 Winter 2021 – Sam Toueg 18
Weighted Interval Scheduling
R-OPT(“):
if # = 0 do return 0
else
return max{R-OPT(# − 1), $& + R-OPT(% # )}
Why is the runtime high?
• Some subproblems are being computed many, many times, for example: oR-OPT(5) calls both R-OPT(4) and R-OPT(%[5])
oSo if %[5] = 3, then R-OPT(5) calls both R-OPT(4) and R-OPT(3)
oBut R-OPT(4) itself calls R-OPT(3) again…
Avoid recomputations with “memoization’’:
• Remember what you’ve already computed and re-use it if needed again
2021-01-27 CSC373 Winter 2021 – Sam Toueg 19
Weighted Interval Scheduling
Dynamic Programming: Bottom-Up
Ø Find an order to compute sub-problems so that
their solutions are ready when needed
678 # = max weight for intervals in 1, … , #
678# =9 0
max 678 # − 1 , $& + 678 % #
if#=0 if # > 0
BOTTOM-UP(! weighted intervals):
sort intervals by finish time: $$ ≤ $% ≤ ⋯ ≤ $& compute * 1 ,* 2 ,…,* ! via binary search 234 0 ← 0
for”=1to!do 6 –
6 -log- 6 -log-
array
234” ←max{234[“−1],’!+234[*”]} 6(1) previously computed values
ØTimecomplexity? 6 -log-
2021-01-27 CSC373 Winter 2021 – Sam Toueg 20
Weighted Interval Scheduling
Dynamic Programming: Top-Down time complexity: 6 – log –
TOP-DOWN(! weighted intervals):
sort intervals by finish time: $$ ≤ $% ≤ ⋯ ≤ $& compute * 1 ,* 2 ,…,* ! via binary search 234 0 ← 0 global array
return TD−OPT(!) 6 –
TD−OPT(“)
if234″ isnotinitializeddo
6 -log- 6 -log-
234 ” ← max{TD−OPT(” − 1), ‘! + TD−OPT(* ” )} return 234 ”
• OPT[#] is computed at most once for each #
⇒ TD-OPT(-) takes only 6 – time (think why…)
2021-01-27 CSC373 Winter 2021 – Sam Toueg 21
Weighted Interval Scheduling
• The previous algorithms only gave us the maximum total weight
• What about the actual solution (optimal subset of intervals)?
• It can be done by computing simultaneously (for each subproblem): Ø(a) the maximum total weight, and
Ø(b) a subset of intervals that gives this weight
BOTTOM-UP(! weighted intervals):
sort intervals by finish time: $$ ≤ $% ≤ ⋯ ≤ $& compute * 1 ,* 2 ,…,* ! via binary search 234 0 ← 0 ; %[0] ← ∅
for ” = 1 to ! do
234 ” ←max{234[“−1],’! +234[* ” ]} if234 ” =234[“−1]
then% ” ←%[“−1] else % ” ← ” ∪ % * ”
2021-01-27
CSC373 Winter 2021 – Sam Toueg 23
Weighted Interval Scheduling
• The previous algorithms only gave us the maximum total weight
• What about the actual solution (optimal subset of intervals)?
• We can also compute it after computing the maximum weight array 234
Ø OPTIMAL-SET(234): %←∅
+←!
while + ≠ 0 do
if234 + =234 +−1 then + ← + − 1 else%←%∪ +
Optfor 1,…,J doesnotincludeJ
Optfor 1,…,J includesintervalJ
+←*+ soitdoesnotincludeintervals %J +1,…,J−1
return %
Whyisthecomputed.optimalforintervals 1,…,-?Think…
2021-01-27 CSC373 Winter 2020 25