主题DynamicProgrammingII.ppt

1,主題: Dynamic Programming (II),經典問題 Longest Common Subsequence Longest Increasing Subsequence Matrix-chain Multiplication Optimal Polygon Triangulation 例題講解: H.89.4 歷年題目,2,Longest Common Subsequence,Subsequence: 對字串 T 而言，T 的 subsequence 為從 T 中消掉某些字元可以得到的新字串 對數列也有類似的定義,3,Longest Common Subsequence,對兩個字串 X = x1x2xn 和 Y = y1y2ym求兩字串中相同且最長的 subsequence,X ,Y , ba, bca, bcba, bdab, ,common subsequence,LCS ,bcba, bdab, ,4,LCS: Optimal Substructure,若 xn = ym，則在 LCS 中有包含這兩個的解，至少跟沒有同時包含這兩個的任何解一樣好,5,LCS: Optimal Substructure (cont.),所以若 xn = ym，就取這兩個為 LCS 的一部分，然後求 X1n-1 和 Y1m-1 的 LCS 來和這兩個合併 若 xn ym，則 LCS 就會是下面兩種其中之一的解 X1n 和 Y1m-1 的 LCS X1n-1 和 Y1m 的 LCS,6,LCS: Recurrence,定義 Li, j 為 X1i 和 Y1j 之間的 LCS 長度,L0, j = 0 Li, 0 = 0,Boundary condition,7,LCS: Build Table,Li, j 需要的表格, row-major column-major 對角線順序,Time = O(nm),8,LCS: 節省空間,雖然 LCS 是二維 mn 的 recurrence，但在 row-major (column-major) 順序下，每一個 row (column) 都只需要看前一個 row (column) 就可以算出 LCS 的長度，更前面的部分就用不到 若不需要 backtracking，則只需要兩個 row (column) 就足夠算出長度的最佳解,9,Longest Increasing Subsequence,給一串數列 a1, a2, , an，從數列中找出最長且數字依序單調遞增的subsequence,A ,10,LIS: 直覺解法,依照定義，LIS 是原數列的 subsequence 若將 a1, a2, , an 照大小重排會變成一個遞增數列 B = b1, b2, , bn，由於 LIS 也是遞增數列，LIS 為 B 的 subsequence LIS 為原數列 A 和新數列 B (對 A 做 sort 所得) 兩者的 LCS,11,LIS: Example,Time complexity = O(n2),問題: 若題目要求的是最長的嚴格遞增數列呢? Hint: 對 B 做改變,12,Matrix Multiplication,一個大小為 a b 的矩陣與大小為 b c 的矩陣相乘，需要做 (a c) b 次乘法和加法，然後得到一個 a c 的矩陣,13,Matrix-chain Multiplication,給定 n 個需要連續相乘且大小不等的矩陣 A1 A2 An，其中第 i 個矩陣 Ai 的大小為 pi-1 pi，為了使運算量最少，請求出最好的運算順序(用括號表示) Ex: (p0, p1, p2, p3) = (50, 5, 100, 10),(A1A2)A3) ,(A1(A2A3) ,505100,+ 5010010 = 75000,510010,+ 50510 = 7500,14,MCM: Optimal Substructure,假設要先把 A1 Ai 和 Ai+1 An 兩個部分做完，然後這兩個部分再來對乘，則在此情形下最好的解必定是 先做 A1 Ai 的 MCM， 再做 Ai+1 An 的 MCM， 最後再把兩個完成的矩陣相乘 A1A2A3A4A5A6A7,挑最好的切法,15,MCM: Recurrence,令 mi, j 為做 Ai Aj 的 MCM 所需的最少運算量 mi, j = min mi, k + mk+1, j + pi-1pkpj mi, i = 0 for all i,i k j,Time complexity = O(n3),16,適合的填表順序 對角線 由下而上做 row-major 由左而右做逆向的 column-major MCM 沒辦法只用一維陣列 O(n2),MCM: Build Table,17,MCM: Backtracking,在計算 mi, j 時所取的 k 表示從 Ai 到 Aj 之間最好的計算順序是先算 Ai 到 Ak，再算 Ak+1 到 Aj，最後兩邊相乘 (Ai Ak)(Ak+1 Aj) 用一個額外的陣列 ci, j 來幫每個 mi, j 記住其最好的 k,18,Polygon Triangulation,給定一個 n 邊的凸多邊形，只要加入 n 3 條互不相交的對角線，就可以把此多邊形切成 n 2 個三角形,19,Triangulation 的 cost,按照不同題目的定義，可以給每一個 abc 一個 cost w(abc ) 每種 triangulation 的 cost，是由所有三角形之 cost 計算而得，如: w(abc ) = 邊長總合， triangulation 的 cost 是所有三角形之 cost 加總 w(abc ) = 面積， triangulation 的 cost 是最大三角形的面積,20,Optimal Polygon Triangulation,以順時針方向給予一個凸多邊形的 n 個頂點 v0, v1, , vn-1，並指定一種 cost function w，求 cost 最小的 triangulation 因為 triangulation 中對角線互不相交，所以任一個三角形的頂點必為此多邊形的頂點 vi, vj, vk，令此三角形為 vivjvk,21,OPT: Optimal Substructure,v1,vk,vn-2,任一條 edge 必定也是某個三角形的 edge,w(v0vkvn-1),vn-1,v0,22,OPT: Recurrence,令 Pi, j 為從 vi-1 開始順時鐘繞到 vj 再繞回 vi-1 的凸多邊形，而 ti, j 就是對 Pi, j 進行 optimal polygon triangulation 所得最佳解的 cost 總合 ti, j = min ti, k + tk+1, j + w(vi-1vkvj) ti, i = 0 for 1 i n 1,i k j,23,OPT: Analysis,Time: O(n3) Space: O(n2) 要 backtracking 只需要記住每個 ti, j 所使用的 k 即可,24,例題講解: H.89.4 (.tw/info_race89/doc/final_program.doc),現在有 n 個貨櫃 (n 10)，載重量分別為 a1, a2, , an公斤 (50 ai 1000)，要用來運送主機以及螢幕 主機一台 7 公斤，螢幕一台 10 公斤，一套系統需要一台主機及兩台螢幕 問每個貨櫃應該如何配置主機及螢幕的數量，使這 n 個貨櫃可以運送最多套的系統,25,Definition,令 f(i, j) 為貨櫃 i 在裝了 j 台主機之後，剩下的負重量足夠放置的螢幕數量 f(i, j) = (ai 7j) / 10, for ai 7j , otherwise,26,Recurrence (cont.),令 ci, j 為只使用前 i 個貨櫃，並且在其中裝入 j 台主機後，最多可以再放置多少螢幕的數量 ci, j = max ci 1, j k + f(i, k) c1, j = f(1, j),0 k j,27,輸出答案,從最後一個貨櫃的解中，找出可以放置最多主機，且螢幕容量在主機兩倍以上的那一個位置 最大系統套數 = max j | 2j cn, j 題目需要 backtracking，所以每個 ci, j 都要記住使這格可以取得最大值的 k,28,Analysis,二維的 recurrence 中第一個維度是 n，而第二個維度的最大值是用 n 個貨櫃可以塞下去的主機總數，也就是所有貨櫃的負重量總合除以 7 令 S = (1 i n ai) / 7 1500 Time: O(nS2) Space: O(nS),29,練習題,練習題 A.526 String Distance and Transform Process http:/acm.uva.es/p/v5/526.html A.348 Optimal Array Multiplication Sequence http:/acm.uva.es/p/v3/348.html A.10003 Cutting Sticks http:/acm.uva.es/p/v100/10003.html H.88.5 .tw/info_race88/Q.pdf H.89.4 貨櫃配置問題 .tw/info_race89/doc/final_program.doc 挑戰題 A.10379 Pit Stop Strategy http:/acm.uva.es/p/v103/10379.html A.757 Gone Fishing http:/acm.uva.es/p/v7/757.html,30,歷年題目,其他歷年題目 A.111, A.103, A.116, A.136, A.164, A.231, A.242, A.357, A.323, A.443, A.481, A.497, A.417, A.452, A.531, A.585, A.580, A.590, A.640, A.674, A.682, A.702, A.707, A.751, A.861, A.10000, A.10036, A.10051, A.10066, A.10007, A.10069, A.10076, A.10100, A.10120, A.10130, A.10131, A.10154, A.10164, A.10192, A.10111, A.10128, A.10157, A.10198, A.10213, A.10223, A.10232, A.10237, A.10238, A.10239, A.10259, A.10261, A.10271, A.10280, A.10337, A.10303, A.10304, A.10312, A.10313, A.1032