投影片 1

Size: px

Start display at page:

Download "投影片 1"

音铜扶
5 years ago
Views:

1 Chapter 17 資料結構與演算法 1

2 學習目標第 17 章資料結構與演算法認識資料結構與演算法的定義熟悉佇列與堆疊的原理與應用熟悉二元樹的原理與應用瞭解常用排序與搜尋方法的原理與應用瞭解演算法的分析方法瞭解基本演算法設計策略 2

3 大綱 17-1 虛擬碼 17-2 基礎資料結構 17- 基礎演算法 17-4 演算法分析與策略

4 CH17 資料結構與演算法資料結構是指資料在電腦內的表示方式和存取方法演算法就是電腦處理資料的詳細流程資料結構與演算法要相互配合才能有效率的處理資料每個資料結構都有其對應的存取使用方法, 演算法設計必須搭配資料結構設計才能達到最佳表現

5 17-1 虛擬碼流程圖 (Flow Chart): 用來描繪虛擬碼動作流程圖是由一些圖形所組成, 主要的圖形如下圖所示動作圖形運算 / 處理 / 轉換決策判斷條件是否邏輯流向

6 17-1 虛擬碼以下介紹幾個主要的虛擬碼 (pseudo code) 指令 READ READ 讀入資料儲存於某變數其語法格式如下 : READ 變數名稱 PRINT PRINT 指令用來輸出資料語法格式如下 : PRINT 變數名稱或訊息

7 17-1 虛擬碼 IF-THEN IF-THEN 指令在選擇或決策使用語法格式為 : IF 條件式 THEN 指令敘述 ENDIF 條件式是否指令敘述

8 17-1 虛擬碼範例 : 虛擬碼流程圖 IF A>0 THEN B=C+D C=D+F ENDIF E=F+G A > 0 E=F+G 是 B = C + D C=D+F 否 8

9 17-1 虛擬碼 IF-THEN-ELSE 此指令在選擇或決策時使用語法格式為 : IF 條件式 THEN 指令敘述 1 ELSE 指令敘述 2 ENDIF 條件式成立是否指令敘述 1 指令敘述 2

10 17-1 虛擬碼範例 : 虛擬碼流程圖 IF A>0 THEN A=A+B ELSE B=C+D A > 0 是 A = A + B 否 B= C + D ENDIF C=C+D C = C+ D 10

11 17-1 虛擬碼 FOR-LOOP 此指令在需重複執行指令時使用語法格式為 : FOR 控制變數 = 初值 TO 終值 SETP 累加值指令敘述 END FOR

12 17-1 虛擬碼 FOR-LOOP 累加值為正值或 0 時 : 累加值為負值或 0 時 : 控制變數 = 初值控制變數 = 初值控制變數終值否控制變數終值否是是指令敘述指令敘述控制變數 = 控制變數 + 累加值控制變數 = 控制變數 + 累加值

13 17-1 虛擬碼例如要重複印出五個 A, 利用 FOR-LOOP 寫出的虛擬碼如下 : 虛擬碼流程圖 FOR I=1 TO 5 STEP 1 END FOR PRINT A I=1 I 5 是 PRINT A 否 I= I+1

14 17-1 虛擬碼 WHILE-LOOP 此指令在需重複執行指令時使用語法格式為 : WHILE 條件運算式指令敘述 END WHILE 可以把前面 FOR- LOOP 的例子改為 WHILE-LOOP: I=1 WHILE I<=5 PRINT A I=I+1 END WHILE WHILE 條件運算式成立指令敘述不成立

15 17-1 虛擬碼 EXIT EXIT 指令表示停止執行虛擬碼語法格式為 : EXIT EXIT FOR EXIT FOR 指令將停止執行目前的 FOR-LOOP, 並繼續執行目前 FOR-LOOP 後的第一個指令語法格式為 : EXIT FOR

16 17-1 虛擬碼 EXIT WHILE EXIT WHILE 指令表示停止執行目前的 WHILE-LOOP, 並繼續執行目前 WHILE-LOOP 後的第一個指令語法格式為 : EXIT WHILE

17 17-1 虛擬碼本章演算法之格式 : 格式中的演算法描述可以虛擬碼敘述, 或以一步一步的步驟式方式敘述之本章將演算法描述格式如下 : 演算法 : 名稱輸入 : 輸入資料輸出 : 輸出資料 BEGIN 演算法描述 END

18 17-2 基礎資料結構陣列 (Array): 是最常見的資料結構之一當一個資料需儲存到主記憶體時, 可以指定一個變數來儲存, 但若要同時處理 100 個同樣類型資料時, 指定 100 個不同變數名稱, 在使用上就相當不便了, 此時就能利用陣列來處理陣列是記憶體的變數名稱, 它是一群具有相同性質的資料型態之集合, 而各個元素以不同的註標 (Index) 值來區分

19 17-2 基礎資料結構一維陣列 : 欲儲存 10 個人的平均成績 79,80,55,75,99,65,70,68,90,74, 可以使用名稱為 SCORE 的陣列, 而各元素的變數名稱分別為 SCORE[1],SCORE[2],SCORE[],...,SCORE[10], 其陣列的表示如下 : SCORE[1] SCORE[2] SCORE[] SCORE[4] SCORE[5] SCORE[6] SCORE[7] SCORE[8] SCORE[9] SCORE[10]

20 17-2 基礎資料結構上述以一個註標來存取元素的陣列稱為一維 (One Dimension) 陣列, 以 n 個註標來存取元素的陣列稱為 n 維陣列第一個學生第二個學生第三個學生第四個學生第一次考試第二次考試第三次考試第四次考試第五次考試第六次考試第七次考試第八次考試第九次考試第十次考試

21 佇列與堆疊當我們買票看電影時, 大家依據到達的先後次序排隊買票, 先來的先買票進場 ; 但是當我們清洗餐盤時, 常是把洗完的盤子直接就放在之前洗好的盤子的最上面, 等到要取用盤子時會先拿最上面的盤子, 反而是後放上去的盤子先使用前者排隊買票是先進先出 (First In First Out,FIFO) 的處理觀念, 而後者使用盤子是後進先出 (Last In First Out,LIFO) 的處理觀念接下來介紹的佇列和堆疊分別應用了 FIFO 和 LIFO 的處理觀念 21

22 佇列與堆疊佇列 (Queue) 是一個有順序的資料列, 其資料列有兩端, 分別稱為頭端 (Front) 和尾端 (Rear) ( 如圖 17.4) 資料可加入 (Add) 佇列中或從佇列中刪除 (Delete), 但是加入的資料只能加在資料列的尾端, 而刪除資料卻是除去資料列頭端的資料頭端尾端 A B C D E F 圖

23 佇列與堆疊假設 Q 是一佇列, 以 ADD (Q, a) 表示將 a 加入佇列 Q 中, 以 DELETE (Q) 表示從佇列 Q 刪除資料若佇列 Q 內有, 9, 7, 8, 四個資料, 其資料列的頭端是, 尾端是 8 ( 見圖 17.5 (a)) 頭端尾端頭端尾端頭端尾端 Q ADD(Q, 5) ADD(Q, 2) (a) (b) (c) DELETE(Q) 頭端尾端頭端尾端 (e) DELETE(Q) (d)

24 佇列與堆疊如果將 5 加入 Q 中, 則 5 將加在尾端 8 之後, 而使 5 成為新的尾端 ( 圖 17.5 (b)) 頭端尾端頭端尾端頭端尾端 Q ADD(Q, 5) ADD(Q, 2) (a) (b) (c) DELETE(Q) 頭端尾端頭端尾端 (e) DELETE(Q) (d) 24

25 佇列與堆疊再加入 2, 則佇列 Q 的資料列成為, 9, 7, 8, 5, 2 ( 圖 17.5 (c)) 頭端尾端頭端尾端頭端尾端 Q ADD(Q, 5) ADD(Q, 2) (a) (b) (c) DELETE(Q) 頭端尾端頭端尾端 (e) DELETE(Q) (d) 25

26 佇列與堆疊若此時從佇列 Q 刪除資料, 將會刪除其頭端資料, 而使 9 成為新的頭端 ( 圖 17.5 (d)) 頭端尾端頭端尾端頭端尾端 Q ADD(Q, 5) ADD(Q, 2) (a) (b) (c) DELETE(Q) 頭端尾端頭端尾端 (e) DELETE(Q) (d) 26

27 佇列與堆疊再刪除一次, 則資料列成為 7, 8, 5, 2 ( 圖 17.5 (e)) 頭端尾端頭端尾端頭端尾端 Q ADD(Q, 5) ADD(Q, 2) (a) (b) (c) DELETE(Q) 頭端尾端頭端尾端 (e) DELETE(Q) (d) 27

28 佇列與堆疊下面分別是 ADD 和 DEL 兩個演算法, 其中 ADD 將 ITEM 加入最多有 N 個資料的佇列 Q 中, 而 DEL 是從最多有 N 個資料的佇列 Q 中刪除一個資料, 並以 ITEM 紀錄此刪除的資料此處以一維陣列來儲存佇列 Q, 並以 FRONT 及 REAR 分別表示頭端及尾端的位置 28

29 佇列與堆疊演算法 :ADD (ITEM, Q[], N, REAR) 輸入 :ITEM, Q[], N, REAR 輸出 :Q[], REAR 1 BEGIN 2 IF REAR = N THEN PRINT QUEUE IS FULL 4 EXIT 5 END IF 6 REAR=REAR+1 7 Q[REAR] = ITEM 8 END 29

30 佇列與堆疊演算法 :DEL (ITEM, Q[], FRONT, REAR) 輸入 :Q[], FRONT, REAR 輸出 :ITEM, Q[], FRONT 1 BEGIN 2 IF FRONT = REAR THEN PRINT QUEUE IS EMPTY 4 EXIT 5 END IF 6 FRONT = FRONT ITEM = Q[FRONT] 8 END 0

31 佇列與堆疊佇列常使用於作業系統中, 如工作佇列 (Job Queue) 列印佇列 (Printer Queue) 等 1

32 佇列與堆疊堆疊 (Stack) 也是一個有順序的資料列, 其資料列兩端的一端稱為頂端 (Top) ( 如圖 17.6) 資料一樣可以加入 (Push) 堆疊中或從堆疊中刪除 (Pop), 可是加入的資料只能放於資料列的頂端, 而刪除資料也是目前資料列頂端的資料 C B A 堆疊圖 17.6 頂端 2

33 佇列與堆疊假設 S 是一堆疊, 以 PUSH (S, a) 表示將 a 加入堆疊 S 中, 以 POP (S) 表示從堆疊 S 刪除資料若堆疊 S 內有 1, 5, 三個資料, 其資料列的頂端是 ( 見圖 17.7 (a)) 5 1 頂端頂端頂端 S PUSH(S,9) S PUSH(S, 2) S (a) (b) (c) POP(S) 頂端 9 頂端 5 1 POP(S) 5 1 S S (e) (d)

34 佇列與堆疊如果將 9 加入 S 中, 則 9 將加在頂端之上, 使 9 成為新的頂端 ( 圖 17.7 (b)) 5 1 頂端頂端頂端 S PUSH(S,9) S PUSH(S, 2) S (a) (b) (c) POP(S) 頂端 9 頂端 5 1 POP(S) 5 1 S S (e) (d) 4

35 佇列與堆疊再加入 2, 則堆疊 S 的資料列成為 1, 5,, 9, 2 ( 圖 17.7 (c)), 其中 2 為頂端 5 1 頂端頂端頂端 S PUSH(S,9) S PUSH(S, 2) S (a) (b) (c) POP(S) 頂端 9 頂端 5 1 POP(S) 5 1 S S (e) (d) 5

36 佇列與堆疊若此時從堆疊 S 刪除資料, 將會刪除其頂端資料 2, 而使 9 成為新的頂端 ( 圖 17.7 (d)) 5 1 頂端頂端頂端 S PUSH(S,9) S PUSH(S, 2) S (a) (b) (c) POP(S) 頂端 9 頂端 5 1 POP(S) 5 1 S S (e) (d) 6

37 佇列與堆疊再刪除一次, 則資料列成為 1, 5, ( 圖 17.7 (e)), 其中為頂端 5 1 頂端頂端頂端 S PUSH(S,9) S PUSH(S, 2) S (a) (b) (c) POP(S) 頂端 9 頂端 5 1 POP(S) 5 1 S S (e) (d) 7

38 佇列與堆疊下面分別有 PUSH 和 POP 的演算法, 其中 PUSH 將 ITEM 加入最多有 N 個資料的堆疊 S 中, 而 POP 是從最多有 N 個資料的堆疊 S 中刪除一個資料, 並以 ITEM 紀錄此刪除的資料此處以一維陣列來儲存堆疊 S 8

39 佇列與堆疊演算法 : PUSH ( S[], ITEM, N, TOP) 輸入 :S[], ITEM, N, TOP 輸出 :S[], TOP 1 BEGIN 2 IF TOP >= N THEN PRINT "STACK IS FULL" 4 EXIT 5 END IF 6 TOP = TOP S[TOP] = ITEM 8 END 9

40 佇列與堆疊演算法 : POP (ITEM, S[], TOP) 輸入 :S[], TOP 輸出 :ITEM, S[], TOP 1 BEGIN 2 IF TOP <= 0 THEN PRINT "STACK IS EMPTY" 4 EXIT 5 END IF 6 ITEM = S[TOP] 7 TOP = TOP 1 8 END 40

41 佇列與堆疊堆疊的應用很多, 如程式執行計算數學式等以下以計算數學式為例說明堆疊的應用假設我們要計算數學式 A + B*C 的值, 依四則運算的規則, 要先計算 B*C 的值後再加上 A 若用電腦計算 A + B*C, 不能單單地只從左至右計算, 需先將此算式轉換成後序算式 (Postfix Expression), 亦即將運算符號放到其運算對象的後方例如 A+B*C 的後序算式為 ABC*+ 41

42 佇列與堆疊若給了一個後序算式, 我們就能利用堆疊算出其值從左至右輸入後序算式, 當輸入的不是運算符號時, 就將其加入堆疊中 ; 若輸入的是運算符號, 就連續從堆疊中刪除兩個資料, 並以此二資料作為這運算符號的運算對象計算之, 然後將計算結果再加入堆疊中如此這般直到算式輸入完畢, 最後位於堆疊頂端的資料就是此算式的值 42

43 佇列與堆疊若現在要計算後序算式 52*+ 的值, 首先設定好一空堆疊 ( 圖 17.8 (a)) 當輸入 `' `5' `2' 時, 因為都不是運算符號, 所以都被加入堆疊中 ( 圖 17.8 (b), (c), (d)) 5 頂端 5 S 頂端 S S (a) (b) (c) 頂端 2 1 S (f) 頂端 + 10 S 4 (e) 頂端 * 2 5 S (d) 頂端

44 佇列與堆疊當輸入 `*' 時, 從堆疊刪除 `2' 和 `5' 兩個資料, 然後作 `5*2' 的計算, 得結果 10, 再將 10 加入堆疊中 ( 圖 17.8 (e)) 5 頂端 5 S 頂端 S S (a) (b) (c) 頂端 2 1 S (f) 頂端 + 10 S (e) 頂端 44 * 2 5 S (d) 頂端

45 佇列與堆疊最後輸入 `+' 時, 從堆疊刪除 `10' 和 `' 兩個資料, 然後作 `+10' 的計算, 得結果 1, 再將 1 加入堆疊中 ( 圖 17.8 (f)) 所以 52*+ 的值是位於堆疊頂端的 1 5 頂端 5 S 頂端 S S (a) (b) (c) 頂端 2 1 S (f) 頂端 + 10 S (e) 45 頂端 * 2 5 S (d) 頂端

46 樹與二元樹下圖是一張具有樹狀結構的家譜李一是大家的共同祖先, 其後有李二李三和李四, 李二之後有李五, 李三之後有李六李七和李八, 李四之後有李九, 而李七之後有李十整張圖就像是以李一為樹根向外生長的一棵樹 46

47 樹與二元樹樹 (Tree) 是一群有限個但至少一個節點 (Node) 所成的集合, 其中某個節點被指定為樹根 (Root) 除了樹根以外的節點可分為 T 1,..., T n 等 n 個不相交的集合 (n 0), 而且每個集合也是一棵樹 T 1,..., T n 稱為樹根的子樹 (Subtree) 若節點 N 沒有子樹, 則稱節點 N 為樹葉 (Leaf) 節點 N 的子樹的樹根稱為節點 N 的孩子 (Child), 而 N 稱為其孩子的父母 (Parent) 47

48 樹與二元樹以右圖為例 : 節點有李一... 李十, 樹根是李一 T1, T 2, T 是李一的三棵子樹, 其樹根分別為李二李三和李四李五李六李十李八和李九都是樹葉李一的孩子有李二李三和李四, 李二李三和李四的父母都是李一 48

49 樹與二元樹二元樹 (Binary Tree): 是每個節點至多兩個孩子的樹 ( 如下圖 ) 我們稱節點左邊的孩子為左孩子, 右邊的為右孩子 49

50 樹與二元樹用右圖的 LCHILD RCHILD 和 DATA 三個欄位表示節點其中 LCHILD 和 RCHILD 分別是節點的左孩子和右孩子,DATA 是原來的節點資料 50

51 樹與二元樹則可將圖 : 表示改成 51

52 樹與二元樹圖 17.1 是用所謂的鏈結串列 (Linked List) 來表示二元樹鏈結串列也可以用陣列表示宣告 Data Lchild 和 Rchild 三個陣列, 先將節點資料存入陣列 Data 中, 然後一一將節點的左孩子及右孩子在位於陣列 Data 的註標值分別填入到陣列 Lchild 和 Rchild 中圖 17.1 的陣列表示方式如圖所示 52

53 樹與二元樹追蹤 (Traversal) 樹上的節點是對樹狀結構相當重要的運算追蹤樹上的節點, 就是拜訪每個節點恰好一次, 而其追蹤的結果就是拜訪節點的順序追蹤方式可分 : 中序追蹤後序追蹤前序追蹤以下將介紹二元樹的各種追蹤方式 5

54 樹與二元樹中序追蹤 (Inorder Traversal): 若樹只有一個節點 a, 定義此樹之中序追蹤為 a 對二元樹的中序追蹤是先以中序追蹤拜訪樹根的左子樹, 再拜訪樹根, 然後以中序追蹤拜訪樹根的右子樹各子樹又依此定義遞迴 (Recursive) 追蹤下去 54

55 樹與二元樹以右圖的二元樹為例樹根 `+' 的左子樹的中序追蹤為 A; 因為節點 `*' 的左右子樹的中序追蹤分別為 B 和 C, 所以樹根 `+' 的右子樹的中序追蹤為 B*C 最後得知中序追蹤為 : A + B * C 55

56 樹與二元樹以右圖的二元樹為例 : 以拜訪順序 : 左中右追蹤此樹可知其中序追蹤是 DBEHAFCG 56

57 樹與二元樹前序追蹤 (Preorder Traversal): 若樹只有一個節點 a, 定義其前序追蹤為 a 對二元樹的前序追蹤是先拜訪樹根, 再以前序追蹤拜訪樹根的左子樹, 然後以前序追蹤拜訪樹根的右子樹各子樹又依此定義遞迴的追蹤下去 57

58 樹與二元樹以右圖為例 : 以拜訪順序 : 中左右追蹤此樹可得前序追蹤為 : ABDEHCFG 58

59 樹與二元樹以右圖為例 : 以拜訪順序 : 中左右追蹤此樹可得前序追蹤為 : +A*BC 59

60 樹與二元樹後序追蹤 (Postorder Traversal): 若樹只有一個節點 a, 定義其後序追蹤為 a 對二元樹的後序追蹤是先以後序追蹤拜訪樹根的左子樹, 再以後序追蹤拜訪樹根的右子樹, 然後拜訪樹根各子樹又依此定義遞迴的追蹤下去 60

61 樹與二元樹以右圖為例 : 以拜訪順序 : 左右中追蹤此樹可得前序追蹤為 : DHEBFGCA 61

62 樹與二元樹以右圖為例 : 以拜訪順序 : 左右中追蹤此樹可得前序追蹤為 : ABC*+ 62

63 樹與二元樹二元樹還能用來表示廣泛使用的 Huffman 碼之解碼樹 (Decode Tree) 以下圖為例 : 樹根 a 0 1 b 1 c d 6

64 樹與二元樹下圖是 a b c d 四個字元的解碼樹以 0 代表左分支, 以 1 代表右分支, 從樹根沿著分支走到各節點的路徑可分別記為 : a:000 b:001 0 樹根 1 d c: d:1 c 以此路徑當作編碼, 當要傳送資料時, 依此編碼方式轉換資料, 而接收端在收到後利用此圖解碼之, 可還原成原始資料 0 a 1 b 64

65 樹與二元樹如何找出解碼樹 : 假設字母 a b c d 出現的機率分別為 0.1, 0.2, 0., 0.4 首先產生 a b c d 四個樹葉節點, 設定其加權 (Weight) 分別為 0.1, 0.2, 0., 0.4, 並設集合 L = {a, b, c, d} ( 如下圖 ) L = {a, b, c, d} a b c d (a) 65

66 樹與二元樹其後的每一步驟如右圖 (a)~ (d) 產生一新的節點並設定其加權為 L 中前兩個加權最低的節點之加權和令新節點為此二節點的父母然後將此二節點從 L 中刪除, 將新的節點加入 L 如此重複直到 L 只剩一加權為 1.0 的節點最後指定 L 中的節點為樹根這樣就完成了 a b c d 的解碼樹 ( 如圖 (d)) L = {a, b, c, d} L = {ab, c, d} L = {abc, d} L = {abcd} 66 a b c d (a) ab 0. c d a b (b) abc 0.6 d ab c 0.4 a b (c) 1.0 abcd 0 1 abc 0.6 d 0 1 ab c 0 1 a b

67 17- 基礎演算法本節將介紹以下兩個主題 : 排序搜尋 67

68 17--1 排序排序問題 (Sorting Problem) 是將資料依據其大小 " 由小至大或由大至小排好, 例如將考卷依分數從高至低排好以下將介紹四個排序法 1. 插入排序法 2. 氣泡排序法. 謝耳排序法 4. 兩兩合併排序法 68

69 插入排序法插入排序法 (Insertion Sort) 利用下述技巧將資料排序好假設是一群由左至右依小至大順序排序好的整數資料若 15 要在維持排序順序之條件下加入此群資料內, 可以將 15 直接插入 9 和 16 之間如此和 26 三個資料就要向右移一個位置, 使得 9 之後空出一個位置讓 15 填入, 最後得到的排序結果 ( 如右圖 ) 69

70 插入排序法如右圖將五個整數資料依序放入陣列 D 中一開始設定 I = 2,N = 5 將 D[I] 依排序順序插入 D[1] 至 D[I 1] 的資料群中, 完畢後將 I 加 1 重複上述動作, 直到 I >N 70

71 插入排序法下圖是一個插入排序演算法程式的 2~4 行讀取資料放於陣列 D 內,5~15 行的迴圈 I 是排序程式,16~18 行是輸出排序好的資料迴圈 I 從 2 至 N 遞增, 內有一從 I 1 至 1 遞減的迴圈 J 迴圈 I 的目的是把 D[I] 逐一插入前 I 1 個資料內, 利用迴圈 J 自 D[I 1] 開始向左反方向找出 D[I] 應插入的位置演算法 :InsertionSort (D[], N) 輸入 :D[], N 輸出 :D[] 1 BEGIN 2 FOR I=1 TO N STEP 1 READ D[I] 4 END FOR 5 FOR I=2 TO N STEP 1 6 K=D[I] 7 FOR J=I-1 TO 1 STEP -1 8 IF K >= D[J] THEN 10 ELSE 11 D[J+1]=D[J] 12 END IF 1 END FOR 14 D[J+1]=K 15 END FOR 16 FOR I=1 TO N STEP 1 17 PRINT D[I] 18 END FOR 19 END 9 EXIT FOR

72 氣泡排序法氣泡排序法 (Bubble Sort) 是利用相鄰資料兩兩相比而完成資料的排序如果給了 N 個資料, 其排序過程分為 N 1 回合, 第 I 回合將第 I 大的資料像氣泡般的浮現 " 至其排序的位置如下圖將五個整數資料依序放入陣列 D 中

73 氣泡排序法用氣泡排序法將這五個資料由小到大排序好首先要把最大者從左向右推到到 D[5] 內從 D[1] 開始, 讓兩個相鄰的資料相比, 若左方的資料比右方的大, 就將資料交換, 也就是讓較大者放到右方, 而較小者放到左方先比較 D[1] 與 D[2], 因為 D[1]<D[2], 所以資料不交換再比較 D[2] 與 D[], 因為 D[2]>D[], 所以交換 D[2] 和 D[] 的資料如此繼續向右比較下去最後在 D[5] 內的 49 就是這五個資料的最大者 D: 不交換交換不交換不交換不

74 氣泡排序法找出最大數後, 然後就要找出次大數並放於 D[4] 內同樣的, 從 D[1] 開始, 讓兩個相鄰的資料相比, 把較大者放到右方, 而較小者放到左方最後在 D[4] 內的 8 就是這五個資料的次大者 D: 交換交換交換

75 氣泡排序法右圖是浮現第三大數的過程相同的, 利用前述的方法可找出第三大數並放於 D[] 最後將 0 放於 D[] 內 D: 不交換交換不交換不

76 氣泡排序法最後就是找出第四大數並放於 D[2] 內之後陣列 D 的內容為 , 是由小到大的順序 D: 交換不

77 氣泡排序法下圖是一個氣泡排序演算法 5~18 行的迴圈 J 用 7~14 行的迴圈 I 比較 D[I] 與 D[I +1] 相鄰資料, 以使得第 N + 1 J 大數放於 D[J ] 中 9~11 行是交換 D[I] 和 D[I + 1] 的內容 FLAG 變數用來表示迴圈 I 內是否有交換資料, 若無資料交換, 代表資料都已經排序好了, 可以停止排序演算法 :BubbleSort(D[],N) 輸入 :D[], N 輸出 :D[] 1 BEGIIN 2 FOR I=1 TO N STEP 1 READ D[I] 4 END FOR 5 FOR J=N TO 2 STEP 1 6 FLAG=0 7 FOR I=1 TO J-1 STEP 1 8 IF D[I] > D[I+1] THEN 9 TEMP=D[I] 10 D[I]=D[I+1] 11 D[I+1]=TEMP 12 FLAG=1 1 END IF 14 END FOR 15 IF FLAG=0 THEN 16 EXIT FOR 17 END IF 18 END FOR 19 FOR I=1 TO N STEP 1 20 PRINT D[I] 21 END FOR 22 END

78 兩兩合併排序法兩兩合併排序法 (2-Way Merge Sort) 是先將資料分成幾個排序好的串列, 然後把串列兩兩合併成更大的已排序串列, 直到合併成包含所有資料的已排序串列為止

79 兩兩合併排序法如右圖要排序 10 個整數資料先分成 10 個只有一個資料的串列, 然後兩兩合併成擁有兩個資料的串列接著又合併成有 4 個資料的串列, 依此做下去, 直到合併成包含 10 個資料的串列

80 兩兩合併排序法合併方法是將兩個已排序好的資料串列 A 與 B 合併成為一排序好的串列 C 其方法是分別從 A 和 B 中依小到大的順序取出第一數, 比較此二數, 將較小數放入 C 中, 並從較小數的來源串列中取出下一個數, 然後再與先前的較大數比較如此比較及讀取資料下去, 直到有一方的資料都已放入 C 中, 最後將另一方未放入 C 內的資料依序放入 C

81 兩兩合併排序法如右圖, 陣列 A 和 B 的內容都是依小到大排序好的三個整數現在我們要把這兩個資料串列合併到陣列 C 內, 還要保證陣列 C 的內容一樣是由小到大排序好的

82 兩兩合併排序法一開始比較 A[1] 和 B[1] 因為 B[1] 較小, 所以將 B[1] 放入 C[1]( 如圖 17.28), 陣列 B 及 C 的索引指標向前推 1 接著比較 A[1] 與 B[2], 此時 A[1] 較小, 所以放入 C[2] ( 圖 17.29), 然後將陣列 A 及 C 的索引指標向前推進

83 兩兩合併排序法再比較 A[2] 和 B[2] 因為 B[2] 較小, 所以將 B[2] 放入 C[]( 如圖 17.0), 陣列 B 及 C 的索引指標向前推進然後比較 A[2] 與 B[], 此時 B[] 較小, 所以放入 C[4]( 如圖 17.1)

84 兩兩合併排序法現在陣列 B 的資料都已放入 C, 所以把 A[2] 和 A[] 依序放入 C ( 如圖 17.2) 最後完成合併陣列 A 與 B 於陣列 C

85 兩兩合併排序法下圖的演算法 MERGE 是將陣列 A( 有 N 個已排好的整數 ) 與陣列 B( 有 M 個已排好的整數 ) 以合併成排序序列並存於陣列 C 中演算法 :MERGE (A[], N, B[], M, C[]) 輸入 :A[], N, B[], M, C[] 輸出 :C[] 1 BEGIN 2 I=1 J=1 4 K=1 5 WHILE I <= N AND J < = M 6 IF A[I] <= B[I] THEN 7 C[K]=A[I] 8 I=I+1 9 ELSE 10 C[K]=B[I] 11 J=J+1 12 END IF 1 K=K+1 14 END WHILE 15 IF I > N THEN 16 FOR L=J TO M STEP 1 17 C[K]=B[L] 18 K=K+1 19 END FOR 20 END IF 21 IF J > M THEN 22 FOR L=I TO N STEP 1 2 C[K]=A[L] 24 K=K+1 25 END FOR 26 END IF 27 END

86 17--2 搜尋在一堆資料裏尋找某特定的資料謂之搜尋 (Searching) 以下將陸續介紹 : 循序搜尋二分搜尋二元搜尋樹等常用搜尋法

87 17--2 搜尋循序搜尋 (Sequential Search) 又稱線性搜尋 (Linear Search), 依據資料儲存順序從頭至尾尋找下去如下圖, 陣列 D 中有六個整數資料若要尋找的資料為 25, 從 D[1] 開始比對, 然後 D[2], 一直到 D[] 才找到但如果要找的是 40, 就要經歷 D[1], D[2],..., D[6] 六次比對才找到

88 17--2 搜尋右圖的演算法 SEQSEACH 是在有 NUM 個整數的陣列 D 中以循序搜尋找尋 KEY 執行完後, 若 INDEX = 0, 表示 KEY 不在陣列 D 內, 否則,KEY 在 D[INDEX) 內演算法 :SEQSEACH (D[], NUM, KEY, INDEX) 輸入 :D[], NUM, KEY, INDEX 輸出 : INDEX 1 BEGIN 2 INDEX=0 FOR I=1 TO NUM 4 IF D[I]=KEY THEN 5 INDEX=I 6 EXIT FOR 7 END IF 8 END FOR 9 END

89 17--2 搜尋使用二分搜尋 (Binary Search) 的前題是資料要先排序好假設陣列 D 中有 N 個已排序好的數, 要尋找的資料為 KEY 二分搜尋法是每比對一次後就把搜尋範圍縮小一半, 在 (log2n ) +1 次比對內就可判斷出 KEY 是否在資料中一開始搜尋的範圍是 D[1] 至 D[N ], 將 KEY 與 D[1] 至 D[N ] 的中間數 D[(1 + N )/2] 相比, 若 KEY 較大, 就將搜尋範圍縮小為後半, 即 D[(1 + N )/2+1] 至 D[N ]; KEY 較小, 就將搜尋範圍縮小為前半, 即 D[1] 至 D[(1 + N )/2 1] 然後 KEY 再與新搜尋範圍的中間數比對, 如此遞迴地搜尋下去

90 17--2 搜尋如下圖, 陣列 D 內有依小至大順序排好的七個整數假設 KEY = 41, 第一次 KEY 與中間數 D[4] 比較因 KEY > D[4], 所以繼續搜尋 D[5] 至 D[7] 第二次 KEY 與 D[6] 比較, 結果 KEY < D[6], 再搜尋 D[5] 至 D[5] 第三次 KEY 與 D[5] 比較, 因為 KEY = D[5], 所以 KEY 的確在陣列 D 中

91 17--2 搜尋下圖的演算法 BINSEACH 是在有 NUM 個整數的陣列 D 中以二分搜尋法找尋 KEY 執行完後, 若 INDEX = 0, 表示 KEY 不在陣列 D 內, 否則,KEY 在 D [INDEX] 內演算法 :BINSEACH (D[], NUM, KEY, INDEX) 輸入 :D[], NUM, KEY, INDEX 輸出 : INDEX 1 BEGIN 2 INDEX=0 LOWER=1 4 UPPER=NUM 5 WHILE LOWER <= UPPER 6 MIDDLE= (LOWER+UPPER)/2 7 IF KEY > D[MIDDLE] THEN 8 LOWER=MIDDLE+1 9 END IF 10 IF KEY < D[MIDDLE] THEN 11 UPPER=MIDDLE-1 12 END IF 1 IF KEY = D[MIDDLE] THEN 14 INDEX=MIDDLE 15 EXIT WHILE 16 END IF 17 END WHILE 18 END

92 二元搜尋樹二元搜尋樹 (Binary Search Tree) 是二元樹的結構, 但是樹中的每一節點資料都不小於它的左孩子, 也不大於它的右孩子將資料先存於此特殊的二元搜尋樹, 之後可利用此樹做資料的搜尋

93 二元搜尋樹若有等七個整數資料, 我們依據輸入順序建立一二元樹第一個輸入的數 18 當作樹根 ( 如圖 17.6) 接下來輸入的數從樹根的節點資料開始與之相比若比節點資料大, 就再和其右孩子相比 ( 如果沒有右孩子, 就將新輸入的數當作其右孩子 ) 若比節點資料小, 就再和其左孩子相比 ( 如果沒有左孩子, 就將新輸入的數當作其左孩子 ) 18 圖 17.6

94 二元搜尋樹圖 17.7 圖 17.8 圖 17.9 圖圖和圖分別是輸入和 1 後二元樹的變化最後在圖上得到的二元樹就是這七個資料的二元搜尋樹圖 17.7 圖圖 17.9 圖圖圖 17.42

95 二元搜尋樹假設搜尋的資料為 KEY, 從二元搜尋樹之樹根的節點資料開始與 KEY 相比若相等, 就找到了 ; 若 KEY 比節點資料大, 而且此節點又沒有右孩子, 表示 KEY 不在資料內, 否則就再和其右孩子相比 ; 若比節點資料小, 而且此節點又沒有左孩子, 表示 KEY 不在資料內, 否則就再和其左孩子相比

96 二元搜尋樹例如在圖的二元搜尋樹上找尋 KEY, 假設 KEY 為 1 開始時 KEY 與樹根 18 相比, 因為 KEY < 18, 所以再與其左孩子節點 11 相比又因 KEY > 11, 再與節點 11 的右孩子節點 1 相比, 結果就找到了 KEY 的確在這些資料中圖

97 二元搜尋樹但當 KEY=12 時, 開始與樹根 18 相比, 因為 KEY < 18, 所以再與其左孩子節點 11 相比又因 KEY > 11, 再與節點 11 的右孩子節點 1 相比因為 KEY < 1, 而且節點 1 又沒有左孩子, 表示 KEY 不在這些資料中圖

98 17-4 演算法分析與策略演算法 (Algorithm) 就是解決問題的方法例如兩個整數相加的問題, 其演算法是先做個位數字的相加, 再做十位數字的相加, 接著是百位數, 依此類推完整的演算法包括明確的輸出入資料和詳細且有限的執行步驟 98

99 算法分析圖 17.4 描繪出在電腦上解決問題的基本架構演算法以程式描述後在電腦上執行, 資料輸入至程式後, 經過程式對資料的運算, 最後產生解答資料演算法 ( 程式 ) 圖 17.4 解答 99

100 算法分析假設演算法 A 能解問題 P, 而問題 P 的輸入資料量為 N 假設資料量為 N 的資料樣本 (Data Instance) 有 D 1, D 2,..., D i,..., D m 共 m 種, 令 T (D i ) 表示當輸入資料為 D i 時演算法 A 要執行的運算或步驟的總次數演算法 A 的最好狀況時間複雜度 (Best-Case Time Complexity) 是 T (D i ) (1 i m) 中最小的值, 即 min 1 i m { T (D i )}, 而演算法 A 的最差狀況時間複雜度 (Worst-Case Time Complexity) 是 T (D i ) (1 i m) 中最大者, 即 max 1 i m { T (D i )} 100

101 算法分析而演算法 A 的一般狀況時間複雜度 (Average- Case Time Complexity) 是 T (D i ) (1 i m) 的平均值或期望值 ( 在某機率假設下 ) 通常我們說演算法 A 的時間複雜度為 C 就是指其最差狀況時間複雜度為 C 例如問題 P 之輸入資料量為 N 的樣本有 D 1, D 2, D 三種, 而 T (D 1 ) =,T (D 2 ) = N,T (D ) = N, 則演算法 A 的最好狀況時間複雜度為, 最差狀況為 N, 而一般狀況為 ( + N + N ) / 稱演算法 A 的時間複雜度為 N 101

102 算法分析時間複雜度常用階次 (Order) 來表達首先介紹表示漸近上限 (Asymptotic Upper Bound) 的 O 階次如果存在某固定正實數 c 及某個非負整數 m 使得對所有的 n m, 不等式 g (n) c f (n) 都成立, 則 g (n) = O ( f (n)), 稱 f (n) 為 g (n) 的漸近上限例如 N 2 +10N = O (N 2 ), 因為當 n 10 時, N N 2N 2 稱 N 2 為 N N 的漸進上限 102

103 算法分析接著介紹 Ω 階次若存在某固定正變數 c 及某非負整數 m 使得對所有 n m, 不等式 g (n) c f (n) 都成立, 則 g (n) = Ω ( f (n)), 稱 f (n) 為 g (n) 的漸近下限 (Asymptotic Lower Bound) 例如 n = Ω (n 2 ), 因為當 n 1 時,n 1 n 2, 所以 n 2 為 n 的漸近下限 10

104 算法分析若 g (n) = O ( f (n)) 且 g (n) = Ω ( f (n)), 則稱 f (n) 為 g (n) 的真正階次 (Exact Order), 記為 g (n) = θ ( f (n)) 104

105 算法分析表 17.1 顯示多種 f (n) 函數的數值, 當 n 足夠大時,2 n > n > n 2 > nlogn > n > logn n f(n) 2 n n n 2 nlogn n logn E E E E

106 算法分析如果 f (n) = c p (n), 其中 c 為常數,p (n) 為 n 的多項式函數 (Polynomial Function) ( 如 n, n , log 2 n, nlog 2 n), 則稱 f (n) 為指數函數 (Exponential Function) 例如 2 n n 4 logn 等函數都是指數函數因為指數函數的數值上升速度相當快, 所以時間複雜度為指數函數階次的演算法, 在資料量足夠多時, 需要相當長的時間才能解得答案 106

107 算法分析若演算法的時間複雜度是 O (p (n)), 其中 p (n) 為 n 的多項式函數, 則稱此演算法為多項式時間演算法 (Polynomial-Time Algorithm) 若問題 P 能用多項式時間演算法解得答案, 則問題 P 就能用電腦在合理時間內求得答案, 在電腦上是可解 (Tractable) 的問題例如排序及搜尋等問題就是此類問題 107

108 算法分析表 17.2 是各種排序法及搜尋法的時間複雜度演算法時間複雜度最好狀況最差狀況插入排序 O(n) O(n 2 ) 氣泡排序 O(n) O(n 2 ) 兩兩合併排序 O(n) O (nlog 2 n) 循序搜尋 O(1) O(n) 二分搜尋 O(1) O (log 2 n) 108

109 算法分析若可解問題 P 的演算法 A 的時間複雜度為 t, 而解問題 P 的演算法最少需要 t 時間, 則稱演算法 A 是解問題 P 的最佳演算法 (Optimal Algorithm) 像排序 n 個數的問題已證明在比較與交換模式 (compare-and-exchange model) 下最少需要 Ω (nlog 2 n) 時間, 而兩兩合併排序法的時間複雜度也是 O (nlog 2 n), 所以兩兩合併排序法是最佳排序演算法 109

110 算法分析若問題 P 到目前為止仍無法以多項式時間演算法解得答案, 也就是無法於電腦上在合理時間內求得答案, 我們稱問題 P 為難解問題 (Intractable Problem) 有許多的應用問題是屬於這類的問題, 舉例說明如下 : 1. 旅行推銷員問題 (Travelling Salesman Problem) 有各城市間的公路交通圖, 請找出一條從某城市出發, 經過每個城市一次再回到該城市的最小長度的交通路線 110

111 算法分析 2. 圖形塗色問題 (Graph-Coloring Problem) 給一由頂點 (Vertex) 及邊 (Edge) 構成的圖形, 在有邊相連的兩頂點不能有相同顏色的限制下來對頂點塗色, 請問所需的顏色個數最少是多少?. 裝箱問題 (Bin-Packing Problem) 有 n 個不可分解的貨物, 其大小分別為 S 1,..., S n, 0 < S i 1, 若每個箱子的容量為 1, 請問將這 n 個貨物放入箱子內所需的最小箱子個數為何? 111

112 算法分析目前要找出難解問題的真正解答 (exact solution) 是相當耗時的, 因為目前還沒有人能提出在當今電腦架構下任何快速的演算法以求得真正解答然而有些難解問題是能以多項式時間演算法求得接近解答的逼近解 (approximate solution) 112

113 個別擊破策略個別擊破策略 (Divide-and-Conquer Method) 的主要精神是將原來的問題 P 分解成 2 個或多個子問題, 待個別解決這些子問題後再經由合併 (Merge) 處理, 整理出原來問題的答案, 而分割後的子問題是資料量較小的問題 P 因此在解子問題時又可遞迴應用上述的方法, 經由分割及合併的過程得到解答前一章介紹的二分搜尋法就是採用個別擊破策略 11

114 個別擊破策略兩兩合併排序法也可視為是個別擊破的策略如圖所示, 一開始就將資料分割成兩部分處理, 然後再遞迴細分各資料直至不能細分為止, 接著就兩兩合併成排序的序列, 慢慢的將分割的資料合併成排序的序列, 最後得到所有資料的排序結果分割分割分割合併合併合併圖

115 個別擊破策略讓我們回到排序的問題上假設陣列 D 中依序放有 4,, 5, 2, 6, 7, 1 等七個整數, 我們的目的是將這些數依小到大順序排序首先觀察第一個數 4 在最後排序好的序列中應是第四位, 即應放在 D [4] 如果能進一步將小於 4 的數放在 D [1] 至 D[] 中, 而大於 4 的數放在 D[5] 至 D [7] 中, 則只要再分別排序好 D [1] 至 D[] 的數及 D[5] 至 D[7] 內的數, 那原來排序問題就解決了 115

116 個別擊破策略接著介紹如何將 4 放到 D[4] 及將小於 4 的數集中在 D[1] 至 D[] 內, 而大於 4 的數則集中在 D[5] 至 D[7] 內 116

117 個別擊破策略令 i = 2,j = 7 從 D[i] 開始向右找到第一個比 D[1] 大的數, 以 i 紀錄其陣列的索引從 D[ j] 開始向左找到第一個不大於 4 的數, 以 j 紀錄其陣列索引 117

118 個別擊破策略若 i < j, 則交換 D[i] 與 D[ j] 的內容, 並繼續前述的左右搜尋 ; 若 i j, 則交換 D[1] 與 D[ j] 的內容, 並停止搜尋 118

119 個別擊破策略雖然快速排序法的最差時間複雜度為 O (n 2 ) ( 其中 n 為資料個數 ), 因為其一般狀況時間複雜度為 O (nlog 2 n), 還是相當實用的排序方法 119

120 17-4- 貪婪策略貪婪策略 (Greedy Method) 常用來解決最佳化問題 (Optimization Problem) 貪婪法是最直接的解法, 每次的決策都是朝向目前最好 " 的方向前進, 而且不回頭 120

121 17-4- 貪婪策略舉例來說, 某一個銀行出納櫃檯要服務 n 個顧客, 銀行的目標是希望顧客在櫃檯等待的平均時間要最少解決之道是每次都從尚未服務的顧客中, 選擇需要服務時間最短的顧客來服務, 如此就可達到預期目標像這樣每次都選擇最小服務時間的策略就是一種貪婪策略 121

122 17-4- 貪婪策略假設有 5 個顧客 A, B, C, D, E 幾乎同時到達銀行櫃檯, 其所需服務時間如表 17. 根據貪婪演算法, 銀行櫃檯將依序服務 B, D, E, C, A 顧客在櫃檯等待的平均時間為 [1 + (1 + 2) + ( ) + ( ) + ( ) ] / 5 = 7 顧客所需服務時間 A 5 B 1 C 4 D 2 E 122

123 17-4- 貪婪策略再介紹一個可用貪婪策略解決的背包問題 (Knapsack Problem) 假設有多個可分解的物件和一只限重 W 的背包, 每件物件有其重量及其被選取放入背包內的利益請問要如何將物件放進背包內而使得獲得的利益最大? 解決的方法是每次在限重的情形下, 選取尚未放入的物件中擁有最大的利益與重量的比值之物件放入背包內 12

124 17-4- 貪婪策略設背包限重 100, 有 A, B, C, D, E 共五個物件, 其資料如表 17.4 物件重量利益利益 / 重量 A B C D E

125 17-4- 貪婪策略因為物件 C 的利益 / 重量最高, 所以將物件 C 放入背包內, 此時背包的重量為 0 物件個數累計利益重量 C

126 17-4- 貪婪策略接著從物件 A, B, D, E 中挑出其利益 / 重量最高的物件 A 放入背包內, 這時背包的重量為 0+10=40 物件個數累計利益重量 C A

127 17-4- 貪婪策略接下來, 從物件 B, D, E 中挑出其利益 / 重量最高的物件 B 裝入背包內, 之後背包的重量為 = 60 物件個數累計利益重量 C A B

128 17-4- 貪婪策略再從剩下的物件 D 和 E 中選出其利益 / 重量最高的物件 E 由於物件 E 整個放入背包內會超過重量 100, 所以物件 E 只能放入 0.8 個物件個數累計利益重量 C A B E 表

129 17-4- 貪婪策略放入以後得總重量為 = 100 最後得到的利益為 = 164 物件裝入背包的情形整理於表 17.5 物件個數累計利益重量 C A B E 表

130 17-4- 貪婪策略接著介紹最小擴展樹 (Minimum Spanning Tree) 問題圖是由頂點 (Vertex) 及邊 (Edge) 構成的圖形, 其中圓圈代表頂點, 連接兩頂點的線為邊, 而且每個邊都有非負 (nonnegtive) 的加權 (Weight) ( 例如頂點 V 與頂點 V 5 間的邊之加權為 5) 4 V 1 V V V 4 V 8 10

131 17-4- 貪婪策略由於圖的邊都無方向, 稱圖的圖形為無向圖 (Undirected Graph) V V 4 4 V V 2 V 2 11

132 17-4- 貪婪策略定義無向圖的路徑 (Path) 為頂點的序列, 其中序列裡每個頂點與其後一個頂點之間必有邊相連例如圖中 [V 1, V 5, V 2 ] 是一條從頂點 V 1 到頂點 V 2 的路徑 4 V 1 V V V 4 V 8 12

133 17-4- 貪婪策略若無向圖的任兩頂點都存在一條路徑, 則稱此圖為聯通圖 (Connected Graph) 例如圖就是聯通圖從某頂點出發回到該頂點的路徑稱為迴圈 (Cycle) 例如圖的 [V 1, V 5, V 2, V 1 ] 路 6 徑就是迴圈一個沒有迴圈的圖形稱為無迴圈圖 (Acyclic Graph) 4 V V 5 5 V 4 8 V 2 V 2 1

134 17-4- 貪婪策略定義樹 (Tree) 為聯通的無迴圈圖若圖形 G 的頂點所成的集合為 V, 邊所成的集合為 E, 以 G = (V, E) 表示圖形 G 定義圖形 G = (V, E) 的擴展樹 (Spanning Tree) T = (V, E) 是包括所有 G 的頂點的樹, 其中 E' 是 E 的子集合例如圖 (a) 及 (b) 都是圖的擴展樹 V V 4 V V 4 V V 5 5 V 2 2 V 圖 V 2 2 V

135 17-4- 貪婪策略接著介紹以貪婪策略設計的 Kruskal 演算法假設要求圖形 G = (V, E) 的最小擴展樹此演算法依據邊的加權由小到大的順序考慮該邊是否為最小擴展樹的邊若邊 e 加入後不會產生迴圈, 則邊 e 為最小擴展樹的一員 ; 反之, 邊 e 就不是最小擴展樹的一員如此重複直到建構出最小擴展樹詳細的步驟分述於下 : 15

136 17-4- 貪婪策略演算法 :Kruskal 方法輸入 : 圖形 G = (V, E) 輸出 :G 的最小擴展樹步驟 1: 將圖形 G = (V, E) 所有的邊依其加權由小到大排好, 依序為 e 1, e 2, e,, e m 步驟 2: 建立圖形 T = (V, E ), 其中 E = Φ 設 i = 1 步驟 : 若 e i 加入圖形 T 中不產生迴圈, 則將 e i 加入圖形 T, 即 E = E { e i }; 否則, i = i + 1 步驟 4: 若圖形 T 的邊數小於 V -1, 則重複步驟 ; 否則, 圖形 T 是圖形 G 的最小擴展樹, 結束演算法執行 16

137 17-4- 貪婪策略用 (a, b) 表示頂點 a 與頂點 b 的邊以找圖的最小擴展樹為例, 將圖的邊依加權排序後得 e 1 = (V 1,V 5 ), e 2 = (V 2,V ), e = (V 2,V 5 ), e 4 = (V 1,V 2 ), e 5 = (V,V 5 ), e 6 = (V 1,V 4 ), e 7 = (V 4,V 5 ), e 8 = (V,V 4 ) V 1 V 4 V 5 V 2 V (a) T V 1 1 V 2 2 V (d) 加入 (V 2, V 5 ) V 1 1 V 4 V 5 V 5 V 2 2 V (g) 加入 (V 1, V 4 ) 6 V 4 V 1 1 V 2 V (b) 加入 (V 1, V 5 ) V 1 1 V 4 V 5 V 4 V 5 V 2 V 2 (e) 拒絕 (V 1, V 2 ) V 1 1 V 2 2 V (c) 加入 (V 2, V ) V 1 1 V 4 V 5 V 4 V 5 V 2 V 2 (f) 拒絕 (V, V 5 ) 17

138 17-4- 貪婪策略一開始圖形 T 只有頂點但沒有邊 ( 圖 17.48(a)) 考慮 e 1 = (V 1,V 5 ), 因不產生迴圈, 就將 (V 1,V 5 ) 加入 T 內 ( 圖 17.49(b)) V 1 V 4 V 5 V 2 V (a) T V 1 1 V 4 V 5 V 2 V 2 V 1 1 V 2 V (b) 加入 (V 1, V 5 ) V 1 1 V 4 V 5 V 4 V 5 V 2 V 2 V 1 1 V 2 2 V (c) 加入 (V 2, V ) V 1 1 V 4 V 5 V 4 V 5 V 2 V 2 (d) 加入 (V 2, V 5 ) (e) 拒絕 (V 1, V 2 ) (f) 拒絕 (V, V 5 ) V V 4 V 5 V 2 2 V (g) 加入 (V 1, V 4 ) 18

139 17-4- 貪婪策略同樣的, e 2 = (V 2,V ) 及 e = (V 2,V 5 ) 也依序加入 T 內 ( 圖 17.49(c) 和 (d)) V 1 V 4 V 5 V 2 V (a) T V 1 1 V 4 V 5 V 2 V (b) 加入 (V 1, V 5 ) V 1 1 V 4 V 5 V 2 2 V (c) 加入 (V 2, V ) V 1 1 V 4 V 1 1 V 4 V 1 1 V 4 V 5 V 5 V 5 V 2 V 2 (d) 加入 (V 2, V 5 ) V 2 V 2 (e) 拒絕 (V 1, V 2 ) V 2 V 2 (f) 拒絕 (V, V 5 ) V V 4 V 5 V 2 V 2 (g) 加入 (V 1, V 4 ) 19

140 17-4- 貪婪策略當考慮 e 4 = (V 1,V 2 ) 時, 因加入後會產生 [V 1, V 5, V 2, V 1 ] 的迴圈, 所以拒絕 (V 1,V 2 ) 的加入 ( 圖 17.49(e)) V 1 V 4 V 5 V 2 V (a) T V 1 1 V 4 V 5 V 2 V 2 V 1 1 V 2 V (b) 加入 (V 1, V 5 ) V 1 1 V 4 V 5 V 4 V 5 V 2 V 2 V 1 1 V 2 2 V (c) 加入 (V 2, V ) V 1 1 V 4 V 5 V 4 V 5 V 2 V 2 (d) 加入 (V 2, V 5 ) (e) 拒絕 (V 1, V 2 ) (f) 拒絕 (V, V 5 ) V V 4 V 5 V 2 2 V (g) 加入 (V 1, V 4 ) 140

141 17-4- 貪婪策略同樣的理由, 也拒絕 e 5 = (V,V 5 ) 的加入 ( 圖 17.49(f)) V 1 V 4 V 5 V 2 V V 1 1 V 4 V 5 V 2 V V 1 1 V 4 V 5 V 2 V 2 (a) T (b) 加入 (V 1, V 5 ) (c) 加入 (V 2, V ) V 1 1 V 4 V 1 1 V 4 V 1 1 V 4 V 5 V 5 V 5 V 2 V 2 (d) 加入 (V 2, V 5 ) V 2 V 2 (e) 拒絕 (V 1, V 2 ) V 2 V 2 (f) 拒絕 (V, V 5 ) V V 4 V 5 V 2 V 2 (g) 加入 (V 1, V 4 ) 141

142 17-4- 貪婪策略而後因 e 6 = (V 1,V 4 ) 加入 T 後不產生迴圈, 所以將 (V 1,V 4 ) 加入 T 中 ( 圖 17.49(g)) 此時 T 為 G 的擴展樹, 停止演算法最後得到的圖 17.49(g) 就是圖的最小擴展樹 V 1 V 4 V 5 V 2 V (a) T V 1 1 V 2 2 V (d) 加入 (V 2, V 5 ) V 1 1 V 4 V 5 V 5 V 2 2 V (g) 加入 (V 1, V 4 ) 6 V 4 V 1 1 V 2 V (b) 加入 (V 1, V 5 ) V 1 1 V 4 V 5 V 4 V 5 V 2 V 2 (e) 拒絕 (V 1, V 2 ) V 1 1 V 2 2 V (c) 加入 (V 2, V ) V 1 1 V 4 V 5 V 4 V 5 V 2 V 2 (f) 拒絕 (V, V 5 ) 142

143 17-4- 貪婪策略接著介紹最短路徑問題 (Shortest Path Problem) 下圖是 S A B T 四個地點的交通路線, 各路線分別標上距離 : S 40 A 0 B 60 T

144 17-4- 貪婪策略假設要求從 S 到 T 的最短路徑長度令 D (a, b) 表示從 a 到 b 的最短路徑長度從上圖, 可知 D (S, T) = D (S, A) +D (A, B) +D (B, T) = = 45 如此只要利用貪婪策略就能得到答案但是此貪婪策略並不適用於所有的最短路徑問題 144

145 17-4- 貪婪策略例如要找下圖的 D (S, T ), 則 D (S, T ) = = 44, 此結果不等於 D (S, A) + D (A, B) + D (B, T) = S 40 A 0 B 60 T 圖

146 動態規劃先前介紹的個別擊破策略是遞迴地將問題分成較小的問題後分別求得解答, 然後合併每個小部分的答案成為完整的答案, 是屬於由上至下 (Top- Down) 的計算策略例如要計算下面的 Fibonacci 函數 f (n): f (0) = 0 f (1) = 1 f (n) = f (n 1) + f (n 2), n 2 146

147 動態規劃若要計算 f (5), 利用個別擊破方法的計算過程如下圖所示: f (5) f () f (4) f (1) f (2) f (2) f () f (0) f (1) f (0) f (1) f (1) f (2) f (0) f (1) 圖其中 f (), f (2), f (1), f (0) 被重複計算許多次, 如果能先依序將 f (0), f (1),f (2), f (), f (4) 的結果計算出來並儲存於表格或陣列, 就可避免重複計算, 增進計算速度 147

148 動態規劃以陣列 FIB 儲存 Fibonacci 函數, 可利用下面的方法計算 f (n): FIB[0] =0 FIB[1] =1 FOR I = 2 TO n STEP 1 FIB[I] = FIB[I-1] + FIB[I-2] END FOR 將問題分成小問題, 然後直接解小問題, 將結果儲存起來以備之後使用, 像這種由下至上 (Bottom-Up) 的設計策略稱為動態規劃 (Dynamic Programming) 148

149 動態規劃二項式係數 (Binomial Coefficient) 的定義為當 n, k 的值不小時,n! 及 k! 是很大的天文數字, 非常難計算修改此定義, 重新以遞迴關係定義於下: 149

150 動態規劃陣列 BI 是一個二維陣列, 有 n +1 個列 ( 編號從 0 至 n),k + 1 個欄 ( 編號從 0 到 k), 讓 B (n, k) 的值儲存於 BI[n, k] 內下列的方法能很快的計算出 B (n, k) : FOR I = 0 TO n STEP 1 FOR J = 0 TO min{i, k} STEP 1 IF J = 0 OR J = I THEN ELSE BI[I, J] =1 BI[I, J] =BI[I-1, J-1] +BI[I-1,J] END IF END FOR END FOR 150

151 動態規劃接下來介紹有向圖的最短路徑問題 (Shortest Path Problem) 下圖是一個有向的 (Directed) 且加權的的圖形, 其中圓圈代表頂點, 而連接兩頂點的線稱為邊 2 1 V 1 V 4 V V 151

152 動態規劃每個邊都有方向也有對應的非負的加權, 例如有一個從頂點 V 1 至頂點 V 2 的邊, 其加權為 1 路徑是一個頂點序列, 其中序列裡每個頂點到其後一個頂點的邊一定存在例如 [V 1, V, V 2 ] 就是一條從頂點 V 1 至頂點 V 2 的路徑 2 V V V V 4

153 動態規劃設定路徑的長度為路徑上所有的邊的加權的和例如路徑 [V 1, V, V 2 ] 的長度為 = 10 假設邊的加權不為負數, 最短路徑問題是要去找出在有向及加權的圖形上任兩頂點的最短路徑 2 V V V 4 4 V 15

154 動態規劃假設圖形有 n 個頂點, 分別是 V 1,, V n 令 d k (i, j) 表示只有經過集合 {V 1, V 2,, V k } 中某頂點的 V i 到 V j 的最短路徑長度, 令 d 0 (i, j) 為 V i 到 V j 的邊的加權 154

155 動態規劃經過集合 {V 1,,V k } 中某些頂點的 V i 到 V j 最短路徑可能不經過 V k, 也可能經過 V k, 如果不經過 V k, 則 d k (i,j) = d k 1 (i,j); 如果經過 V k, 則 d k (i,j) = d k 1 (i,k) + d k 1 (k,j), 所以 d k (i, j) 可由下列式子計算得到 155

156 動態規劃對圖的圖形求最短路徑, 計算過程的 d 0, d 1,, d 4 表格列於圖 d d

157 動態規劃 d d d

158 動態規劃假設 V i 到 V j 的最短路徑經過 V k, 則 V i 到 V j 的路徑也是最短的路徑, 而 V k 到 V j 的路徑也是最短的例如, 由 V 2 到 V 4 的最短路徑為 [V 2, V 1, V 4 ], 而路徑 [V 2, V 1 ] 也是 V 2 到 V 1 的最短路徑, 而路徑 [V 1, V 4 ] 也是 V 1 到 V 4 的最短路徑像這樣最佳解包含其組成份子的最佳解之特性, 稱為最佳化原則 (Principle of Optimality) 如果最佳化問題能應用此最佳化原則, 則可以用動態規劃策略設計遞迴運算式來求得最佳解 158

Microsoft PowerPoint - DS&Algorithm [相容模式]

Microsoft PowerPoint - DS&Algorithm [相容模式] 資料結構與演算法陳怡芬什麼是 Data structure? 將資料群組織起來的抽象資料型態, 稱為資料結構典型的資料結構資料表格 (Table) 堆疊 (stack) 佇列 (queue) 串列 (list) 樹 (tree) 圖形 (graph) table, stack, queue: 可用陣列表現出來 List, tree, graph: 適合用指標表現出來堆疊 (Stack) 將資料依序從堆疊下面儲存起來,