短視近利 與 深謀遠慮 國立中央大學 資訊工程學系 江振瑞 教授 貪婪演算法 與 動態規劃演算法 短視近利 與 深謀遠慮 國立中央大學 資訊工程學系 江振瑞 教授

3.1 貪婪演算法基本概念

貪婪解題策略 貪婪演算法(greedy algorithm)使用貪婪策略(greedy strategy)解決問題。 假設一個問題可以藉由一系列的選擇(或決策)來解決，貪婪演算法的特性為每一次選擇皆採取區域最佳解(locally optimal solution)，而透過每一個區域最佳解最後綜合成為全域最佳解(globally optimal solution)而將問題解決。 換句話說，貪婪演算法一步步地建構出一個問題的完整解答。其每一步都藉由貪婪解題策略選擇當下最好的部份解答加入完整解答中以解決問題。

使用貪婪解題策略的演算法 背包(Knapsack)演算法 Huffman編碼演算法 Kruskal最小含括樹演算法 Prim最小含括樹演算法 Dijkstra最短路徑演算法

3.2 背包演算法

背包演算法背景介紹 背包演算法(knapsack algorithm)使用貪婪解題策略解決背包問題(knapsack problem)或稱為零碎背包問題(fractional knapsack problem) 以下我們先定義背包問題

定義 -- 背包問題 給定一個最大載重容量(capacity)為m的背包，以及n個可以放入背包的物品，其中第i個物品的重量為wi>0，價格為pi>0 目標: 找出x1,…,Xn以最大化 限制條件為 其中 0xi1, 1  i  n

背包演算法 Algorithm 背包演算法 Input: 背包的最大容量m，以及可以放入背包的n個物品的非負重量wi與價格pi Output: 介於0與1之間的x1,…,xn分別代表第1個,…,第n個物品放入背包中的零碎部份。可以最大化 ，並且滿足 。 1: 將pi/wi由大至小排序。 2: 根據此排序來將物品依序盡可能地放入背包中，直至背包容量m用完為止。 The greedy algorithm: Step 1: Sort pi/wi into non-increasing order. Step 2: Put the objects into the knapsack according to the sorted sequence as much as possible.

背包演算法時間複雜度 行1: 依pi/wi由大至小排序: O(n log n) 行2: 將物品依序放入背包: O(n) The greedy algorithm: Step 1: Sort pi/wi into non-increasing order. Step 2: Put the objects into the knapsack according to the sorted sequence as much as possible.

背包演算法範例 給定: 貪婪策略解答: n = 3, m = 5, (w1, w2, w3) = (1, 2, 3) (p1, p2, p3) = (20, 60, 45) 貪婪策略解答: p1/w1 = 20/1 = 20 p2/w2 = 60/2 = 30 p3/w3 = 45/3 = 15 最佳解: x2 = 1, x1 = 1, x3 = 2/3 最大總價值: 601+201+45(2/3)=110

定義 -- 0/1背包問題 給定一個最大載重容量(capacity)為m的背包，以及n個可以放入背包的物品，其中第i個物品的重量為wi>0，價格為pi>0 目標: 找出x1,…,Xn以最大化 限制條件為 其中 xi=0 or xi=1, 1  i  n

0/1背包演算法範例 給定: 貪婪策略解答: n = 3, m= 5, (w1, w2, w3) = (1, 2, 3) (p1, p2, p3) = (20, 60, 45) 貪婪策略解答: p1/w1 = 20/1 = 20 p2/w2 = 60/2 = 30 p3/w3 = 45/3 = 15 解答: x2 = 1, x1 = 1, x3 = 0 總價值: 601+201+450=80 最佳解: x1 = 0, x2 = 1, x3 = 1 總價值: 200+601+451=105

背包演算法與 0/1背包演算法範例圖示

3.3 Huffman編碼演算法

Huffman編碼 字元編碼(character coding)可以分為 固定長度編碼: 如ACSII、Unicode 可變長度編碼: Huffman code Huffman編碼以字首碼(prefix code)方式達到字元編碼最佳資料壓縮(optimal data compression) 字首碼 (prefix code): 任何字元編碼一定不是其他字元編碼的字首(prefix)。 可以使用二元樹來呈現，達到簡單編碼(encoding)與解碼(decoding)的功能。

Huffman編碼範例 假設給定一個僅用到a, b, c, d, e五個字元的文件，現在欲針對五個字元進行編碼，以下是可能的固定長度編碼與可變長度的Huffman字首碼。 字首碼讓出現頻率較高字元的編碼較短，以達到使用最少位元就可以將所有資料儲存的目標。 a b c d e 出現頻率 14% 17% 23% 6% 40% 固定長度編碼 000 001 010 011 100 可變長度編碼 1111 110 10 1110

對應不同編碼的樹及其成本 Cost(T)=3 Cost(T)=2.17

Huffman編碼演算法 Algorithm Huffman編碼演算法 Input: 字元集合C與每個字元的出現頻率f Output: Huffman編碼樹 1. n  |C| //C: the set of n characters 2. Q  C //Q: 優先佇列，以字元頻率為優先次序 3. for i  1 to n – 1 //n個字元(節點)欲合併成一個節點，每迭代合併一次可少一節點 4. 配置一個新的樹節點u 5. u.left  x  GetMin(Q) 6. u.right  y  GetMin(Q) 7. u.f  x.f + y.f 8. Insert u into Q 9. return GetMIN(Q) 作為Huffman編碼樹的樹根

Huffman編碼演算法時間複雜度 行2: O(n)建立優先佇列Q 行3-8: for迴圈一共執行n-1次，而且迴圈中的優先佇列操作均為O(log n)複雜度，因此整個迴圈具有O(n log n)的複雜度 總時間複雜度: O(n log n) The greedy algorithm: Step 1: Sort pi/wi into non-increasing order. Step 2: Put the objects into the knapsack according to the sorted sequence as much as possible.

Huffman編碼演算法的執行範例

Huffman編碼演算法的執行範例(續)

Huffman編碼演算法的執行範例(續)

Huffman編碼演算法的執行範例(續)

Huffman編碼演算法的執行範例(續) (4)

3.4 Kruskal最小含括樹演算法

最小含括樹 最小含括樹(Minimum Spanning Tree, MST)可以定義在歐氏空間(Euclidean space)或者一個圖(graph)上。 給定一個加權連通無向圖(weighted connected undirected graph) G = (V, E) 含括樹(spanning tree) H= (V, T), T  E, 是一個無向樹(undirected tree)，它是G的子圖，包含G的所有節點 最小含括樹MST是一個擁有最小(minimum)總加權(weight)或總成本(cost)的含括樹。

最小含括樹範例 圖G的最小含括樹(非唯一) 一個圖G

Kruskal最小含括樹演算法概念 Kruskal最小含括樹演算法是一個貪婪演算法(greedy algorithm) 它採取貪婪解題策略產生給定圖G=(V, E)的最小含括樹H=(V, T)，每次都是挑選最小成本且不形成cycle的邊加入目前的最小含括樹的邊集合T之中 因為n個節點的樹具有n-1個邊，因此，經過n-1次邊的挑選之後，就可以形成累積成本最小的含括樹。

Kruskal最小含括樹演算法 Algorithm Kruskal最小含括樹演算法 Input: 無向加權圖G=(V, E)，其中|V|=n Output: G的最小含括樹(MST)H=(V, T) T← //T為MST的邊集合，一開始設為空集合 while T包含少於n-1個邊 do 選出邊(u, v)，其中(u, v)E，且(u, v)的加權(weight)最小 E←E-(u, v) if ( (u, v)加入T中形成循環(cycle) ) then 將(u, v)丟棄 else T←T(u, v) return H=(V, T)

Kruskal最小含括樹演算法執行範例

Kruskal最小含括樹演算法討論 Q: 我們如何檢查加入新的邊是否會形成循環? A: 使用 集合 (SET) 尋找與 聯集 (UNION)操作 使用 集合 (SET) 與 聯集 (UNION)操作。 考慮樹的節點集合: 一開始產生n個包含單一節點的集合；也就是說若V={v1,…,vn} ，則產生{v1}, {v2},…,{vn} 加入邊(u, v)是否會形成循環: 找出u,v所屬的集合，若 u, v 在相同的集合, 則加入邊(u, v)會形成循環。反之，若uS1 , vS2 ,而且 S1S2則加入邊(u, v)不會形成循環，此時應對 S1 與 S2 進行聯集操作。

Kruskal演算法的時間複雜度 時間複雜度: O(|E| log|E|) 排序 : O(|E| log|E|) O(|E| log|E|) 找出元素所在的集合 O(log |V|) : O(|E| log |V|) |E|  |V|2 聯集兩集合 O(log |V|) =O(|V|2 log |V|) =O(n2 log n)

3.5 Prim最小含括樹演算法

Prim最小含括樹演算法概念 Prim最小含括樹演算法是一個貪婪演算法(greedy algorithm)。 它採取貪婪解題策略產生給定圖G=(V, E)的最小含括樹H=(V, T)。此演算法先隨意挑一個節點加入集合X中，此後每次都挑選一個一端的節點在X中，而另一端的節點在(V-X)中的最小成本的邊。如此，可保證將所挑選的邊加入T之後不會形成循環(cycle)，這代表H=(V, T)是一棵樹(tree)。 等挑完n-1個邊之後，H=(V, T)就是最小含括樹(MST)。

Prim最小含括樹演算法 Algorithm Prim最小含括樹演算法 Input: G=(V, E)為無向加權圖，其中|V|=n Output：G的最小含括樹(MST)H=(V, T) T← //T為MST的邊集合，一開始設為空集合 X←{v} //隨意選擇一個節點v加入集合X中 while T包含少於n-1個邊 do 選出(u, v)E，其中uX且vV-X，且(u, v)的加權(weight)最小 T←T(u, v) //(u, v)是一個邊 X←X{v} return H=(V, T)

Prim最小含括樹演算法執行範例

Prim最小含括樹演算法時間複雜度 外層的while迴圈(行3-6): n-1  O(n) 內層迴圈(行4): 在(u, v)中選擇最小加權，其中u屬於X，v屬於V-X  O(n) (藉著使用Prim提出的兩個向量C1和C2) (Ref: R. C. Prim, “Shortest connection networks and some generalizations,” Bell System Technical Journal, 36(1389–1401), 1957.) 比較: 如果 |E|<<n2，則採用Kruskal演算法 (複雜度O(|E| log|E|)效能較佳

3.6 Dijkstra最短路徑演算法

圖的最短路徑 由圖(graph)中的某個節點(vertex or node)v到圖中的另一節點u，若v到u之間存在一條路徑(path)，則路徑中所經過的邊(edge)的加權(weight)的總合稱為路徑的成本(cost)或距離(distance)。所有路徑中具有最小成本的稱為最短路徑(shortest path)。 由於最短路徑具有許多應用，因此有許多求取最短路徑的演算法，著名的演算法包括： (1) Dijkstra演算法(使用貪婪解題策略) (2) Bellman-Ford演算法(使用動態規劃解題策略) (3) Floyd-Warshall演算法(使用動態規劃解題策略)

Dijkstra最短路徑演算法設計者 E. W. Dijkstra(1930年5月11日－2002年8月6日)生於荷蘭鹿特丹 在1972年獲得圖靈獎(Turing Award) 2002年，Dijkstra獲得了ACM PODC (Principles of Distributed Computing) 最具影響力論文獎(Influential Paper Award)，以表彰他在分散式計算(distributed computing)領域中關於自我穩定(self stabilization)計算模式的貢獻。為了紀念他，這個每年一度獎項也在此後被更名為Dijkstra獎(Dijkstra Prize) Source: http://en.wikipedia.org/wiki/Edsger_W._Dijkstra Creative Commons Attribution-Share Alike 3.0 Unported Author:Hamilton Richards

Dijkstra最短路徑演算法 是喝咖啡時20分鐘想出的發明 “One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a 20-minute invention. In fact, it was published in 1959, three years later.” Thomas J. Misa (Editor), "An Interview with Edsger W. Dijkstra," Communications of the ACM 53 (8): 41–47, 2010. Attribution 2.0 Generic (CC BY 2.0) Elliott Brown Source: https://www.flickr.com/photos/ell-r-brown/14165662691/in/photolist-

Dijkstra最短路徑演算法介紹 Dijkstra演算法: Dijkstra演算法屬於求取單一(single)(來)源(source)(節)點至全部(all)(目)標(destination)(節)點的單源點至全標點之一至全(one-to-all)最短路徑演算法。 Dijkstra演算法只能用在所有的邊都是非負邊(non-negative weighted edge)的圖。因為負邊有可能產生負循環，因而無法產生正確的最短路徑，而Dijkstra演算法並無法檢查給定的圖是否有負循環。 Dijkstra最短路徑演算法採用貪婪策略解決問題，每次都挑選一個目前可以由源節點抵達距離(累積邊加權)最小的節點往外調整其鄰居節點的最短路徑距離。在經過n次(n為節點個數)的節點選擇之後，則所有的節點都可以求得由單一源節點可以抵達的最短路徑距離。

Dijkstra最短路徑演算法 Algorithm Dijkstra最短路徑演算法 Input：給定一個非負加權有向圖(non-negative 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 將每一個節點加入優先佇列Q while Q≠ do 自Q中移出具有最小d[u]值之節點u for 每一個與u相鄰之節點x do if d[x] > d[u]+w[u][x] then d[x]←d[u]+w[u][x] return d

Dijkstra最短路徑演算法 如何記錄所有路徑經過的節點? 若要讓Dijkstra演算法也能夠求出每一條最短路徑所經過的每一個節點，則我們要將每一節點在最短路徑中的前一節點紀錄下來，其作法為增加一個陣列p(代表predecessor，前行節點)來記錄最短路徑中的每一個節點的前一節點。 Dijkstra演算法之if敘述修改如下： if (d[x] > d[u]+w[u][x]) then d[x]←d[u]+w[u][x] p[x]←u //此為新加敘述，代表在最短路徑中節點ｘ的前一節點為u

Dijkstra演算法執行範例 (0)是初始狀態，(1)是第一次迭代之後的狀態，(2)-(5)類推。 粗黑邊對應Predecessor的值，由前行節點指向路徑中下一個節點。 節點u內的數字代表d[u]，是現存的由源點s到達節點u的最短路徑距離。 加星號表示每個迭代以貪婪色略所選擇的節點，綠色表示未被挑過的節點，而黃色表示已經被挑過的節點。

Dijkstra最短路徑演算法 時間複雜度 假設G一共有n個節點，m個邊(也就是|V|=n, |E|=m) 行2將每一個節點加入優先佇列Q，因此Q具有n個元素 行3的while迴圈每次迭代會自Q中次移出一個節點，因此會執行n次迭代 行4使用O(log n)時間自Q中移出最小d[u]值之節點u 行5的for迴圈在整個演算法的執行過程中一共執行m次迭代 行7使用O(log n)的時間根據新的d[u]值更新u在Q中的位置(先刪除u再新增u) 因此總時間複雜度為O((n+m) log n)=O( (|V|+|E|) log |V|)

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

動態規劃解題策略 動態規劃演算法(dynamic programming algorithm)使用動態規劃策略(dynamic programming strategy)解決問題。它將原問題分解成一系列相依子問題(subproblems)，並作出一系列的決策解決子問題以解決原問題。 然而這些子問題是相依的，因此一個子問題的決策需要遞迴地參考許多不同子問題的決策。為避免一再地解重複的子問題，一旦確認解出子問題的最佳解答(solution)，即會將其存在表格(或陣列)中。當需要用到某一子問題的解答時，即直接從表格中取出其解答以節省遞迴計算時間，是一個「系統化」的、「節省不必要計算」的、「以空間換取時間」的演算法。

動態規劃解題策略(續) 一般動態規劃演算法的設計原則如下: 決定需要建構的表格 決定遞迴關係 決定填表格順序，用以填完表格而解決問題 一般依照遞迴關係中的邊界條件(boundary condition)將初始值(initial value)填入表格，然後以由底而上(bottom-up)的方式持續運行直至填完整個表格而求出原問題解答為止。

動態規劃與貪婪演算法之比較 比較: 二者都是透過一系列的決策以解決問題，但是有以下的不同點: 在貪婪演算法中，任何決策都是獨立(independent)的，都只要考慮區域最佳解(locally optimal)。 而這些區域最佳解最後可以匯總為全域最佳解(globally optimal solution)。 在動態規劃演算法中，決策是相依的(dependent)，也就是說每個決策不能只是考慮區域最佳解。 若需要執行n次決策，則第i次決策與第1次到第i-1次連續決策所產生的狀態是相依的；或是說第i次決策與第i+1次到第n次連續決策所產生的狀態是相依的。

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

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

多階圖最小成本路徑問題簡單範例 輸入: 一個多階圖 輸出: 節點S到節點T的 最小成本路徑 就像分三期付款以取得商品的產權一樣。有的付款方式第一期要繳1萬，有的要繳3萬，有的要繳6萬。但是依照不同的第一期繳法，則在第二期及第三期有不同的繳款選擇，而造成繳款總額的不同。我們當然想要選擇最少繳款總額的方式。 貪婪演算法無法解決此問題: S A D T  cost = 1+2+17 = 20. 實際最短路徑: S C F T  cost = 6+3+1 = 10. 輸入: 一個多階圖 輸出: 節點S到節點T的 最小成本路徑 就像買房子一樣，分三期付款，最終都可以得到房子的產權。有的付款方式第一期要繳1萬，有的要繳2萬，有的要繳5萬。但是依照不同的第一期繳法，則在第二期甚或第三期都有不同的繳款選擇，而造成總繳款數的不同。

多階圖定義 一個k階(k-stage),k2,多階圖(multi-stage graph) G=(V,E)是一個加權有向圖(weighted digraph)，其節點被分割置入k個互斥集合(disjoint sets) V1, V2, …,Vk。 其中每一個集合Vi, 1 i  k, 被定義為圖中的第i階(ith stage)，而且V1 和 Vk 都僅包含一個節點(node or vertex)。V1 中的節點稱為源點(source)，而Vk中的節點稱為標點(target或destination)。 此外，若<u,v>是E的邊，則uVi 且 vVi+1，1 i <k，而每個邊都有一個加權(weight)(或稱為成本或距離)。

多階圖範例 以下是一個4階多階圖

多階圖最小成本路徑問題 多階圖最小成本路徑問題(multi-stage graph minimum-cost path problem)定義: 給定一個k階多階圖G=(V,E)，找出從 V1 中的源點(source) v1(或s) 到 Vk 中的標點(target) vk(或t) 的最小成本路徑(minimum-cost path)。

多階圖最小成本路徑問題範例 範例：從以下多階圖(multi-stage graph)中找出v1到v4的 最短路徑 貪婪演算法解答: v1v2,2v3,1v4  cost = 1+1+29=31 最佳解: v1v2,3v3,4v4  cost = 6+3+1=10 貪婪演算法無法解決此問題，這是因為不同階(stage)的決策會影響到其他階的決策，它們是相依的。

使用動態規劃演算法解決 多階圖最小成本路徑問題 決定表格結構: 我們首先決定使用陣列d[x]來儲存節點x到標點的最短路徑距離(或成本)，使用陣列p[i]來儲存最短路徑在第i階所經過的節點。 然後我們決定表格間不同元素的遞迴關係(如下頁所示)。 最後我們由底而上地(由第k, 第k-1,…,到第1階)填完表格而得到解答。

動態規劃遞迴關係 動態規劃遞迴關係: d[S, T] = min{1+d[A, T], 3+d[B, T], 6+d[C, T]}

動態規劃遞迴關係(續) d[A, T] = min{2+d[D, T], 10+d[E, T]} = min{2+(17+d[T,T]), 10+(12+d[T,T])} = min{2+17+0, 10+12+0}=19. 邊界條件: d[T, T]=0

多階圖最小成本路徑演算法 Algorithm 多階圖最小成本路徑演算法 Input: 具n個節點的k階多階圖G(V, E), V= i=1..k Vi , ViVj= for ij, V1={1},Vk={n}, <x,y>E (xVi  yVi+1), <x,y>的加權為w[x,y] Output: 具k個節點由節點1到節點n的最小成本路徑(記錄在p[1..k]中)及其最 小成本(記錄在d[1]中) d[n]=0; d[1..n-1]=; //陣列d[x]儲存節點x到標點t的最小距離(distance) for ik-1 to 1 do for every node x in Vi do for every edge <x, y>E do if (d[x]>w[x,y]+d[y]) do d[x]=w[x,y]+d[y] s[x]=y //s代表節點的下節點(successor) p[1]=1;p[k]=n; //陣列p[i]儲存最短路徑在第k階的節點 for i2 to k-1 do p[i]s[p[i-1]]; return p,d[1]

多階圖最小成本路徑演算法 時間複雜度 行1: 設定d[0],d[1..n]啟始值: O(n) 行2-4: 三層for迴圈實際執行|E|次迭代: O(|E|) 行5-7: 迴圈內if敘述執行需要常數時間 行8: 2個設定敘述 行9: for迴圈執行k-2次迭代: O(k) 行10: 回傳演算法執行結果需要常數時間 總時間複雜度: O(n + |E| + k)  O( |E| ) 一般|E|比k與n都大，因此我們可以將總時間複雜度寫為 O(n + |E| + k)  O( |E| )

3.9 0/1背包演算法

定義 -- 0/1背包問題 給定一個最大載重容量(capacity)為m的背 包，以及n個可以放入背包的物品，其中第i 個物品的重量為wi>0，價格為pi>0 目標: 找出x1,…,xn以最大化 限制條件為 其中 xi=0 or xi=1, 1  i  n (令 S={1,…,n}且T={i | xi=1}S)

使用暴力法解決0/1背包問題 0/1背包問題是一個最佳化問題(optimization problem)。 我們可以測試S集合的所有2n個子集合來解這問題，其時間複雜為O(2n)。 Q: 有任何比暴力法更好的演算法嗎? A: 有。我們可以利用動態規劃(dynamic programming)策略，用空間(表格或陣列)以換取時間(trade space for time)。

0/1背包演算法 建構表格(陣列) 我們建構一個陣列P[0..n, 0..m]。 元素P[i, w], 1in, 0wm, 用以儲存物品集合{1,2,…,i}的所有可能子集合中的物品最大總價值，而這些物品的總重量小於等於w。 如果我們可以計算出陣列中的所有元素，那麼元素P[n, m]儲存的值為物品集合{1,2,…,n}的所有可能子集合中的物品最大總價值，而這些物品的總重量小於等於m。

0/1背包演算法 確定遞迴關係 初始化設定(initialization): P[0, w]=0 for 0wm 對所有的i與w(0in, 0wm)而言: max(P[i-1, w], pi+P[i-1, w-wi]), if wiw P[i, w]=P[i-1, w], otherwise P[i, w]=

0/1背包演算法 由底而上的逐一將表格填完 i, w由小而大，或稱由底而上(bottom up)，根據上頁的遞迴關係，逐一計算P[i, w]的值，將表格填完。 P[i, w] w=0 1 2 … m i=0   n 解 答

0/1背包演算法 Algorithm 0/1背包演算法 Input:背包的最大容量m，以及可能放入背包的n個物品(編號為1,…,n)的非負重量wi與價格pi, 1in。 Output: 以全放或全不放的方式容納在背包中所有物品的最大總價值 for w←0 to m do P[0, w]=0 for i←1 to n do for w←0 to m do if wiw then P[i,w]=max(P[i-1, w], pi+P[i-1, w-wi]) else P[i,w]=P[i-1, w] return P[n,m]

0/1背包演算法範例 Input: n=3, m=8 Table: Output: p[3,8]=50 i 1 2 3 wi 5 4 pi 20 30 10 Table: P[i,w] w=0 1 2 3 4 5 6 7 8 i=0 20 30 50 40 The greedy algorithm: Step 1: Sort pi/wi into non-increasing order. Step 2: Put the objects into the knapsack according to the sorted sequence as much as possible. Output: p[3,8]=50

0/1背包演算法 時間複雜度 行1: 設定P[0,1..m]初始值: O(m) 行2: 外層for迴圈執行n次迭代: O(n) 行3: 內層for迴圈執行m次迭代: O(m) 行4-7: 迴圈內敘述執行需要常數時間 行8: 回傳演算法執行結果需要常數時間 總時間複雜度: O(n  m) The greedy algorithm: Step 1: Sort pi/wi into non-increasing order. Step 2: Put the objects into the knapsack according to the sorted sequence as much as possible.

0/1背包演算法時間複雜度討論 0/1背包演算法時間複雜度為O(nm) Q: 這是多項式時間嗎? A: 實際上這個演算法是屬於偽多項式時間(pseudo-polynomial time)。 如果一個演算法的時間複雜度是輸入數值(numeric value of the input)的多項式，但卻是輸入長度(the length of the input)的指數函數，那麼該演算法屬於偽多項式時間複雜度。 例如，若m以長度為K位元的無正負號的二進位數字來表示，則表格p有2k-1個直欄，而0/1背包演算法時間複雜度為O(n2k)，為輸入長度k的指數函數。

0/1背包演算法 如何找出哪些物品該放在背包中? 前面提到的0/1背包演算法只計算P[i,w]，也就是背包中物品的最高總價值，並沒有記錄哪些物品所形成的子集合T(TS)可以達成最高總價值的最佳解。 為了計算出實際達成最佳解的子集合，我們增加一個輔助的布林陣列Q[1..n, 1..m]。若P[i,w]得最佳解答時，第 i 個物品在子集合T中，則Q[i,w]設為 1；否則Q[i,w]設為 0。

0/1背包演算法 如何找出哪些物品該放在背包中?? 若Q[n, m]為1，則nT，我們可以遞迴地檢查Q[n-1, m-wn] 若Q[n, m]為0，則 nT，我們可以遞迴地檢查Q[n-1, m] 因此，以下的碼可以找出T中的元素。 k=m T for in to 1 do if Q[i, k]=1 then TT{i} k=k-wi 下頁中之完整演算法可以找出正確的集合T 與T所對應的物品最大總價值P[n,m]

更完整的0/1背包演算法 Algorithm 0/1背包演算法 Input:背包的最大容量m，以及可能放入背包的n個物品的非負重量wi與價格pi Output: T與p，其中T為物品子集，T中物品總重小於m而且可以產生最大總價值p for w←0 to m do P[0, w]=0 for i←1 to n do for w←0 to m do if (wiw)  ((pi+P[i-1, w-wi])>P[i-1, w]) then P[i,w]= pi+P[i-1, w-wi] Q[i,w]=1 else P[i,w]=P[i-1, w] Q[i, w]=0 k=m T for in to 1 do if Q[i, k]=1 then T=T{i} k=k-wi return T, P[n,m] 更完整的0/1背包演算法

3.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等與空序列都是X的子序列 例: 序列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的最長共同子序列來解決。 一個生物的DNA中，可能會有某些不一定連續部份的物質突然消失，或突變，因而造成DNA序列的變化 腺嘌呤（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: 如何檢查一個序列是否為另一個序列的子序列?

最長共同子序列動態規劃演算法 建構表格 我們定義Xi = < x1,x2,...,xi > 及Yj = <y1,y2,...,yj>。 我們建構表格c[0..m,0..n]，令c [i, j]紀錄Xi 和Yj 的LCS的長度 則c[m, n]紀錄X = <x1,x2,...,xm>和Y = <y1,y2,...,yn>的LCS的長度

最長共同子序列動態規劃演算法 遞迴關係 - - + c [ i , j ] = c [ i 1 , j 1 ] 1 x =y - - x ¹ 如前頁所定義，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

最長共同子序列動態規劃演算法 由底而上的逐一將表格填完 i, j由小而大，或稱由底而上(bottom up)，根據上頁的遞迴關係，逐一計算c[i, j]的值，將表格填完。 c[i, j] j=0 1 2 … n i=0   0  m 解 答

最長共同子序列演算法 Algorithm 最長共同子序列演算法 Input: 兩個序列X = <x1,x2,...,xm>, Y = <y1,y2,...,yn> Input: X和Y的最長共同子序列長度 1. m  |X| //m記錄序列X的長度 2. n  |Y| //n記錄序列Y的長度 3. for i  1 to m do c[i, 0]  0 4. for j  1 to n do c[0, j]  0 本演算法參考以下書籍改寫: CORMEN, Thomas H., et al. Introduction to algorithms. Cambridge: MIT press, 2001.

最長共同子序列演算法(續) 我們同時建構陣列d[1..m, 1..n]，並使用d[i,j]記錄c[i,j]最大值的參考由來 5. for i  1 to m do 6. for j  1 to n do 7. if xi = yj then 8. c[i, j]  c[i-1, j-1]+1 9. d[i, j]  “” //對應i-1及 j-1 10. else if c[i–1, j]  c[i, j-1] then 11. c[i, j]  c[i-1, j] 12. d[i, j]  “” //對應i-1 13. else 14. c[i, j]  c[i, j-1] 15. d[i, j]  “” //對應 j-1 16. return c and d

最長共同子序列演算法 時間複雜度 行5的外層for迴圈一共有m次迭代 行6的內層for迴圈一共有n次迭代 行7-15的if敘述需要常數時間 因此總時間複雜度為O(mn) ，相對於暴力法的 O(2m)或 O(2n)，有非常大的改善。

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

最長共同子序列演算法 如何找出最長共同子序列 16. LCS //LCS初始值為空序列 17. im; jn 18. while |LCS| <c[m, n] do // |LCS| 表示LCS的長度 19. if d[i, j] = “” then 20. LCS xi || LCS // || 表示序列連結 21. i--; j--; 22. else if d[i, j] = “” then 23. i-- 24. else // d[i, j] = “” 25. j-- 26. return LCS, |LCS| (也就是c[m, n]) 行18-25while迴圈時間複雜度為O(m+n)，因為當i由m減為1時且/或j由n減為1時一定會產生正確的LCS

3.11 矩陣鏈乘積演算法

二個矩陣相乘所需的純量乘法數 假設 M 是一個xy的矩陣，N 是一個yz的矩陣， 則 MN需要xyz次的純量乘法計算。 例如: M = , N = a d b e c f 3x2 則MN = 1a+2b+3c 1d+2e+3f 4a+5b+6c 4d+5e+6f 2x2 1 2 3 4 5 6 2x3

矩陣相乘執行順序非常關鍵 假設M1是個5200的矩陣，M2是一個20010 的矩陣，M3是一個10100的矩陣。 520010+1010100=5000+10000= 15000次的純量乘法計算。 然而算出(M1(M2M3))卻需要20010100 + 5200100=200000+100000= 300000次的純量乘法計算。

矩陣鏈乘積問題 定義: 矩陣鏈乘積問題(matrix-chain product problem) 給定一個含n個矩陣的矩陣鏈乘積M1M2…Mn，其中矩陣Mi, 1in, 的維度為ei-1ei。找出一種M1M2…Mn的完全括號(fully parenthesized)方式，以便可以使用最少的純量乘法求出M1M2…Mn的乘積。 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.

完全括號矩陣鏈乘積 若一個矩陣鏈乘積為完全括號(fully parenthesized)，則其為單一矩陣或為兩個完全括號矩陣鏈乘積相乘並加括號。 例如: X、Y是完全括號矩陣鏈乘積，(XY)也是完全括號矩陣鏈乘積 又例如: ((XY)Z)與(X(YZ))都是完全括號矩陣鏈乘積 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.

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

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

矩陣鏈乘積演算法 建構表格 使用表格m[1..n, 1..n]，定義 m[i, j] = 計算Mi…Mj所需的最小純量相乘數，其中Mi的維度為ei-1  ei，1 i, j n。 目標為求得m[1, n] 除了表格m之外，矩陣鏈乘積演算法利用另一個輔助表格s[1..n, 1..n]來記錄矩陣鏈分割(split)的位置。s[i, j]記錄哪一個分割位置造就了m[i, j]的最小純量相乘數。 Step 1: The structure of an optimal parenthesization

矩陣鏈乘積演算法 遞迴關係 定義 m[i, j]= 計算Mi…Mj所需的最小相乘數，其中Mi維度為ei-1ei，1 i, j n。

矩陣鏈乘積演算法 由底而上的逐一將表格填完 因為邊界條件為i=j，因此我們根據11,22,…,nn, 12,23,…,(n-1)n, 13,24,(n-2)n, …, 1n的方式填表，也就是根據 j-i的差值d由0到n-1，或稱由底而上(bottom up)，根據上頁的遞迴關係，逐一計算m[i, j]的值，將表格填完。 d=n-1 d=… 因為ji，因此 表格中有一半 的格子不使用。 d=2 d=1 d=0(符合邊界條件的初始值)

矩陣鏈乘積演算法 Algorithm 矩陣鏈乘積演算法 Input: 矩陣鏈乘積M1M2…Mn 本演算法參考以下書籍改寫: CORMEN, Thomas H., et al. Introduction to algorithms. Cambridge: MIT press, 2001. Algorithm 矩陣鏈乘積演算法 Input: 矩陣鏈乘積M1M2…Mn Output: 計算矩陣鏈乘積M1M2…Mn所需最少的純量乘法數 1. for i  1 to n do 2. m[i, i]  0 3. for d  1 to n – 1 do 4. for i  1 to n – d do 5. j  i + d 6. m[i, j]   7. for k  i to j – 1 do 8. t  m[i, k] + m[k+1, j]+ ei-1ekej 9. if t < m[i, j] then 10. m[i, j]  t 11. s[i, j]  k 12. return m and s

矩陣鏈乘積演算法 時間複雜度 行3的外層for迴圈一共有O(n)次迭代 行4的中層for迴圈一共有O(n)次迭代 行8-11的敘述需要常數時間計算 因此總時間複雜度為O(n3)

矩陣鏈乘積演算法 印出最佳全完括號矩陣鏈乘積 Algorithm 印出完全括號矩陣鏈乘積(s, i, j) Input: 矩陣鏈乘積演算法輸出的表格s,整數i與j, ij Output: 將完全括號矩陣鏈乘積印出 if i=j then print “M” ||i else print “(“ 印出完全括號矩陣鏈(s, i, s[i,j]) 印出完全括號矩陣鏈(s, s[i,j]+1, j) print “)” 藉由呼叫印出完全括號矩陣鏈乘積(s, 1, n)就可以印出M1M2…Mn的完全括號方式。因為陣列s是矩陣鏈乘積演算法產生的，用以記錄產生最少純量乘法數的完全括號矩陣鏈乘積，因此呼叫印出完全括號矩陣鏈乘積(s, 1, n)印出的是M1M2…Mn的最佳完全括號方式。 本演算法參考以下書籍改寫: CORMEN, Thomas H., et al. Introduction to algorithms. Cambridge: MIT press, 2001.

3.12 Bellman-Ford 最短路徑演算法

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

Bellman-Ford最短路徑演算法介紹(續) Bellman-Ford最短路徑演算法採用動態規劃 策略解決問題，找出由源點s到其他全部節點 的最短路徑。 Bellman-Ford演算法一開始在第1次迭代先求 出所有屬於1-邊路徑(1-edge path)的最短路徑 ，並將其最短路徑距離儲存在陣列中。 所謂1-邊路徑，就是由源點s開始，只能經過 1個邊所造成的路徑。 所謂k-邊路徑，就是由源點s開始，只能經過 k個邊所造成的路徑。

Bellman-Ford最短路徑演算法介紹(續) 然後Bellman-Ford演算法基於儲存在陣列中 的1-邊最短路徑結果，在第2次迭代針對每個 邊(u, x)，由u往外調整到x的最短路徑距離， 可以得出所有屬於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]，及每個節點u最短路徑上的前節點(predecessor)p[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] p[x]← u for 每一個G的邊(u, x) do //檢查有無負循環(negative-weight cycle) if d[x] > d[u] + w[u][x] then exit //代表有負循環，無法產生正確結果 return d, p

Bellman-Ford最短路徑演算法時間複雜度 假設G一共有n個節點，m個邊(也就是|V|=n, |E|=m) 行2-6的外層for迴圈一共有O(n)次迭代 行3-6的內層for迴圈一共有O(m)次迭代 行4-6為內層if指令，針對每個邊(u, x)依據目前的d[u]值調整d[x]，其執行需要常數時間 行7-8的for迴圈在求出(n-1)邊路徑之後再針對每個邊(u, x)，檢查目前的d[u]值，一共有O(m)次迭代 因此總時間複雜度為O(n  m)= O(|V|  |E|)

Bellman-Ford最短路徑演算法 執行範例

3.13 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：一個加權有向圖(weighted digraph)G，其中節點編號為1,…,n，而 各邊的加權值以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 for k←1 to n do //針對每個編號由1至n的節點 for i←1 to n do //針對每個編號由1至n的節點 for j←1 to n do //針對每個編號由1至n的節點 if d[i][j] > d[i][k]+d[k][j] then d[i][j]←d[i][k]+d[k][j] p[i][j]←p[k][j] return d, p

Floyd-Warshall演算法討論 前節點(predecessor)陣列p紀錄每個節點在最短路徑上的前節點。在進行p[i][j]初始化時，若i=j或(i,j)∉E則p[i][j]初始化為NIL()，否則(也就(i,j)E)p[i][j]初始化為i。 演算法執行完畢之後，則可藉由前節點陣列p來找出由任意節點到其他任意節點最短路徑上經過的所有節點。

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) 行2的外層for迴圈一共有n次迭代 行3的中層for迴圈一共有n次迭代 行4的內層for迴圈一共有n次迭代 行5-7迴圈內if敘述的執行為常數時間 因此總時間複雜度為O(n3)=O(|V|3)

The End