貪婪演算法 3 2019/5/6 演算法 ＿ 第三章.

Presentation on theme: "貪婪演算法 3 2019/5/6 演算法 ＿ 第三章."— Presentation transcript:

1 貪婪演算法 3 2019/5/6 演算法 ＿ 第三章

2 最佳化問題 每一個最佳化問題都包含一組限制條件以及一個最佳化函數 滿足這些限制條件的解稱為可行解或候選解
其中使得最佳化函數得到最佳值的可行解稱為最佳解 2019/5/6 演算法 ＿ 第三章

3 找錢幣問題 假設有一個小女孩要買14塊錢的糖果，她給了店員一張100塊錢的鈔票
假設收銀機裡提供足夠的50塊、20塊、10塊、5塊、1塊的硬幣，而且店員想用最少數量的硬幣來找錢 店員該找給小女孩哪些硬幣各多少個？ 2019/5/6 演算法 ＿ 第三章

4 找錢幣問題 限制條件是只能使用50塊、20塊、10塊、5塊、1塊共五種硬幣 利用這五種硬幣的組合必須產生總共10014 = 86塊
可行解包括：{20, 20, 20, 20, 5, 1}, {50, 10, 10, 10, 1, 1, 1, 1, 1, 1}, {50, 20, 10, 5, 1}, 。 硬幣數目最少的組合，{50,20,10,5,1} 2019/5/6 演算法 ＿ 第三章

5 找錢幣問題 店員必須做出好幾次的決定，每次的決定都加進一個硬幣
加進一個硬幣的貪婪原則是：每一次所加進的硬幣金額越大越好，但是不能讓總金額超過該找錢的金額 如果每一次我們都選擇最佳決定，而這些決定也將導致最後的最佳解，那麼這個最佳化問題就可以用貪婪法來解 2019/5/6 演算法 ＿ 第三章

6 最短路徑 2019/5/6 演算法 ＿ 第三章

7 最小花費生成樹 給定一個加權的無向圖，我們定義它的生成樹之花費是在該生成樹上所有邊的花費（加權值）總和
最小花費生成樹是所有生成樹中花費最少的一棵。 2019/5/6 演算法 ＿ 第三章

8 Kruskal 演算法 最壞情況複雜度是 O(e log e) 2019/5/6 演算法 ＿ 第三章

9 Kruskal 演算法 2019/5/6 演算法 ＿ 第三章

10 Kruskal 演算法 2019/5/6 演算法 ＿ 第三章

11 Kruskal 演算法 2019/5/6 演算法 ＿ 第三章

12 Kruskal 演算法 2019/5/6 演算法 ＿ 第三章

13 Kruskal 演算法 2019/5/6 演算法 ＿ 第三章

14 Kruskal 演算法 2019/5/6 演算法 ＿ 第三章

15 Kruskal 演算法 2019/5/6 演算法 ＿ 第三章

16 Kruskal 演算法 2019/5/6 演算法 ＿ 第三章

17 Prim 演算法 最壞情況複雜度是 O(n2) 2019/5/6 演算法 ＿ 第三章

18 Prim 演算法 2019/5/6 演算法 ＿ 第三章

19 Prim 演算法 2019/5/6 演算法 ＿ 第三章

20 Prim 演算法 2019/5/6 演算法 ＿ 第三章

21 Prim 演算法 2019/5/6 演算法 ＿ 第三章

22 Prim 演算法 2019/5/6 演算法 ＿ 第三章

23 Prim 演算法 2019/5/6 演算法 ＿ 第三章

24 Prim 演算法 2019/5/6 演算法 ＿ 第三章

25 Sollin 演算法 在每一個階段中，我們替樹林裡的每一棵樹選出一個邊 這個邊的花費最小，而且恰好有一個頂點是在該樹中
當圖中有好幾個花費相同的邊時，兩棵樹可能會選出兩個不同的邊來彼此相連 這兩個花費相同的邊只有一個需要留下來 2019/5/6 演算法 ＿ 第三章

26 Sollin 演算法 2019/5/6 演算法 ＿ 第三章

27 Sollin 演算法 2019/5/6 演算法 ＿ 第三章

28 Sollin 演算法 2019/5/6 演算法 ＿ 第三章

29 單一起點之最短路徑 2019/5/6 演算法 ＿ 第三章

30 單一起點之最短路徑 令 S 表示已經找到最短路徑的頂點所成的集合
對於一個不在 S 內的頂點 w，令 dist[w] 為一條從 v 開始，只經過在 S 裡的頂點，再到終點 w 的最短路徑之長度 2019/5/6 演算法 ＿ 第三章

31 單一起點之最短路徑 如果路徑是按照長度的遞增順序來產生，那麼我們觀察到：
如果下一條找到的最短路徑是到頂點 u，那麼這條路徑必然是從 v 開始、以 u 為終點、而且只路過在 S 內的頂點 下一條所產生的路徑之終點 u 必須是所有不在 S 內的頂點中 dist 最小的一個 如果 dist[w] 變小的話，那麼這個改變是由於 v 到 u 再到 w 的這條路徑的緣故，其中這條路徑的長度是dist[u] + length(<u, w>) 2019/5/6 演算法 ＿ 第三章

32 單一起點之最短路徑 2019/5/6 演算法 ＿ 第三章

33 If true, dist[w] = dist[u] + length[u,w].
length[i, j] = the edge cost between node i and j, dist[i] = the sum of cost between start node v and node i; i.e. dist[i] = length[v, a1] + … + length[am, i] 1. Using the greedy method, select an unprocessed node u. Set the node u processed. 2. For each unprocessed node w, test whether dist[w] > dist[u] + length[u,w]. If true, dist[w] = dist[u] + length[u,w]. 3. Goto step 1 if any unprocessed node exists. 2019/5/6 演算法 ＿ 第三章

34 單一起點之最短路徑 時間複雜度是 O(n2) 2019/5/6 演算法 ＿ 第三章

35 單一起點之最短路徑 2019/5/6 演算法 ＿ 第三章

36 凸面體 2019/5/6 演算法 ＿ 第三章

37 凸面體 給定平面上的點，我們所將求出凸面體端點 這些端點依序連起來構成一個把所有的點都包圍在內的最小凸多邊形－凸面體 2019/5/6
演算法 ＿ 第三章

38 凸面體 2019/5/6 演算法 ＿ 第三章

39 凸面體 決定各點的處理先後順序 2019/5/6 演算法 ＿ 第三章

40 凸面體 2019/5/6 演算法 ＿ 第三章

41 凸面體 2019/5/6 演算法 ＿ 第三章

42 凸面體 2019/5/6 演算法 ＿ 第三章

43 凸面體 2019/5/6 演算法 ＿ 第三章

44 凸面體 2019/5/6 演算法 ＿ 第三章

45 凸面體 2019/5/6 演算法 ＿ 第三章

46 凸面體 2019/5/6 演算法 ＿ 第三章

47 凸面體 2019/5/6 演算法 ＿ 第三章

48 凸面體 2019/5/6 演算法 ＿ 第三章

49 凸面體 2019/5/6 演算法 ＿ 第三章

50 凸面體 2019/5/6 演算法 ＿ 第三章

51 凸面體 2019/5/6 演算法 ＿ 第三章

52 凸面體 2019/5/6 演算法 ＿ 第三章

53 凸面體 複雜度為 O(n log n) 2019/5/6 演算法 ＿ 第三章

54 霍夫曼編碼 多序列的合併問題 2019/5/6 演算法 ＿ 第三章

55 霍夫曼編碼 加權外部路徑長度 對於圖 3.12 中的兩棵樹，它們的加權外部路徑長度分別是：
73 + 93 + 272 + 351 = 137 以及 72 + 92 + 272 + 352 = 156 2019/5/6 演算法 ＿ 第三章

56 霍夫曼編碼 圖3.12的兩棵合併樹分別需要 (161) + (431) + (781) = 1373 = 134 以及
(161) + (621) + (781) = 1563 = 153 次的比較運算 2019/5/6 演算法 ＿ 第三章

57 霍夫曼編碼 2019/5/6 演算法 ＿ 第三章

58 霍夫曼編碼 2019/5/6 演算法 ＿ 第三章

59 霍夫曼編碼 演算法的時間複雜度為 O(n) + O(n log n) = O(n log n) 2019/5/6 演算法 ＿ 第三章

60 打包問題 給定的 n 項物品，每一項物品 I 有其重量 wi 以及價值 pi。
這個問題要求我們，在總重量小於等於 C 的前提下，選出來要搬走的物品之總價值要最高 2019/5/6 演算法 ＿ 第三章

61 打包問題 這個問題可以公式化如下： 最大化 前提是必須滿足下面的限制條件 0  xi  1, 1  i  n 2019/5/6
演算法 ＿ 第三章

62 打包問題 我們必須決定出每一個 xi 的值 xi = 1 代表物品 i 整個要搬 xi = 0 代表物品 i 整個不搬
2019/5/6 演算法 ＿ 第三章

63 打包問題 2019/5/6 演算法 ＿ 第三章

64 打包問題 假設 w = [18, 15, 10], p = [25, 24, 15], C = 20 價值密度是 d = [1.32, 1.6, 1.5] 價值密度最高的是物品 2，它的重量是w[2] = 15  C。因此，物品2 整個放入背包 我們剩下能負擔的重量是 Cw[2] = 2015 = 5，打包物品 2 所獲得的利益是 24 在剩下的物品中價值密度最高的是物品 3，它的重量是10，大於目前的 C = 5。我們因此只打包物品 3 的 5/10 = 1/2，即 x[3] = ½ 打包部分物品 2 所獲得的利益是 151/2 = 7.5 因此，我們最後求出的最佳解是：x[1] = 0、x[2] = 1、x[3] = 1/2，總獲利為 = 31.5 2019/5/6 演算法 ＿ 第三章

65 打包問題 「1.5將物品根據d[i]的大小由大到小排序過；」 時間複雜度是 O(n log n) 2019/5/6 演算法 ＿ 第三章