深謀遠慮以空間換取時間 中央大學資工系 江振瑞 教授

Presentation on theme: "深謀遠慮以空間換取時間 中央大學資工系 江振瑞 教授"— Presentation transcript:

1 深謀遠慮以空間換取時間 中央大學資工系 江振瑞 教授
動態規劃演算法 深謀遠慮以空間換取時間 中央大學資工系 江振瑞 教授 漢·賈誼《過秦論》：“深謀遠慮，行軍用兵之道，非及曩時之士也。” 且夫天下非小弱也，雍州之地，殽函之固，自若也；陳涉之位，非尊於齊、楚、燕、趙、韓、魏、宋、衛、中山之君也；鋤耰棘矜，非銛於鉤戟長鎩也；謫戍之眾，非抗於九國之師也；深謀遠慮，行軍用兵之道，非及曩時之士也；然而成敗異變，功業相反也。試使山東之國，與陳涉度長絜大，比權量力，則不可同年而語矣；然秦以區區之地，致萬乘之權，招八州而朝同列，百有餘年矣；然後以六合為家，殽函為宮，一夫作難而七廟隳，身死人手，為天下笑者，何也？仁義不施，而攻守之勢異也。 此時秦朝的天下其實沒有變小變弱，雍州的肥沃土地，殽山、函谷關的險固，依舊像原來一樣；陳涉的地位，並不比齊、楚、燕、趙、韓、魏、宋、衛、中山的國君尊貴；鋤柄和棘木柄菜刀，並不比有勾的戟和長矛鋒利；被抓來充軍的混混，比不上九國的軍隊；創造點子，帶兵作戰的本領，也比不上從前六國的謀士將領：然而成功失敗完全改變，功業的大小恰恰相反。假如拿殽山以東諸國和陳涉來量長短比大小，比較權勢力量，根本不能相提並論！然而秦憑藉小小的雍州地方，到取得帝王的權勢，和其他八州的土地，而使各國諸侯來朝，長達一百多年！此後秦始皇把天下當作一家所有，把殽山、函谷關當作自家宮牆，但是，一個小混混發難，秦朝就消風了。二世子嬰死在項羽手中，被天下人笑到脫褲，這到底是什麼情形？由於不知施行仁義，同時，進攻和防守的情勢也改變了。

2 動態規劃演算法基本概念

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

4 動態規劃解題策略(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所產生的結果才可以得到問題的最佳解。這表示決策間必定有遞迴關係。

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

6 有些問題可以使用貪婪演算法解決 例:找出從v0到v3的最短路徑(shortest path)。 最短路徑: 1 + 2 + 4 = 7
貪婪演算法可以解決此問題。 最短路徑: = 7

7 有些問題不能使用貪婪演算法解決 例：從多階圖(multi-stage graph)中找出v0到v3的最短路徑。
貪婪演算法: v0v1,2v2,1v3 = 23 最佳解: v0v1,1v2,2v3 = 7 貪婪演算法無法解決此問題。 這是因為不同階(stage)的決策會影響到其他階的決策。

8 使用動態規劃解題策略的演算法 最長共同子序列演算法 最大連續子序列和動態規劃演算法 最小編輯成本演算法 0/1 背包動態規劃演算法
子集合加總動態規劃演算法 矩陣鏈乘積演算法 最佳二元搜尋樹動態規劃演算法 多階圖最小成本路徑演算法 Bellman-Ford最短路徑演算法 Floyd-Warshall最短路徑演算法

9 最長共同子序列演算法

10 最長共同子序列 以下我們說明最長共同子序列(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

11 最長共同子序列應用: 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）

12 最長共同子序列應用: 化身路徑群組 化身路徑群組(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 , 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.

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

14 最長共同子序列應用: 化身路徑群組(續) 將化身路徑轉為序列:
將虛擬世界切割為方格(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

15 最長共同子序列應用: 化身路徑群組(續) 找出兩條路徑對應的最長共同子序列以衡量其相似程度。
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.

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

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

18 最長共同子序列問題 子問題的遞迴關係 ì ï 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

19 最長共同子序列演算法 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

20 7 for i  1 to m do for j  1 to n do if xi = yj then c[i, j]  c[i-1, j-1]+1 b[i, j]  “” //for both i-1 and j-1 else if c[i–1, j]  c[i, j-1] then c[i, j]  c[i-1, j] b[i, j]  “” //for i-1 else c[i, j]  c[i, j-1] b[i, j]  “” //for j-1 only 17 return c and b

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

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

23 最長共同子序列演算法 如何找出最長共同子序列
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

24 最大連續子序列和動態規劃演算法

25

26

27 最小編輯成本演算法

28 最小編輯成本 (Minimum Edit Cost, MEC)問題
也稱為最小編輯距離 (Minimum Edit Distance, MED)問題 給定字串A=a1a2…am及字串B=b1b2...bn, MEC問題是要找到成本最低的一連串的編輯操作將字串A轉為字串B。可以使用的操作及其成本如下所述: 操作1: 由字串A刪除一個字元 (Cost1) 操作2: 在字串A插入一個字元 (Cost2) 操作3: 在字串A將一個字元換成另一個字元 (Cost3)

29 最小編輯成本 (Minimum Edit Cost, MEC)問題 (cont.)
MEC問題可以使用動態規劃演算法解決，在陣列c[i, j]中儲存將A的子字串a1a2...ai 轉為B的子字串b1b2...bj 的最小成本，其中 0  i  m 且 0  j  n。 c[i, j]的遞迴關係及其邊界條件是動態規劃演算法的設計核心。

30 最小編輯成本 (Minimum Edit Cost, MEC)問題 (cont.)
c[i, j]的遞迴關係 a1a2...ai  b1b2...bj 𝑐 𝑖, 𝑗 = 𝑐 𝑖−1, 𝑗− 𝑖𝑓 𝑎 𝑖 = 𝑏 𝑗 𝑚𝑖𝑛 𝑐 𝑖−1, 𝑗 +Cost 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 𝑐 𝑖, 𝑗−1 +Cost 𝑐 𝑖−1, 𝑗−1 +Cost3

31 最小編輯成本 (Minimum Edit Cost, MEC)問題 (cont.)
c[i, j]的邊界條件 c[m, n] 就是解答 a1a2...ai  Null Null  b1b2...bj 𝑐 𝑖,0 =𝑖×cost1 , 𝑓𝑜𝑟 0≤𝑖≤𝑚 𝑐 0,𝑗 =𝑗×cost2 , 𝑓𝑜𝑟 0≤𝑗≤𝑛

32 0/1 背包動態規劃演算法

33 0/1 背包問題 0/1 knapsack problem
n個物品， 帶著重量 w1, w2, , wn, 值 (利潤) v1, v2, , vn, 背包載重容量 (capacity) W, 欲最大化 , 限制條件為  W, xi = 0 or 1, 1in。 (令 S={1,…,n}且T={i | xi=1}S)

34 暴力法解決方案 (brute force solution)
0/1背包問題(或簡稱背包問題)是一個最佳化問題(optimization problem)。 我們可以一一試過S集合所有2n個子集合來解這問題，其時間複雜為O(2n)。 問題: 有任何解決方案比暴力法更好嗎? 回答: 有。我們可以利用動態規劃(dynamic programming, DP) ，用空間(表格或陣列)以換取時間(trade space for time)。

35 表格(陣列) 我們建構一個陣列V[0..n, 0..W]。
元素V[i, w], 1in, 且 0wW, 將儲存來自物品1,2,…,i的任何子集合的最大合併價值，而這些物品的合併重量為w。 如果我們可以計算陣列中的所有元素，那麼元素V[n, W]儲存的值為物品1,2,…,n中的任一子集合，此子集合中的物品可以放入容量W的背包中，而具有最大的合併價值。

36 遞迴關係 初始化設定(initial settings): V[0, w]=0 for 0wW
若wiw，則 V[i, w]=max(V[i-1, w], vi+V[i-1, w-wi]) 否則，V[i, w]=V[i-1, w] for 0in and 0wW

37 使用迭代(iteration)而非遞迴(recursion) 由下而上(bottom-up)計算V[i, w]
由下而上的計算：逐行的計算表格，使用

38 超多項式時間：O(c^f(n))，其中c為大於1的常數，f(n)大於常數，小於線性。
時間複雜度：O(nW)

39 備註： 最後的輸出為: 這方法並沒有告訴我們最佳解是由哪個S={1,2,3,4}的子集合所產生的(在這個例子中為子集合{2,4})

40 前面提到的用於計算V[i, w]的演算法，並沒有記錄那些物品所形成的子集合可以形成最佳解。
為了計算出實際形成最佳解的子集合，我們增加一個輔助的布林陣列keep[i, w]，若第 i 個物品在子集合中，則設其值為 1，否則設其值為 0。

41 若 keep[n, W]為1，則 n∈𝑇，我們可以重複這種討論來計算 keep[n-1, W-wn]
因此，以下的碼可以輸出T中的元素。

42

43 0/1背包決策問題是經典的NPC問題。 (0/1背包問題是經典的NP-hard問題)。
解0/1背包問題的DP演算法時間複雜度為O(nW) 這是多項式時間嗎? 時間複雜度O(nW)是偽多項式時間(pseudo-polynomial time)。

44 多項式及偽多項式時間

45 多項式及偽多項式時間 多項式時間(polynomial time): 計算時間T(n)不大於問題規模n的多項式。也就是T(n)=O(nk)，k為常數。 偽多項式時間(pseudo-polynomial time): 如果時間複雜度是輸入數值(numeric value of the input)的多項式，但卻是輸入長度(the length of the input)的指數函數，那麼稱其為偽多項式時間。 深層定義: 一個問題的輸入規模(input size)為將整個輸入表達出來的位元數(The size of the input to a problem is the number of bits required to write out that input.) Source: The size of the input to a problem is the number of bits required to write out that input. For example, if the input to a sorting algorithm is an array of 32-bit integers, then the size of the input would be 32n, where n is the number of entries in the array.   If you use something like selection sort to do this, the runtime, as a function of the number of input elements in the array, will be O(n2). But how does n, the number of elements in the input array, correspond to the the number of bits of input? As mentioned earlier, the number of bits of input will be x = 32n. Therefore, if we express the runtime of the algorithm in terms of x rather than n, we get that the runtime is O(x2), and so the algorithm runs in polynomial time. Things break down, however, when we start talking about algorithms that operate on numbers. Let's consider the problem of testing whether a number is prime or not. Given a number n, you can test if n is prime using the following algorithm: function isPrime(n): for i from 2 to n - 1: if (n mod i) = 0, return false return true So what's the time complexity of this code? Well, that inner loop runs O(n) times and each time does some amount of work to compute n mod i (as a really conservative upper bound, this can certainly be done in time O(n3)). Therefore, this overall algorithm runs in time O(n4) and possibly a lot faster. Unfortunately, we don't. Remember, the formal definition of time complexity talks about the complexity of the algorithm as a function of the number of bits of input. Our algorithm runs in time O(n4), but what is that as a function of the number of input bits? Well, writing out the number n takes O(log n) bits. Therefore, if we let x be the number of bits required to write out the input n, the runtime of this algorithm is actually O(24x), which is not a polynomial in x.

46 子集合加總演算法

47

48

49 矩陣鏈乘積演算法

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

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

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

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

54 矩陣鏈乘積問題 (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.

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

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

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

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

59 矩陣鏈乘積演算法解題思維步驟 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].

60 矩陣鏈乘積演算法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 m[i, j]   for k  i to j – 1 9 do q  m[i, k] + m[k+1, j]+ pi-1pkpj if q < m[i, j] then m[i, j]  q s[i, j]  k 13 return m and s 時間複雜度:

61 例子:

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

63 m[2,5]= min{ m[2,2]+m[3,5]+p1p2p5= 1520=13000, m[2,3]+m[4,5]+p1p3p5= 520=7125, m[2,4]+m[5,5]+p1p4p5= 1020=11374 } =7125

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

65 最佳二元搜尋樹動態規劃演算法

66 最佳二元搜尋樹 Optimal binary search trees
給定一個有n個不同鍵(key)的已排序的序列(sorted sequence)K=<k1,k2,…,kn>，其中k1<k2<…<kn，而且每個鍵ki都伴隨著一個可能被搜尋機率pi (1in)；另外，有些搜尋無法在K中的鍵找到，因此，還有n+1個假鍵(dummy key) d0,d1,d2,…,dn，其中d0代表所有小於k1的鍵，dn代表所有大於kn的鍵，而其他鍵di則代表介於ki與ki+1的鍵。每個假鍵di都伴隨一個機率qi (0in)。 如何在上述的給定條件下，建立一個最佳二元搜尋樹(optimal binary search tree)，使其具有最小期望搜尋成本(smallest expected search cost)。

67 最佳二元搜尋樹 Optimal binary search trees
cost:2.75 最佳!! cost:2.80

68 預期成本 在T中搜索的預期成本是 根(root)的深度(depth)為0

69 最佳二元搜尋樹的期望搜索成本

70 最佳化二元搜尋樹的結構 考慮一個二元搜索樹的任意子樹。它必須包含在一個連續範圍鍵 ki, ...,kj(1  i  j  n)。此外，包含鍵值 ki, ..., kj的一個子樹也必須包含假鍵di-1, ..., dj為它的葉節點。 如果一個最佳化二元搜尋樹T 有一個子樹T’包含鍵值ki, ...,kj ，那麼對於鍵ki, ...,kj和假鍵di-1, ..., dj所對應的子問題而言，子樹T’必須是最佳化的。

71 期望搜索成本 令e[i, j]代表一個包含鍵ki,…,kj與假鍵di-1,…,dj最佳二元搜尋樹的期望搜索成本，其中i1，jn，ji-1。 我們最終想要求出e[1, n]。 可以直接求得的起始值為e[i, i-1]=qi-1，因為e[i, i-1]代表一個僅包含假鍵di-1最佳二元搜尋樹的期望搜索成本。

72 遞迴解 (recursive solution)
j j = + w ( i , j ) å p å q 令  w[i, j] = w[i, j – 1] + pj+qj l l l = i l = i - 1 如果包含ki,…,kj的最佳化樹的根位於kr ，那麼 e[i, j]=pr+(e[i, r-1]+w(i, r-1))+(e[r+1, j]+w(r+1, j)) = - + + + e [ i , r 1 ] e [ r 1 , j ] w ( i , j)

73 遞迴解 (recursive solution)
q if j = i - 1, ì i - 1 e [ i , j ] = í min { e [ i , r - 1 ] + e [ r + 1 , j ] + w ( i , j )} if i j . î i r j

74 最佳二元搜尋樹演算法OPTIMAL-BST
OPTIMAL-BST(p,q,n) 1 for i  1 to n + 1 2 e[i, i – 1]  qi-1 3 w[i, i – 1]  qi-1 4 for l  1 to n 5 for i  1 to n – l + 1 j  i + l – 1 e[i, j]   w[i, j]  w[i, j – 1] + pj+qj

75 9 for r  i to j t  e[i, r –1]+e[r +1, j]+w[i, j] if t < e[i, j] then e[i, j]  t root[i, j]  r 14 return e and root OPTIMAL-BST 演算法時間複雜度 (n3)

76 OPTIMAL-BST計算表格(陣列)e[i,j], w[i,j], 及root[i,j]的過程

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

78 多階圖最小成本路徑問題 (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)。

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

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

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

82 動態規劃遞迴關係 (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.

83 解決多階圖最小成本路徑問題的動態規劃演算法
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]

84 Bellman-Ford 最短路徑演算法

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

86 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次迭代求出 的路徑已經是最終的正確結果了。

87 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

88 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|)

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

90 Floyd-Warshall 最短路徑演算法

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

92 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中所紀錄的最短路徑是可以經由所有節點當作中間節點所造成的，這也就是演算法所需要的結果。

93 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

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

95 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)

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

97 多項式、超多項式、偽多項式時間 多項式時間(polynomial time): 計算時間T(n)不大於問題規模n的多項式。也就是T(n)=O(nk)，k為常數。 偽多項式時間(pseudo-polynomial time): 如果時間複雜度是輸入數值(numeric value of the input)的多項式，但卻是輸入長度(the length of the input)的指數函數，那麼稱其為偽多項式時間。 深層定義: 一個問題的輸入規模(input size)為將整個輸入表達出來的位元數(The size of the input to a problem is the number of bits required to write out that input.) Source: The size of the input to a problem is the number of bits required to write out that input. For example, if the input to a sorting algorithm is an array of 32-bit integers, then the size of the input would be 32n, where n is the number of entries in the array.   If you use something like selection sort to do this, the runtime, as a function of the number of input elements in the array, will be O(n2). But how does n, the number of elements in the input array, correspond to the the number of bits of input? As mentioned earlier, the number of bits of input will be x = 32n. Therefore, if we express the runtime of the algorithm in terms of x rather than n, we get that the runtime is O(x2), and so the algorithm runs in polynomial time. Things break down, however, when we start talking about algorithms that operate on numbers. Let's consider the problem of testing whether a number is prime or not. Given a number n, you can test if n is prime using the following algorithm: function isPrime(n): for i from 2 to n - 1: if (n mod i) = 0, return false return true So what's the time complexity of this code? Well, that inner loop runs O(n) times and each time does some amount of work to compute n mod i (as a really conservative upper bound, this can certainly be done in time O(n3)). Therefore, this overall algorithm runs in time O(n4) and possibly a lot faster. Unfortunately, we don't. Remember, the formal definition of time complexity talks about the complexity of the algorithm as a function of the number of bits of input. Our algorithm runs in time O(n4), but what is that as a function of the number of input bits? Well, writing out the number n takes O(log n) bits. Therefore, if we let x be the number of bits required to write out the input n, the runtime of this algorithm is actually O(24x), which is not a polynomial in x.

98 弱NPC問題 與 強NPC問題 一個具有偽多項式時間複雜度的NPC問題稱之為弱NPC問題(weakly NPC problem)。
若一個NPC問題被證明除非P=NP，不然不可能有偽多項式時間複雜度的解，則稱之為強NPC問題(strongly NPC problem)。 背包問題是弱NPC問題。子集合加總問題(subset sum problem)也是弱NPC問題。 強NP-hard問題與弱NP-hard問題也可以同樣的方式定義。

99 Q&A