《主题DynamicProgrammingIII.ppt》由会员分享，可在线阅读，更多相关《主题DynamicProgrammingIII.ppt（47页珍藏版）》请在三一文库上搜索。
1、1,主題: Dynamic Programming (III),DP 的進階概念 DP 與 multi-stage graph 的關係 DAG shortest path problem multi-dimensional DP multi-recurrence DP 例題講解: A.10604, H.91.6 歷年題目,2,DAG shortest path problem,給定一個 directed acyclic graph (DAG)，每條 edge 都有 weight (可能為負數)，求從起點 s 到其他 vertex 的 shortest path,a,s,b,c,d,e,5,3,
2、2,6,7,-1,2,4,-2,1,3,解題方法: DP,首先對給定的 DAG 進行 topological sort 使原圖得成為一個 multi-stage graph vertices 按照 stage 由小到大排好 edges 全部由小的 stage 指向大的 stage,a,s,b,c,d,e,5,3,2,6,7,-1,2,4,-2,1,4,解題方法 (cont.),若 vertex u 有 edge 指向 vertex v，則 u 為 v 的 predecessor 從 s 出發到任一個 vertex v 的可能走法，必然會經過某個 v 的 predecessor v 的 dist
3、ance 需要其 predecessors 的 distance,a,s,b,c,d,e,2,-2,1,e,5,解題方法 (cont.),要算出 v 的 distance，就要先算出每一個 predecessor u 的 distance，再加上 u 到 v 的 edge weight，然後從每個 predecessor 算出的總合距離中找出最小值 distv = min distu + weight(u, v), Boundary condition: dists = 0,u 到 v 有 edge,6,Example (bottom-up computation),0,2,6,5,3,2,-
4、2,1,0,2,6,5,-1,4,0,2,6,7,0,2,3,2,6,0,5,7,DP 與 multi-stage graph 的關係,DP 的特徵在於先把子問題的解算出來，再集合起來算出原問題的解，這種關係可以被表示成一個 multi-stage graph (不見得只能用格子之間的關係來敘述) 把每一個子問題變成一個 vertex 當子問題 A 需要用到子問題 B 的解，則 vertex A 有 edge 指向 vertex B (edge 可加上適當的 weight) recurrence 描述每一個 vertex 和其 predecessors 的關係 (top-down) 計算時，由
5、小到大一個一個 stage 完成 (bottom-up computation),8,Critical path problem,給定一個 DAG，每條 edge 都有 weight，在 graph 中找出一條最長的 path 沒有規定此 path 的起點 vertex,a,s,b,c,d,e,5,3,2,6,7,-1,2,4,-2,1,Length = 15,9,Solution,將每一個 vertex 都設為起點 (distance 為 0)，然後每一個 vertex 去計算可以往前連的多遠，recurrence 如下: distv = max distu + weight(u, v),
6、0 Critical path 也是一個 DP problem，其最佳解的長度即為所有 vertex 中，可以往前連到的最遠距離: maxdist(v) for all v,u 到 v 有 edge,10,Example: LCS,每個 vertex 的計算方式都是 max,Li, j = Li 1, j 1 + 1 if xi = yj maxLi 1, j, Li, j 1 if xi yj,11,Longest increasing sequence,之前教的做法是用原來的 sequence 和 sorted sequence 做 LCS 現在可以把每一個數字當成一個 vertex，若第
7、 i 個數字 第 j 個數字 (i j)，則 i 到 j 有 edge 且 weight = 1，如此會直接形成一個 multi-stage graph，其最佳解可經由 critical path 得到,3,4,2,6,3,5,4,1,7,12,Recurrence: LIS,lengthi = max lengthk + 1 雖然此 recurrence 一樣是 O(n2) 的時間，但 max 的部分還可以做的更快 從第一個 vertex (數字) 開始依序往後計算 用陣列 last 輔助算出每個 vertex i 的 length(i) 修正陣列 last 的內容,ak ai, k i,1
8、3,Last 陣列,Lastj: 存放現在已知所有 length = j 的 paths 中，終點 vertices 中值最小的數字,3,4,2,6,3,5,4,1,2,1,3,2,3,3,7,length,2,3,last,大小最多到 n,3 4 6 3 3 5 2 3 5 3 4 5 3 3 4 2 3 4 3 4 4,長度為 3 的 vertex 中最後那一個,4,14,計算 length(i),要算 vertex i 的 length，可以用 i 的數字 ai 在 last 中進行 binary search (last 中的數字一定會呈現遞增順序) 當 binary search 使
9、得 lastj ai lastj + 1，則 lengthi = j + 1 由於 ai 會變成是 length = j + 1 的 paths 中值最小的終點，所以令 lastj + 1 = ai 需要 n 回合，每回合 O(log n)，共 O(n log n),15,Example,3,4,2,6,3,5,4,7,1,2,1,3,2,3,3,7,4,length,4,last,3,4,2,6,3,5,4,7,1,2,1,3,2,3,3,7,4,4,3,3,4,2,6,3,5,4,7,1,2,1,3,2,3,3,7,4,length,4,last,3,4,3,4,2,6,3,5,4,7,1
10、,2,1,3,2,3,3,7,4,4,2,4,16,Example (cont.),3,4,2,6,3,5,4,1,1,2,1,3,2,3,3,7,4,length,4,last,2,4,6,3,4,2,6,3,5,4,1,1,2,1,3,2,3,3,7,4,4,2,3,6,3,4,2,6,3,5,4,1,1,2,1,3,2,3,3,7,4,length,4,last,2,3,5,3,4,2,6,3,5,4,7,1,2,1,3,2,3,3,7,4,4,2,3,4,17,Multi-dimensional DP,例題: A.10604 給定 m 種 (m 6) 化學藥劑，將任兩種組合在一起，會產
11、生其中一種藥劑以及一定的熱量 (可能為負數),1,0,3,-10,3,3000,3,-10,2,0,1,-500,3,3000,1,-500,3,0,chem,heat,chem,heat,chem,heat,1,2,3,1,2,3,特別注意: 此題目的測試資料並不一定對稱，可能會有 chemij chemji或 heatij heatji,18,例題講解 (cont.),現有 n 份藥劑 (n 10，而一種藥劑可有好幾份)，要組合到剩下 1 份為止，且不限制最後要剩下哪一種，在此條件下，求合成過程中可能產生的最少熱量 若有 4 份藥劑，分別為 1、2、2、3，則: (1 2) (2 3) 3
12、 (2 3) 3 1 1 -10 + -500 + 3000 = 2400 2 (1 (2 3) 2 (1 1) 2 1 3 -500 + 0 + -10 = -510,19,組合藥劑的範例,令 p(a1, a2, a3, , am) 代表第 i 種藥劑剩下 ai 份的子問題，0 ai n (table size 116) 如 1、2、2、3 的問題可用 (1, 2, 1) 代表 1 和 2 組合產生 3 由 p(1, 2, 1) 變 p(0, 1, 2) 1 和 2 各減少一個，然後產生一個 3 1 和 3 組合產生 3 由 p(1, 2, 1) 變 p(0, 2, 1) 2 和 2 組合產
13、生 2 由 p(1, 2, 1) 變 p(1, 1, 1) 2 和 3 組合產生 1 由 p(1, 2, 1) 變 p(2, 1, 0) 若表格不對稱，則還有更多可能的變化,20,Optimal substructure,每一種組合產生的子問題最佳解再加上此組合散發的熱量，從中取出最小值即為原問題的最佳解,1, 2, 1,0, 1, 2,0, 2, 1,1, 1, 1,2, 1, 0,-10,3000,0,-500,取最小值,21,Example,1, 2, 1,0, 1, 2,0, 2, 1,1, 1, 1,2, 1, 0,1, 0, 1,0, 1, 1,1, 1, 0,0, 0, 2,2,
14、 0, 0,0, 0, 1,1, 0, 0,總數為 4,總數為 3,總數為 2,總數為 1,multi-stage graph,0,boundary,22,Recurrence,令 h(a1, , an) 為 p(a1, , an) 最佳解的值 每個問題所使用的子問題隨表格而變化 很難決定填表順序，建議用 top-down 方式 Recurrence 的維度也隨 input 變化 不適用參數數量固定的 recursive call 方式,23,不定維度的 recursive call,用一個陣列 a 存放每一種藥劑剩下的數量，和 recurrence 的維度 m 一起當作 recursive
15、call 的參數 h(int *a, int m) 由於 m 對同一個 test case 而言是固定的，所以可以用 global variable 存放 當組合藥劑 i 和藥劑 j 時，ai 和 aj 都減 1，而 achemij 要加 1 C 語言的陣列是傳址呼叫， 所以原始值會被修改，所以在 recursive call 一個子問題得到解後要先還原,24,不定維度的 recursive call (cont.),int h(int *a) / 省略計算的部分 for (i = 1; i = m; i+) /省略檢查 ai 數量的部分 ai -; for (j = 1; j = m; j+
16、) /省略檢查 aj 數量的部分 aj -; achemij +; call h(a); / 計算子問題解並求最小值 achemij -; aj +; ai +; ,25,Multi-recurrence DP,Sequence alignment: 給定任意的兩個字串 X = x1x2xn 和 Y = y1y2ym，在兩邊分別加入空白，使兩字串對齊 要變成長度相同的兩個字串 X 和 Y 在同一個位置上，不可以同時有空白,C,A,G,C,A,C,T,T,G,A,G,C,G,T,G,X,Y,X,Y,C,A,G,C,A,-,C,T,T,G,-,-,-,-,A,G,C,G,T,G,X,Y,C,A,G
17、,C,A,C,T,T,G,-,A,G,C,-,G,-,T,G,26,Sequence alignment (cont.),任兩個字元 (包括空白) 在同一個位置 i 上對齊，就會得到一個相似度的分數 score(xi, yi) (由題目定義，正負都有可能) 一種對齊方式的分數，就是在所有位置上對齊的字元分數總合，最好的對齊方式是分數最高的對齊方式 (代表相似度最大),27,Example,舉例來說，如果字元相同可得 2 分，不相等要扣 2 分，而空白要扣 1 分,C,A,G,C,A,-,C,T,T,G,-,-,-,-,A,G,C,G,T,G,C,A,G,C,A,C,T,T,G,-,A,G,C,
18、-,G,-,T,G,2 4 2 1 1 5 = 1,2 5 2 1 1 3 = 5,28,Optimal substructure,令 si, j 代表 x1x2xi 和 y1y2yj 的最佳對齊分數,si, j,x1,xi,y1,yj,x1,y1,x1,xi,y1,yj,x1,xi,y1,yj,si 1, j 1,si, j 1,si 1, j,xi-1,yj-1,xi,yj,yj-1,xi-1,對齊,子問題,29,Recurrence,si 1, j 1 + score(xi, yj) si, j = max si, j 1 + score(空白, yj) si 1, j + score(
19、xi,空白) s0, 0 = 0 si, 0 = x1x2xi 全部對到空白的分數 s0, j = y1y2yj 全部對到空白的分數 填表總共需要 O(mn) 的時間,30,With gap penalty,空白不再是個別計分，而是有一個計分的 function g(len) 計算每一塊連續空白區段 (gap) 的得分，len 是指此區段的長度 g(len) 有幾種常見的形式: 每一段都只扣一個 constant 的值 每一段都要先扣一個起始值 wg，然後每一個空格再加上 ws wg + len ws 每一段都要先扣 wg，然後加上 log (len),31,Example,舉例而言，相等 2
20、 分，不相等扣 2 分，而 gap 起始值扣 wg = 4，每一個加 ws = 1,C,A,G,C,A,-,C,T,T,G,-,-,-,-,A,G,C,G,T,G,C,A,G,C,A,C,T,T,G,-,A,G,C,-,G,-,T,G,2 4 2 1 4 + 1 4 4 + 1 1= 3,2 5 2 1 + (-4 + 1) 3 = -1,32,錯誤的 recurrence,令 fi, j 為 x1x2xi 和 y1y2yj 的最佳對齊分數 fi 1, j 1 + score(xi, yj) fi, j = max fi, j k + g(k), for 1 k j fi k, j + g(k
21、), for 1 k i 雖然會把兩個字串對齊到長度相等，同時也不會有空白對空白的情形，但是這個 recurrence 在計算連續空白的分數時並不正確,用連續 k 個空白和 xi-k+1.xi 對齊,33,Example,假設 f3, 6 的最佳解是由 f3, 3 得到， 而且 f3, 3 的最佳解是由 f3, 1 得到 因為這個 recurrence 不能反應現在的狀態，所以有可能在同一個字串連續加入空白區段,1 3,1 6,f3, 6,1 3,1 3,f3, 3,4 6,3 格空白,1 3,1,f3, 1,2 3,2 格空白,實際上是連續 5 格空白，卻被分別計分,34,Multi-rec
22、urrence,根據現在的狀態來呼叫不同功能的 recurrence ai, j: 在將 xi 和 yj 對齊的情形下，x1xi 和 y1yj 最好的對齊分數 bi, j: 若在 X 加入空白的情形下， x1xi 和 y1yj 最好的對齊分數 ci, j: 若在 Y 加入空白的情形下， x1xi 和 y1yj 最好的對齊分數,x1,y1,xi-1,yj-1,xi,yj,x1,y1,xi,yj-k,yj-k+1yj,x1,y1,xi-k,yj,xi-k+1.xi+k,35,Multi-recurrence (cont.),ai, j 在將 xi 和 yj 對齊之後， 再來有三種選擇: 將 xi-
23、1 和 yj-1 對齊 ai 1, j 1 在 X 加入空白 bi 1, j 1 在 Y 加入空白 ci 1, j 1 ai 1, j 1 ai, j = score(xi, yj) + max bi 1, j 1 ci 1, j 1,x1,y1,xi-1,yj-1,xi,yj,36,Multi-recurrence (cont.),bi, j 會先在 X 這邊加入 k 個連續空白，再來只有兩種選擇 (因為 X 不能再加空白): 將 xi 和 yj-k 對齊 ai, j k 在 Y 加入空白 ci, j k bi, j = g(k) + max ai, j k, for 1 k j ci, j
24、 k, for 1 k j,x1,y1,xi,yj-k,yj-k+1yj,37,Multi-recurrence (cont.),ci, j 會先在 Y 這邊加入 k 個連續空白，再來只有兩種選擇 (因為 Y 不能再加空白): 將 xi-k 和 yj 對齊 ai k, j 在 X 加入空白 bi k, j ci, j = g(k) + max ai k, j, for 1 k i bi k, j, for 1 k i,x1,y1,xi-k,yj,xi-k+1.xi+k,38,Multi-recurrence (cont.),Boundary condition: a0, 0 = 0, a*,
25、0 = a0, * = - b0, j = g(j), ci, 0 = g(i) 最後答案 = maxam, n, bm, n, cm, n 需要 O(n2m + nm2) 的時間 這裡是通式，但針對不同的 g() 還可以更快,39,例題講解: H.91.6 (http:/www.cs.tku.edu.tw/info_race2002/codeq.htm),現有 n 位老師 (n 6) 與 m 位同學 (m 12，且 m 是 n 的整數倍)，每位同學需要選專題老師，每位老師收一樣多的同學 現在每個同學以選填志願的方式將老師排序，請找出所有排法中平均志願最佳(總和志願最小) 的組合,40,解題想
26、法,要把 n 個學生分配到 m 個老師所提供的 n 個固定位置上，用最直覺的暴力法去做就是 n! (先不考慮同一個老師提供的位置沒有順序之分的問題) 但是在 n! 的總計算量當中，實際上有許多部份是被一再重複計算的，可以用 DP 的方式記下來,41,解題想法 (cont.),假設有 6 個學生 (將學生依序編號為 1 到 6)，要分配到 6 個位置上 考慮把 2、4、6 三名學生分配到後三個位置的情形，三個學生分配到三個位置有 3! 種可能 每一種可能下，都一樣要把 1、3、5 分到前三個，而總合最低的分法都相同，和 2、4、6 的順序沒有關係,2, 4, 6,3,1,5,學生,位置,42,D
27、efinition,令 (a1, ., an) 代表每個學生分配位置的狀態，若第 i 個學生已有位置則 ai 為 1，反之則為 0 令 num(a1, ., an) = i ai 代表已經被分配位置的學生人數，就是有多少個 ai 為 1 令 p(a1, ., an) 代表已經把前 num(a1, ., an) 個位置分配給其中 ai = 1 的學生們的子問題 如 p(1, 0, 1, 0, 1, 0) 代表第 1, 3, 5 個學生被分配到前三個位置的子問題,43,Optimal substructure,要求 p(a1, ., an) 這個子問題中總合分數最低的分法 任選一名學生放在第 nu
28、m(a1, ., an) 個位置，而其他學生放到前面的位置就是一組可能的分法 每一組可能的分法都需要是子問題的最佳解 從所有可能的分法中挑出分數最低的組合,44,Example,1, 0, 1, 0, 1, 0,0, 0, 1, 0, 1, 0,1, 0, 0, 0, 1, 0,1, 0, 1, 0, 0, 0,0, 0, 1, 0, 0, 0,1, 0, 0, 0, 0, 0,1, 0, 0, 0, 0, 0,0, 0, 0, 0, 1, 0,0, 0, 0, 0, 1, 0,0, 0, 1, 0, 0, 0,min,min,min,min,45,Recurrence,令 s(a1, .,
29、an) 為 p(a1, ., an) 最佳解的分數 s(a1, ., an) = min s(a1, ., ai = 0, ., an) + w(ai, num(a1, ., an) 只要知道 num(a1, ., an) 就可以算出第 i 個學生要放在哪個位置，就可以算出 cost w() Boundary condition: s(0, 0, , 0) = 0,ai = 1,46,Analysis,這會是一個 n 維的 DP，所以寫作上的注意事項請參照不定維度 DP 的寫法 有 n 維，但是每一維都只有 0 和 1，所以總共要計算 2n 格，需要 O(2n) 的時間 經由 DP 記表，從 n! 降到 2n,47,歷年題目,練習題 A.10534 Wavio Sequence http:/acm.uva.es/p/v105/10534.html A.10604 Chemical Reaction http:/acm.uva.es/p/v106/10604.html H.91.6 專題選課 http:/www.cs.tku.edu.tw/info_race2002/codeq.htm 挑戰題 A.702 The Vindictive Coach http:/acm.uva.es/p/v7/702.html 歷年題目 請參閱 Dynamic programming 2 的講義,