主題DynamicProgrammingIII.pptVIP

1,主題: Dynamic Programming (III),DP 的進(jìn)階概念 DP 與 multi-stage graph 的關(guān)係 DAG shortest path problem multi-dimensional DP multi-recurrence DP 例題講解: A.10604, H.91.6 歷年題目,2,DAG shortest path problem,給定一個(gè) directed acyclic graph (DAG)，每條 edge 都有 weight (可能為負(fù)數(shù))，求從起點(diǎn) s 到其他 vertex 的 shortest path,a,s,b,c,d,e,5,3,2,6,7,-1,2,4,-2,1,3,解題方法: DP,首先對給定的 DAG 進(jìn)行 topological sort 使原圖得成為一個(gè) 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 出發(fā)到任一個(gè) vertex v 的可能走法，必然會(huì)經(jīng)過某個(gè) v 的 predecessor v 的 distance 需要其 predecessors 的 distance,a,s,b,c,d,e,2,-2,1,e,5,解題方法 (cont.),要算出 v 的 distance，就要先算出每一個(gè) predecessor u 的 distance，再加上 u 到 v 的 edge weight，然後從每個(gè) 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 的關(guān)係,DP 的特徵在於先把子問題的解算出來，再集合起來算出原問題的解，這種關(guān)係可以被表示成一個(gè) multi-stage graph (不見得只能用格子之間的關(guān)係來敘述) 把每一個(gè)子問題變成一個(gè) vertex 當(dāng)子問題 A 需要用到子問題 B 的解，則 vertex A 有 edge 指向 vertex B (edge 可加上適當(dāng)?shù)?weight) recurrence 描述每一個(gè) vertex 和其 predecessors 的關(guān)係 (top-down) 計(jì)算時(shí)，由小到大一個(gè)一個(gè) stage 完成 (bottom-up computation),8,Critical path problem,給定一個(gè) DAG，每條 edge 都有 weight，在 graph 中找出一條最長的 path 沒有規(guī)定此 path 的起點(diǎn) vertex,a,s,b,c,d,e,5,3,2,6,7,-1,2,4,-2,1,Length = 15,9,Solution,將每一個(gè) vertex 都設(shè)為起點(diǎn) (distance 為 0)，然後每一個(gè) vertex 去計(jì)算可以往前連的多遠(yuǎn)，recurrence 如下: distv = max distu + weight(u, v), 0 Critical path 也是一個(gè) DP problem，其最佳解的長度即為所有 vertex 中，可以往前連到的最遠(yuǎn)距離: maxdist(v) for all v,u 到 v 有 edge,10,Example: LCS,每個(gè) vertex 的計(jì)算方式都是 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 現(xiàn)在可以把每一個(gè)數(shù)字當(dāng)成一個(gè) vertex，若第 i 個(gè)數(shù)字 第 j 個(gè)數(shù)字 (i j)，則 i 到 j 有 edge 且 weight = 1，如此會(huì)直接形成一個(gè) multi-stage graph，其最佳解可經(jīng)由 critical path 得到,3,4,2,6,3,5,4,1,7,12,Recurrence: LIS,lengthi = max lengthk + 1 雖然此 recurrence 一樣是 O(n2) 的時(shí)間，但 max 的部分還可以做的更快 從第一個(gè) vertex (數(shù)字) 開始依序往後計(jì)算 用陣列 last 輔助算出每個(gè) vertex i 的 length(i) 修正陣列 last 的內(nèi)容,ak ai, k i,13,Last 陣列,Lastj: 存放現(xiàn)在已知所有 length = j 的 paths 中，終點(diǎn) vertices 中值最小的數(shù)字,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 中最後那一個(gè),4,14,計(jì)算 length(i),要算 vertex i 的 length，可以用 i 的數(shù)字 ai 在 last 中進(jìn)行 binary search (last 中的數(shù)字一定會(huì)呈現(xiàn)遞增順序) 當(dāng) binary search 使得 lastj ai lastj + 1，則 lengthi = j + 1 由於 ai 會(huì)變成是 length = j + 1 的 paths 中值最小的終點(diǎn)，所以令 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) 化學(xué)藥劑，將任兩種組合在一起，會(huì)產(chǎn)生其中一種藥劑以及一定的熱量 (可能為負(fù)數(shù)),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,特別注意: 此題目的測試資料並不一定對稱，可能會(huì)有 chemij chemji或 heatij heatji,18,例題講解 (cont.),現(xiàn)有 n 份藥劑 (n 10，而一種藥劑可有好幾份)，要組合到剩下 1 份為止，且不限制最後要剩下哪一種，在此條件下，求合成過程中可能產(chǎn)生的最少熱量 若有 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,組合藥劑的範(fàn)例,令 p(a1, a2, a3, , am) 代表第 i 種藥劑剩下 ai 份的子問題，0 ai n (table size 116) 如 1、2、2、3 的問題可用 (1, 2, 1) 代表 1 和 2 組合產(chǎn)生 3 由 p(1, 2, 1) 變 p(0, 1, 2) 1 和 2 各減少一個(gè)，然後產(chǎn)生一個(gè) 3 1 和 3 組合產(chǎn)生 3 由 p(1, 2, 1) 變 p(0, 2, 1) 2 和 2 組合產(chǎn)生 2 由 p(1, 2, 1) 變 p(1, 1, 1) 2 和 3 組合產(chǎn)生 1 由 p(1, 2, 1) 變 p(2, 1, 0) 若表格不對稱，則還有更多可能的變化,20,Optimal substructure,每一種組合產(chǎn)生的子問題最佳解再加上此組合散發(fā)的熱量，從中取出最小值即為原問題的最佳解,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,總數(shù)為 4,總數(shù)為 3,總數(shù)為 2,總數(shù)為 1,multi-stage graph,0,boundary,22,Recurrence,令 h(a1, , an) 為 p(a1, , an) 最佳解的值 每個(gè)問題所使用的子問題隨表格而變化 很難決定填表順序，建議用 top-down 方式 Recurrence 的維度也隨 input 變化 不適用參數(shù)數(shù)量固定的 recursive call 方式,23,不定維度的 recursive call,用一個(gè)陣列 a 存放每一種藥劑剩下的數(shù)量，和 recurrence 的維度 m 一起當(dāng)作 recursive call 的參數(shù) h(int *a, int m) 由於 m 對同一個(gè) test case 而言是固定的，所以可以用 global variable 存放 當(dāng)組合藥劑 i 和藥劑 j 時(shí)，ai 和 aj 都減 1，而 achemij 要加 1 C 語言的陣列是傳址呼叫， 所以原始值會(huì)被修改，所以在 recursive call 一個(gè)子問題得到解後要先還原,24,不定維度的 recursive call (cont.),int h(int *a) / 省略計(jì)算的部分 for (i = 1; i = m; i+) /省略檢查 ai 數(shù)量的部分 ai -; for (j = 1; j = m; j+) /省略檢查 aj 數(shù)量的部分 aj -; achemij +; call h(a); / 計(jì)算子問題解並求最小值 achemij -; aj +; ai +; ,25,Multi-recurrence DP,Sequence alignment: 給定任意的兩個(gè)字串 X = x1x2xn 和 Y = y1y2ym，在兩邊分別加入空白，使兩字串對齊 要變成長度相同的兩個(gè)字串 X 和 Y 在同一個(gè)位置上，不可以同時(shí)有空白,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.),任兩個(gè)字元 (包括空白) 在同一個(gè)位置 i 上對齊，就會(huì)得到一個(gè)相似度的分?jǐn)?shù) score(xi, yi) (由題目定義，正負(fù)都有可能) 一種對齊方式的分?jǐn)?shù)，就是在所有位置上對齊的字元分?jǐn)?shù)總合，最好的對齊方式是分?jǐn)?shù)最高的對齊方式 (代表相似度最大),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 的最佳對齊分?jǐn)?shù),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 全部對到空白的分?jǐn)?shù) s0, j = y1y2yj 全部對到空白的分?jǐn)?shù) 填表總共需要 O(mn) 的時(shí)間,30,With gap penalty,空白不再是個(gè)別計(jì)分，而是有一個(gè)計(jì)分的 function g(len) 計(jì)算每一塊連續(xù)空白區(qū)段 (gap) 的得分，len 是指此區(qū)段的長度 g(len) 有幾種常見的形式: 每一段都只扣一個(gè) constant 的值 每一段都要先扣一個(gè)起始值 wg，然後每一個(gè)空格再加上 ws wg + len ws 每一段都要先扣 wg，然後加上 log (len),31,Example,舉例而言，相等 2 分，不相等扣 2 分，而 gap 起始值扣 wg = 4，每一個(gè)加 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,錯(cuò)誤的 recurrence,令 fi, j 為 x1x2xi 和 y1y2yj 的最佳對齊分?jǐn)?shù) 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 雖然會(huì)把兩個(gè)字串對齊到長度相等，同時(shí)也不會(huì)有空白對空白的情形，但是這個(gè) recurrence 在計(jì)算連續(xù)空白的分?jǐn)?shù)時(shí)並不正確,用連續(xù) k 個(gè)空白和 xi-k+1.xi 對齊,33,Example,假設(shè) f3, 6 的最佳解是由 f3, 3 得到， 而且 f3, 3 的最佳解是由 f3, 1 得到 因?yàn)檫@個(gè) recurrence 不能反應(yīng)現(xiàn)在的狀態(tài)，所以有可能在同一個(gè)字串連續(xù)加入空白區(qū)段,1 3,1 6,f3, 6,1 3,1 3,f3, 3,4 6,3 格空白,1 3,1,f3, 1,2 3,2 格空白,實(shí)際上是連續(xù) 5 格空白，卻被分別計(jì)分,34,Multi-recurrence,根據(jù)現(xiàn)在的狀態(tài)來呼叫不同功能的 recurrence ai, j: 在將 xi 和 yj 對齊的情形下，x1xi 和 y1yj 最好的對齊分?jǐn)?shù) bi, j: 若在 X 加入空白的情形下， x1xi 和 y1yj 最好的對齊分?jǐn)?shù) ci, j: 若在 Y 加入空白的情形下， x1xi 和 y1yj 最好的對齊分?jǐn)?shù),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 會(huì)先在 X 這邊加入 k 個(gè)連續(xù)空白，再來只有兩種選擇 (因?yàn)?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 會(huì)先在 Y 這邊加入 k 個(gè)連續(xù)空白，再來只有兩種選擇 (因?yàn)?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) 的時(shí)間 這裡是通式，但針對不同的 g() 還可以更快,39,例題講解: H.91.6 (.tw/info_race2002/codeq.htm),現(xiàn)有 n 位老師 (n 6) 與 m 位同學(xué) (m 12，且 m 是 n 的整數(shù)倍)，每位同學(xué)需要選專題老師，每位老師收一樣多的同學(xué) 現(xiàn)在每個(gè)同學(xué)以選填志願(yuàn)的方式將老師排序，請找出所有排法中平均志願(yuàn)最佳(總和志願(yuàn)最小) 的組合,40,解題想法,要把 n 個(gè)學(xué)生分配到 m 個(gè)老師所提供的 n 個(gè)固定位置上，用最直覺的暴力法去做就是 n! (先不考慮同一個(gè)老師提供的位置沒有順序之分的問題) 但是在 n! 的總計(jì)算量當(dāng)中，實(shí)際上有許多部份是被一再重複計(jì)算的，可以用 DP 的方式記下來,41,解題想法 (cont.),假設(shè)有 6 個(gè)學(xué)生 (將學(xué)生依序編號(hào)為 1 到 6)，要分配到 6 個(gè)位置上 考慮把 2、4、6 三名學(xué)生分配到後三個(gè)位置的情形，三個(gè)學(xué)生分配到三個(gè)位置有 3! 種可能 每一種可能下，都一樣要把 1、3、5 分到前三個(gè)，而總合最低的分法都相同，和 2、4、6 的順序沒有關(guān)係,2, 4, 6,3,1,5,學(xué)生,位置,42,Definition,令 (a1, ., an) 代表每個(gè)學(xué)生分配位置的狀態(tài)，若第 i 個(gè)學(xué)生已有位置則 ai 為 1，反之則為 0 令 num(a1, ., an) = i ai 代表已經(jīng)被分配位置的學(xué)生人數(shù)，就是有多少個(gè) ai 為 1 令 p(a1, ., an) 代表已經(jīng)把前 num(a1, ., an) 個(gè)位置分配給其中 ai = 1 的學(xué)生們的子問題 如 p(1, 0, 1, 0, 1, 0) 代表第 1, 3, 5 個(gè)學(xué)生被分配到前三個(gè)位置的子問題,43,Optimal substructure,要求 p(a1, ., an) 這個(gè)子問題中總合分?jǐn)?shù)最低的分法 任選一名學(xué)生放在第