深謀遠慮，大功告成!! 中央大學資工系 江振瑞 教授 動態規劃演算法 深謀遠慮，大功告成!! 中央大學資工系 江振瑞 教授

1. 動態規劃演算法基本概念

動態規劃解題策略(1) 動態規劃演算法(dynamic programming algorithm)使用動態規劃策略(dynamic programming strategy)解決問題。它將原問題分解成一系列子問題(subproblems)，並依序解決子問題來解決原問題。為避免一再地解重複的子問 題，一旦解出子問題的解答(solution)，即會將其存在表格(或陣列)中。當需要用到某一子問題的解答時，即直接從表格中取出其解答以節省計算時間，是一個「系統化」的、「節省不必要計算」的、「以空間換取時間」的演算法。 一個動態規劃演算法一般先解出最簡單的子問題，並以一定的程序持續運行直至求出原問題解答為止。

動態規劃解題策略(2) 動態規劃演算法將一個問題P分解為一系列的子問題P1 , P2, …, Pn-1, Pn，並作出一系列的決策D1, D2, …, Dn-1, Dn來解決問題。 若先完成i個到第j個(1ijn)決策(也就是Di, …, Dj)，則D1, …, Dj-1與Dj+1, …,Dn必須基於Di, …, Dj所產生的結果才可以得到問題的最佳解。這表示決策間必定有遞迴關係。

動態規劃與貪婪演算法之比較 比較: 二者都是透過一系列的決策以解決問題，但是有以下的不同點: 在貪婪演算法中，任何決策都是獨立(independent)的，都只要考慮區域最佳解(locally optimal)。這些區域最佳解最後會加成為全域最佳解(globally optimal solution)。 在動態規劃演算法中，決策是相依的(dependent)。每個決策必須考慮其他決策所產生的結果才能求得全域最佳解(globally optimal solution)。

使用動態規劃解題策略的演算法 最長共同子序列演算法 多階圖最小成本路徑演算法 Bellman-Ford最短路徑演算法 Floyd-Warshall最短路徑演算法 矩陣鏈乘積演算法

2. 最長共同子序列演算法

最長共同子序列 以下我們說明最長共同子序列(Longest common subsequence, LCS or LCSS)相關背景知識 令X為一個由若干符號依序排列組成的序列(sequence)，則X的子序列(subsequence)為從X刪除0個或多個符號(不必要為連續性的)的序列 例: 令X = b a c a d，則ad, ac, bac, acad, bacad, bcd等與空序列都是A的子序列 例: 序列X = b a c a d 與 Y = a c c b a d c b 的共同子序列(common subsequence)有: ad, ac, bac, acad等 例: 序列X與Y的最長共同子序列(longest common subsequence)為: a c a d

最長共同子序列應用: DNA序列比對 DNA = {A|C|G|T}* (A: 腺嘌呤; C: 胞嘧啶; G: 鳥嘌呤; T: 胸腺嘧啶) S1=ACCGGTCGAGTGCGGCCGAAGCCGGCCGAA S2=GTCGTTCGGAATGCCGTTGCTGTAAA Q: S1與S2是否為相似的DNA序列? A: 這問題可以由找出S1與S2的最長共同子序列來解決。 腺嘌呤（A） 胸腺嘧啶（T） 胞嘧啶（C） 鳥嘌呤（G）

最長共同子序列應用: 化身路徑群組 化身路徑群組(Avatar Path Clustering): 由於相似的個性，興趣或習慣，網路虛擬環境(Networked Virtual Environment, NVE)或巨量多人線上遊戲(Massively Multiplayer Online Game, MMOG)的用戶或化身(avatar)可能具有相似的行為模式，導致在虛擬世界中有著類似的化身路徑。 我們希望將類似的化身歸類為一個群組，並為他們找到代表性路徑(representative path, RP)。 參考論文: Jehn-Ruey Jiang, Ching-Chuan Huang, and Chung-Hsien Tsai, “Avatar Path Clustering in Networked Virtual Environments," in Proc. of the 4th International Workshop on Peer-to-Peer Networked Virtual Environments (P2PNVE 2010), 2010. 下圖來源: Huiguang Liang, Ransi Nilaksha Silva, Wei Tsang Ooi, Mehul Motani, “Avatar mobility in user-created networked virtual worlds: measurements, analysis, and implications,” Multimedia Tools and Applications, v.45 n.1-3, p.163-190, October 2009. In order to verify the proposed avatar path clustering method in NVE, the study refers to the movement data of avatars gathered by [6] from Second Life. Second Life has a number of avatar motion paths on different regions. Each Region is the 256x256(unit2) of the virtual world, the AOI range of avatar is 16(unit). Each record includes avatar location data in the region within 24 hours(as seen in Figure 5). Data format for each location data includes date, time, user ID, and avatar location. Interval for data collection is approximately 10 seconds. Thus, the motion path of avatars is composed of a data series. The gathered avatar location data [6] is from the free will of players in the virtual world. This enabled it to correspond best with the actual avatar movements in NVE.

最長共同子序列應用: 化身路徑群組(續) 在第二人生(Second Life, SL)贈品島(Freebies Island)的兩條路徑有多相似？

最長共同子序列應用: 化身路徑群組(續) 將化身路徑轉為序列: 將虛擬世界切割為方格(grid cell)，並針對化身路徑每隔固定時間取樣，找出其所在方格編號形成序列。 In LCSS-DC, the entire virtual world is divided into numbered square cells whose length is of the AOI diameter. According to the cell numbers that the sample points of a path resides in, the path is represented by a sequence of cell numbers. Note that consecutive identical cell numbers in the sequence will be merged to be one number. For example, in Figure 3(a), path A is represented as <60, 61, 62, 63, 55, 47, 39, 31, 32>, and path B, <60, 61, 62, 54, 62, 63, 64>. C60.C61.C62.C63.C55.C47.C39.C31.C32 首先我們將整個虛擬環境切割成數塊長寬(假設每個使用者擁有相同且固定的AOI半徑下，長度設定成AOI直徑，使得使用者的視野有重疊)相等的格子，每一個格子都有它的代號，而每一條路徑從開始到結束依序跨越數個不同的格子，我們在路徑跨越到不同的格子的時候為路徑序列增加一個格子代號，因此每一條路徑都可以以格子的代號當作序列的元素來表示 SeqA:C60.C61.C62.C63.C55.C47.C39.C31.C32

最長共同子序列應用: 化身路徑群組(續) 找出兩條路徑對應的最長共同子序列以衡量其相似程度。 SeqA :C60.C61.C62.C63.C55.C47.C39.C31.C32 SeqB :C60.C61.C62.C54.C62.C63.C64 LCSSAB :C60.C61.C62. C63 找出兩條路徑對應的最長共同子序列以衡量其相似程度。 After using LCSS algorithm to calculate the length of the paths, clustering is performed. LCSS-DC uses a pair of similar path thresholds THa and THb, instead of the similar path radius used in ADOCP-DC, as parameters of clustering. Path Pi takes path Pj as its similar path if Eqs. (3) and (4) are satisfied. In Eqs. (3) and (4), Seqi and Seqj are the cell sequences of Pi and Pj, respectively, and LCSSij is the longest common subsequence of Seqi and Seqj, and SSeqji is the sub-sequence of path Pj containing the whole LCSSij. Like ADOCP-DC, LCSS-DC also adopts the density-based clustering mechanism for clustering paths. When a path has many enough similar paths, it is regarded as a core path and become a candidate of representative paths. Note that the similarity relationship between two paths is asymmetric. To take paths in Figure 3(a) as examples, path B may take path A as a similar path, but not vise versa. The asymmetry is to avoid the case that dissimilar paths appear in the cluster. For example, if path A in Figure 3(b) considers both paths B and C to be similar, then path A is likely to be the representative path of the cluster covering paths A, B and C. It is obvious that such a cluster contains two very dissimilar paths, B and C.

最長共同子序列問題 以下我們定義最長共同子序列(Longest Common Subsequence, LCS)問題： 給定兩個序列X = <x1,x2,...,xm>, Y = <y1,y2,...,yn>，找出X和Y的最長共同子序列長度

最長共同子序列問題 暴力法時間複雜度 產生序列X(或Y)的所有子序列，然後檢查每個子序列是否也是序列Y(或X)的子序列，然後儲存下最長的子序列並輸出。複雜度為: n * 2m = O(2m) 或 m * 2n = O(2n ) Q1: 如何產生一個序列的所有子序列? Q2: 如何檢查一個序列是否為另一個序列的子序列?

最長共同子序列問題 子問題的遞迴關係 ì ï c [ i , j ] = í c [ i - 1 , j - 1 ] + 1 x =y ï 我們定義Xi = < x1,x2,...,xi >及Yj = <y1,y2,...,yj>。令c [i, j]是Xi 和Yj 的LCS的長度，則我們有以下遞迴關係: ì if i= or j= ï c [ i , j ] = í c [ i - 1 , j - 1 ] + 1 if i,j> and x =y i j ï max{ c [ i , j - 1 ], c [ i - 1 , j ]} if i,j> and x ¹ y î i j

最長共同子序列演算法 Algorithm 最長共同子序列演算法 Input: 兩個序列X = <x1,x2,...,xm>, Y = <y1,y2,...,yn> Input: X和Y的最長共同子序列長度 1 m  length[X] 2 n  length[Y] 3 for i  1 to m do 4 c[i, 0]  0 5 for j  1 to n do 6 c[0, j]  0

7 for i  1 to m do 8 for j  1 to n do 9 if xi = yj then 10 c[i, j]  c[i-1, j-1]+1 11 b[i, j]  0 “” //for both i-1 and j-1 12 else if c[i–1, j]  c[i, j-1] then 13 c[i, j]  c[i-1, j] 14 b[i, j]  “” //for i-1 15 else c[i, j]  c[i, j-1] 16 b[i, j]  “” //for j-1 only 17 return c and b

最長共同子序列演算法 執行範例 X=ABCBDAB Y=BDCABA

最長共同子序列演算法 時間複雜度 行7的外層for迴圈一共有m次迭代 行8的內層for迴圈一共有n次迭代 行9-16的if敘述需要常數時間 因此總時間複雜度為O(mn) ，而非暴力法的 O(2m)或 O(2n)

最長共同子序列演算法 如何找出最長共同子序列 PRINT_LCS(b, X, i, j ) 1 if i = 0 or j = 0 then 2 return 3 if b[i, j] = “” then 4 PRINT_LCS(b, X, i-1, j-1) 5 print xi 6 else if b[i, j] = “” then 7 PRINT_LCS(b, X, i-1, j) 8 else PRINT_LCS(b, X, i, j-1) 時間複雜度: O(m+n) 藉由呼叫PRINT_LCS(b, X, length[X], length[Y])函數來印出 LCS

3. 多階圖最小成本路徑演算法

多階圖最小成本路徑問題 (multi-stage graph minimum-cost path problem) 多階圖G=(V,E) 是有向圖(directed graph)，其節點被分割成 k2 個兩兩互斥集(disjoint sets) Pi,1 i  k。 此外，若<x,y>是E的邊，則xPi 且 yPi+i ,1 i <k，每個邊都有一個加權(weight)wi,i+1 (或稱為成本或距離)。 其中集合 P1 和 Pk 都僅包含一節點(node or vertex)。 多階圖問題是要找出從 P1 中的源點(source)s 到Pk中的標點(target) t 的最小成本路徑(minimum-cost path)。 每一個集合Pi ,1 i  k被定義為圖中的第i階(stage)。

貪婪演算法無法解決 多階圖最小成本路徑問題 例如： 貪婪演算法無法解決此問題: S A D T 1+4+18 = 23. 最短路徑為: S C F T 5+2+2 = 9. 就像分期買商品一樣，都分三期付款，最終都可以得到商品的產權。有的付款方式第一期要繳1萬，有的要繳2萬，有的要繳5萬。但是依照不同的第一期繳法，則在第二期甚或第三期都有不同的繳款選擇，而造成繳款總額的不同。 就像買房子一樣，分三期付款，最終都可以得到房子的產權。有的付款方式第一期要繳1萬，有的要繳2萬，有的要繳5萬。但是依照不同的第一期繳法，則在第二期甚或第三期都有不同的繳款選擇，而造成總繳款數的不同。

動態規劃遞迴關係 (1) d(S, T) = min{1+d(A, T), 2+d(B, T), 5+d(C, T)}

動態規劃遞迴關係 (2) d(A, T) = min{4+d(D, T), 11+d(E, T)}

動態規劃遞迴關係 (3) (下式省略邊界條件值d(T, T)=0) d(B, T) = min{9+d(D, T), 5+d(E, T), 16+d(F, T)} = min{9+18, 5+13, 16+2} = 18. d(C, T) = min{ 2+d(F, T) } = 2+2 = 4. d(S, T) = min{1+d(A, T), 2+d(B, T), 5+d(C, T)} = min{1+22, 2+18, 5+4} = 9.

解決多階圖最小成本路徑問題的動態規劃演算法 Algorithm 多階圖最小成本路徑演算法 Input:具n個頂點(vertices)的k階多階圖G(V, E), 其中V= i=1..k Pi , PiPj= for ij, P1={s},Pk={t}, <x,y>E (xPi  yPi+i), <x,y>的權重為w[x,y] Output: path[1..k], d[s]，其中path[1..k]紀錄第1階(節點1)到第k階(節點n)的最 小成本路徑，d[s]紀錄最小成本路徑總成本 d[t]=0; d[x]= for xt; //陣列d[x]儲存節點x到標點t的最小距離(distance) for ik-1 to 1 do //由第k-1階到第1階 for every node x in Pi do for every edge (x, y)E do //實作d[x]=min(x,y)E {w[x,y]+d[y]} if (d[x]>w[x,y]+d[y]) do d[x]=w[x,y]+d[y] next[x]=y //代表在最短路徑中節點x的下節點為y path[1]=s;path[k]=t; //path[j]表示路徑中第j階的節點 for j2 to k-1 do path[j]next[path[j-1]]; return path[s],d[s]

4. Bellman-Ford 最短路徑演算法

Bellman-Ford最短路徑演算法介紹 與Dijkstra演算法相同，Bellman-Ford演算 法也是屬於求取單一源節點至全部終節點 的一至全最短路徑演算法。 但是與Dijkstra演算法不同的是，Bellman- Ford演算法可以檢查圖是否有負加權循環 (cycle)，因此在具有負加權(negative weight)邊的圖也可以正確的執行。

Bellman-Ford最短路徑演算法介紹(續) Bellman-Ford最短路徑演算法採用動態規劃策略解 決問題。一開始在第1次迭代先求出所有屬於1-邊 路徑(1-edge path)的最短路徑，並將其最短路徑距 離儲存在陣列中；然後基於這個儲存結果在第2次 迭代針對每個邊，由始點(starting node)往外調整到 止點(ending node)的最短路徑距離，可以得出所有 屬於2-邊路徑(2-edge path)的最短路徑；…。依此 類推則在第n-1次迭代可以求出所有屬於(n-1)-邊路 徑((n-1)-edge path)的最短路徑。因為具n個節點的 圖最長的路徑具有n-1個邊，因此第n-1次迭代求出 的路徑已經是最終的正確結果了。

Bellman-Ford最短路徑演算法 Algorithm Bellman-Ford最短路徑演算法 Input: 給定一個加權有向圖(weighted digraph)G=(V, E)，及一個來源(source)節點s。G各邊的加權值以w[x][y]表示，其中x 及y為邊的二個節點。 Output: 對每一個頂點u而言，傳回一個由s到u的最短路徑距離(累積邊加權)d[u]。 d[s]←0; d[u]←∞ for each u≠s for i←1 to |V|-1 do for 每一個G的邊(u, x)　do if d[x] > d[u] + w[u][x] then d[x]← d[x] + w[u][x] for 每一個G的邊(u, x) do //檢查有無負循環(negative-weight cycle) if d[x] > d[u] + w[u][x] then return false //代表有負循環，無法產生正確結果 return d

Bellman-Ford最短路徑演算法複雜度 假設G一共有n個節點，m個邊(也就是|V|=n, |E|=m) 行2-5的外層for迴圈一共有n-1次迭代 行3-5的內層for迴圈一共有m次迭代 行4-5為內層if指令，針對每個邊(u, x)依據目前的d[u]值調整d[x] 行6-7的for迴圈在求出(n-1)邊路徑之後再針對每個邊(u, x)依據目前的d[u]值調整d[x]，若有任何調整產生則表示有一個n邊路徑(也就是循環) 因此總時間複雜度為行2-5的外層for迴圈n-1次迭代次數與 行3-5的內層for迴圈m次迭代相乘得O(n  m)= O(|V|  |E|)

Bellman-Ford最短路徑演算法 執行範例 (a)是初始狀態，(b)是first iteration之後的狀況，(c)跟(d)類推。 塗成藍色的虛線邊是對應的Predecessor graph所有的邊， 點內的數字代表d[v]，是現存最短路徑， 綠色的點代表已經將該點的所有邊Relax過了。

5. Floyd-Warshall 最短路徑演算法

Floyd-Warshall最短路徑演算法介紹 與Dijkstra演算法與Bellman-Ford演算法不同的是， Floyd-Warshall演算法可以求出全部節點配對的最 短路徑，是一個全配對最短路徑(all-pair shortest path)演算法。 Floyd-Warshall演算法可以處理有負邊的圖，但是 不能用以檢查有負迴圈的圖。

Floyd-Warshall最短路徑演算法介紹(續) Floyd-Warshall演算法採用動態規劃策略解決問題，利用一個n×n(n為節點總數)的二維陣列d來記錄每一節點配對間的最短路徑成本或距離(distance) 。 在啟始(initial)狀況時， d[i][j]=w[i][j]，for each i and j。 (w[i][j]=0，for i=j; w[i][j]=, for (i, j)E; w[i][j]=the weight of (i, j) for (i, j) E) Floyd-Warshall演算法執行時會不斷的更新陣列d。在第k次更新陣列d時，表示d中所紀錄的最短路徑是經由編號小於或等於k的節點當作中間節點所造成的。因此，當第n次更新陣列d時，則表示d中所紀錄的最短路徑是可以經由所有節點當作中間節點所造成的，這也就是演算法所需要的結果。

Floyd-Warshall最短路徑演算法 Algorithm Floyd-Warshall最短路徑演算法 Input：G為一個加權圖有向(weighted digraph)， G中各邊的加權值以w[x][y]表示，x 及y為邊的二個頂點。 Output：G中的每一個節點配對的最短路徑距離d[x][y]，及對應的路徑前節點p[x][y]，其中x及y為邊的二個節點 d[i][j]w[i][j], for each i and j P[i][j]i, for each i and j for(k←1 to n) do //假設節點的編號由1至n for(i←1 to n) do for(j←1 to n) do if (d[i][j]>d[i][k]+d[k][j]) d[i][j]←d[i][k]+d[k][j] p[i][j]←p[k][j] return d, p

Floyd-Warshall演算法討論 可以使用一個前節點陣列(predecessor matrix)p紀錄每個節點在最短路徑上的前節點。初始化p[i,j]時，若i=j或(i,j)∉E則初始為NIL()，否則初始為i。 等執行完演算法後，則可藉由前節點陣列來建立出由任意節點到其他任意節點的最短路徑。

Floyd-Warshall最短路徑演算法範例: 陣列初始化   s a b c d 6  3 2 4 1 5 d[i][j]   s a b c d  p[i][j] G(V, E)

Floyd-Warshall最短路徑演算法複雜度 假設G一共有n個節點(也就是|V|=n) 行3的外層for迴圈一共有n次迭代 行4的中層for迴圈一共有n次迭代 行5的內層for迴圈一共有n次迭代 行6-8的if敘述的執行為常數時間 因此總時間複雜度為O(n3)=O(|V|3)

6. 矩陣鏈乘積演算法

矩陣鏈乘積 (matrix-chain product) Q: 如何以最少的純量(scalar)乘法，算出A1…An的矩陣鏈乘積? A: 加上括號指定計算矩陣乘積最佳順序 舉例:

二個矩陣相乘的演算法 MATRIX MULTIPLY(A,B) 1 if columns[A] rows[B] 2 then error “不相容的矩陣大小” 3 else for to rows[A] 4 for to columns[B] 5 6 for to columns[A] 7 8 return C

二個矩陣相乘時間複雜度: 假設 A 是一個 的矩陣，B 是一個 的矩陣， 那個 A x B 的時間複雜度為 。

矩陣相乘執行順序非常關鍵 假設 是個 的矩陣, 是一個 的矩陣, 是一個 的矩陣。 那麼算出 需要 次的純量相乘。 然而算出 卻需要

矩陣鏈乘積問題 (matrix-chain product problem) 給定一長度為n的矩陣鏈 ，對於i=1,2,…,n而言，矩陣Ai 的維度為 pi-1pi。找出一種方式對 進行完全括號(fully parenthesized)以最少的純量乘法求出矩陣鏈乘積。 若一個矩陣鏈乘積為完全括號，則其包含單一矩陣或為兩個完全括號矩陣鏈乘積的相乘。 Given a chain of n matrices, where for i=0,1,…,n, matrix Ai has dimension pi-1pi, fully parenthesize the product in a way that minimizes the number of scalar multiplications. A product of matrices is fully parenthesized if it is either a single matrix, or a product of two fully parenthesized matrix product, surrounded by parentheses.

矩陣鏈乘積問題 窮舉所有不同的括號方式: 不同括號方式總數相當於將矩陣鏈在第k個矩陣之後與第k+1個矩陣之前，使用括號分為二組後再計算其結果，而1kn-1。我們可得: 實際上，P(n)為卡塔蘭數(Catalan number)=Cn-1 =O(2n)

卡塔蘭數(Catalan number) 卡塔蘭數是以比利時的數學家歐仁查理卡塔蘭(Eugène Charles Catalan, 1814–1894)命名。 卡塔蘭數的一般項公式為 

矩陣鏈乘積演算法解題思維 步驟1:找出子問題切割方式 Step 1: The structure of an optimal parenthesization

矩陣鏈乘積演算法解題思維步驟 2: 找出子問題遞迴關係 定義 m[i, j]= 計算 所需的最小相乘數。 目標為求得 m[1, n]

矩陣鏈乘積演算法解題思維步驟 3: 以表格儲存計算過的資訊 與其一再地遇到相同問題而重複遞迴求解，取而代之地我們利用一表格化的(tabular)、由下而上(bottom-up)的方式來計算最低成本。 過程利用一輔助表格m[1..n, 1..n] 來紀錄最小成本m[i, j] ，並利用另一個輔助表格s[1..n, 1..n]來記錄哪一個指標 k 造就了m[i, j]的最小成本。 Step 3: Computing the optimal costs Instead of computing the solution to the recurrence recursively, we compute the optimal cost by using a tabular, bottom-up approach. The procedure uses an auxiliary table m[1..n, 1..n] for storing the m[i, j] costs and an auxiliary table s[1..n, 1..n] that records which index of k achieved the optimal cost in computing m[i, j].

矩陣鏈乘積演算法MATRIX_CHAIN_ORDER MATRIX_CHAIN_ORDER(p) 1 n  length[p] –1 2 for i  1 to n 3 do m[i, i]  0 4 for l  2 to n 5 do for i  1 to n – l + 1 6 do j  i + l – 1 7 m[i, j]   8 for k  i to j – 1 9 do q  m[i, k] + m[k+1, j]+ pi-1pkpj 10 if q < m[i, j] 11 then m[i, j]  q 12 s[i, j]  k 13 return m and s 時間複雜度:

例子:

在n=6時， MATRIX-CHAIN-ORDER所計算出的 m 與 s 表格

m[2,5]= min{ m[2,2]+m[3,5]+p1p2p5=0+2500+351520=13000, m[2,3]+m[4,5]+p1p3p5=2625+1000+35520=7125, m[2,4]+m[5,5]+p1p4p5=4375+0+351020=11374 } =7125

印出最佳括號方式 PRINT_OPTIMAL_PARENS(s, i, j) 1 if i=j 2 then print “A”i 3 else print “(“ 4 PRINT_OPTIMAL_PARENS(s, i, s[i,j]) 5 PRINT_OPTIMAL_PARENS(s, s[i,j]+1, j) 6 print “)” 例:

The End