《主题dynamicprogrammingiii》由会员分享，可在线阅读，更多相关《主题dynamicprogrammingiii（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+) /省略檢查 aj 數量的部分 aj -; achemij +; call h(a); / 計算子問題解並求最小值 achemij -; aj +; ai +; ,25,Multi-recurrence DP,Seque
