主题DynamicProgrammingIII.ppt

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,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 的 distance 需要其 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,-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) 計算時，由小到大一個一個 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), 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，若第 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,13,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 使得 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,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) 化學藥劑，將任兩種組合在一起，會產生其中一種藥劑以及一定的熱量 (可能為負數),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 (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 組合產生 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, 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 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+) /省略檢查 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,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,-,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(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 分，不相等扣 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), 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-recurrence,根據現在的狀態來呼叫不同功能的 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-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 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*, 0 = a0, * = - b0, j = g(j), ci, 0 = g(i) 最後答案 = maxam, n, bm, n, cm, n 需要 O(n2m + nm2) 的時間 這裡是通式，但針對不同的 g() 還可以更快,39,例題講解: H.91.6 (.tw/info_race2002/codeq.htm),現有 n 位老師 (n 6) 與 m 位同學 (m 12，且 m 是 n 的整數倍)，每位同學需要選專題老師，每位老師收一樣多的同學 現在每個同學以選填志願的方式將老師排序，請找出所有排法中平均志願最佳(總和志願最小) 的組合,40,解題想法,要把 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,Definition,令 (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) 這個子問題中總合分數最低的分法 任選一名學生放在第