Chapter 17 資料結構與演算法 1
學習目標 第 17 章資料結構與演算法 認識資料結構與演算法的定義 熟悉佇列與堆疊的原理與應用 熟悉二元樹的原理與應用 瞭解常用排序與搜尋方法的原理與應用 瞭解演算法的分析方法 瞭解基本演算法設計策略 2
大綱 17-1 虛擬碼 17-2 基礎資料結構 17- 基礎演算法 17-4 演算法分析與策略
CH17 資料結構與演算法 資料結構是指資料在電腦內的表示方式和存取方法 演算法就是電腦處理資料的詳細流程 資料結構與演算法要相互配合才能有效率的處理資料 每個資料結構都有其對應的存取使用方法, 演算法設計必須搭配資料結構設計才能達到最佳表現
17-1 虛擬碼 流程圖 (Flow Chart): 用來描繪虛擬碼動作 流程圖是由一些圖形所組成, 主要的圖形如下圖所示 動作 圖形 運算 / 處理 / 轉換 決策 判斷 條件 是 否 邏輯流向
17-1 虛擬碼 以下介紹幾個主要的 虛擬碼 (pseudo code) 指令 READ READ 讀入資料儲存於某變數 其語法格式如下 : READ 變數名稱 PRINT PRINT 指令用來輸出資料 語法格式如下 : PRINT 變數名稱或訊息
17-1 虛擬碼 IF-THEN IF-THEN 指令在選擇或決策使用 語法格式為 : IF 條件式 THEN 指令敘述 ENDIF 條件式 是 否 指令敘述
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
17-1 虛擬碼 IF-THEN-ELSE 此指令在選擇或決策時使用 語法格式為 : IF 條件式 THEN 指令敘述 1 ELSE 指令敘述 2 ENDIF 條件式成立 是 否 指令敘述 1 指令敘述 2
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
17-1 虛擬碼 FOR-LOOP 此指令在需重複執行指令時使用 語法格式為 : FOR 控制變數 = 初值 TO 終值 SETP 累加值指令敘述 END FOR
17-1 虛擬碼 FOR-LOOP 累加值為正值或 0 時 : 累加值為負值或 0 時 : 控制變數 = 初值 控制變數 = 初值 控制變數 終值 否 控制變數 終值 否 是 是 指令敘述 指令敘述 控制變數 = 控制變數 + 累加值 控制變數 = 控制變數 + 累加值
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
17-1 虛擬碼 WHILE-LOOP 此指令在需重複執行指令時使用 語法格式為 : WHILE 條件運算式 指令敘述 END WHILE 可以把前面 FOR- LOOP 的例子改為 WHILE-LOOP: I=1 WHILE I<=5 PRINT A I=I+1 END WHILE WHILE 條件運算式 成立 指令敘述 不成立
17-1 虛擬碼 EXIT EXIT 指令表示停止執行虛擬碼 語法格式為 : EXIT EXIT FOR EXIT FOR 指令將停止執行目前的 FOR-LOOP, 並繼續執行目前 FOR-LOOP 後的第一個指令 語法格式為 : EXIT FOR
17-1 虛擬碼 EXIT WHILE EXIT WHILE 指令表示停止執行目前的 WHILE-LOOP, 並繼續執行目前 WHILE-LOOP 後的第一個指令 語法格式為 : EXIT WHILE
17-1 虛擬碼 本章演算法之格式 : 格式中的演算法描述可以虛擬碼敘述, 或以一步一步的步驟式方式敘述之 本章將演算法描述格式如下 : 演算法 : 名稱輸入 : 輸入資料輸出 : 輸出資料 BEGIN 演算法描述 END
17-2 基礎資料結構 陣列 (Array): 是最常見的資料結構之一 當一個資料需儲存到主記憶體時, 可以指定一個變數來儲存, 但若要同時處理 100 個同樣類型資料時, 指定 100 個不同變數名稱, 在使用上就相當不便了, 此時就能利用陣列來處理 陣列是記憶體的變數名稱, 它是一群具有相同性質的資料型態之集合, 而各個元素以不同的註標 (Index) 值來區分
17-2 基礎資料結構 一維陣列 : 欲儲存 10 個人的平均成績 79,80,55,75,99,65,70,68,90,74, 可以使用名稱為 SCORE 的陣列, 而各元素的變數名稱分別為 SCORE[1],SCORE[2],SCORE[],...,SCORE[10], 其陣列的表示如下 : 1 2 4 5 6 7 8 9 10 79 80 55 75 95 65 70 68 90 74 SCORE[1] SCORE[2] SCORE[] SCORE[4] SCORE[5] SCORE[6] SCORE[7] SCORE[8] SCORE[9] SCORE[10]
17-2 基礎資料結構 上述以一個註標來存取元素的陣列稱為一維 (One Dimension) 陣列, 以 n 個註標來存取元素的陣列稱為 n 維陣列 第一個學生 79 80 55 75 95 65 70 68 90 74 第二個學生 80 85 40 80 85 90 95 9 70 60 第三個學生 90 60 90 85 90 75 79 85 88 90 第四個學生 60 90 80 75 95 75 80 8 86 90 第一次考試第二次考試第三次考試第四次考試第五次考試第六次考試第七次考試第八次考試第九次考試第十次考試
17-2-1 佇列與堆疊 當我們買票看電影時, 大家依據到達的先後次序排隊買票, 先來的先買票進場 ; 但是當我們清洗餐盤時, 常是把洗完的盤子直接就放在之前洗好的盤子的最上面, 等到要取用盤子時會先拿最上面的盤子, 反而是後放上去的盤子先使用 前者排隊買票是 先進先出 (First In First Out,FIFO) 的處理觀念, 而後者使用盤子是 後進先出 (Last In First Out,LIFO) 的處理觀念 接下來介紹的佇列和堆疊分別應用了 FIFO 和 LIFO 的處理觀念 21
17-2-1 佇列與堆疊 佇列 (Queue) 是一個有順序的資料列, 其資料列有兩端, 分別稱為 頭端 (Front) 和 尾端 (Rear) ( 如圖 17.4) 資料可 加入 (Add) 佇列中或從佇列中 刪除 (Delete), 但是加入的資料只能加在資料列的尾端, 而刪除資料卻是除去資料列頭端的資料 頭端 尾端 A B C D E F 圖 17.4 22
17-2-1 佇列與堆疊 假設 Q 是一佇列, 以 ADD (Q, a) 表示將 a 加入佇列 Q 中, 以 DELETE (Q) 表示從佇列 Q 刪除資料 若佇列 Q 內有, 9, 7, 8, 四個資料, 其資料列的頭端是, 尾端是 8 ( 見圖 17.5 (a)) 頭端 尾端 頭端 尾端 頭端 尾端 9 7 8 9 7 8 5 Q ADD(Q, 5) ADD(Q, 2) (a) (b) 9 7 8 5 2 (c) DELETE(Q) 頭端 尾端 頭端 尾端 7 8 5 2 (e) DELETE(Q) 2 9 7 8 5 2 (d)
17-2-1 佇列與堆疊 如果將 5 加入 Q 中, 則 5 將加在尾端 8 之後, 而使 5 成為新的尾端 ( 圖 17.5 (b)) 頭端 尾端 頭端 尾端 頭端 尾端 9 7 8 9 7 8 5 Q ADD(Q, 5) ADD(Q, 2) (a) (b) 9 7 8 5 2 (c) DELETE(Q) 頭端 尾端 頭端 尾端 7 8 5 2 (e) DELETE(Q) 9 7 8 5 2 (d) 24
17-2-1 佇列與堆疊 再加入 2, 則佇列 Q 的資料列成為, 9, 7, 8, 5, 2 ( 圖 17.5 (c)) 頭端 尾端 頭端 尾端 頭端 尾端 9 7 8 9 7 8 5 Q ADD(Q, 5) ADD(Q, 2) (a) (b) 9 7 8 5 2 (c) DELETE(Q) 頭端 尾端 頭端 尾端 7 8 5 2 (e) DELETE(Q) 9 7 8 5 2 (d) 25
17-2-1 佇列與堆疊 若此時從佇列 Q 刪除資料, 將會刪除其頭端資料, 而使 9 成為新的頭端 ( 圖 17.5 (d)) 頭端 尾端 頭端 尾端 頭端 尾端 9 7 8 9 7 8 5 Q ADD(Q, 5) ADD(Q, 2) (a) (b) 9 7 8 5 2 (c) DELETE(Q) 頭端 尾端 頭端 尾端 7 8 5 2 (e) DELETE(Q) 9 7 8 5 2 (d) 26
17-2-1 佇列與堆疊 再刪除一次, 則資料列成為 7, 8, 5, 2 ( 圖 17.5 (e)) 頭端 尾端 頭端 尾端 頭端 尾端 9 7 8 9 7 8 5 Q ADD(Q, 5) ADD(Q, 2) (a) (b) 9 7 8 5 2 (c) DELETE(Q) 頭端 尾端 頭端 尾端 7 8 5 2 (e) DELETE(Q) 9 7 8 5 2 (d) 27
17-2-1 佇列與堆疊 下面分別是 ADD 和 DEL 兩個演算法, 其中 ADD 將 ITEM 加入最多有 N 個資料的佇列 Q 中, 而 DEL 是從最多有 N 個資料的佇列 Q 中刪除一個資料, 並以 ITEM 紀錄此刪除的資料 此處以一維陣列來儲存佇列 Q, 並以 FRONT 及 REAR 分別表示頭端及尾端的位置 28
17-2-1 佇列與堆疊 演算法 :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
17-2-1 佇列與堆疊 演算法 :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 + 1 7 ITEM = Q[FRONT] 8 END 0
17-2-1 佇列與堆疊 佇列常使用於作業系統中, 如工作佇列 (Job Queue) 列印佇列 (Printer Queue) 等 1
17-2-1 佇列與堆疊 堆疊 (Stack) 也是一個有順序的資料列, 其資料列兩端的一端稱為頂端 (Top) ( 如圖 17.6) 資料一樣可以加入 (Push) 堆疊中或從堆疊中刪除 (Pop), 可是加入的資料只能放於資料列的頂端, 而刪除資料也是目前資料列頂端的資料 C B A 堆疊圖 17.6 頂端 2
17-2-1 佇列與堆疊 假設 S 是一堆疊, 以 PUSH (S, a) 表示將 a 加入堆疊 S 中, 以 POP (S) 表示從堆疊 S 刪除資料 若堆疊 S 內有 1, 5, 三個資料, 其資料列的頂端是 ( 見圖 17.7 (a)) 5 1 頂端 9 5 1 頂端 2 9 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)
17-2-1 佇列與堆疊 如果將 9 加入 S 中, 則 9 將加在頂端 之上, 使 9 成為新的頂端 ( 圖 17.7 (b)) 5 1 頂端 9 5 1 頂端 2 9 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
17-2-1 佇列與堆疊 再加入 2, 則堆疊 S 的資料列成為 1, 5,, 9, 2 ( 圖 17.7 (c)), 其中 2 為頂端 5 1 頂端 9 5 1 頂端 2 9 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
17-2-1 佇列與堆疊 若此時從堆疊 S 刪除資料, 將會刪除其頂端資料 2, 而使 9 成為新的頂端 ( 圖 17.7 (d)) 5 1 頂端 9 5 1 頂端 2 9 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
17-2-1 佇列與堆疊 再刪除一次, 則資料列成為 1, 5, ( 圖 17.7 (e)), 其中 為頂端 5 1 頂端 9 5 1 頂端 2 9 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
17-2-1 佇列與堆疊 下面分別有 PUSH 和 POP 的演算法, 其中 PUSH 將 ITEM 加入最多有 N 個資料的堆疊 S 中, 而 POP 是從最多有 N 個資料的堆疊 S 中刪除一個資料, 並以 ITEM 紀錄此刪除的資料 此處以一維陣列來儲存堆疊 S 8
17-2-1 佇列與堆疊 演算法 : 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 + 1 7 S[TOP] = ITEM 8 END 9
17-2-1 佇列與堆疊 演算法 : 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
17-2-1 佇列與堆疊 堆疊的應用很多, 如程式執行 計算數學式等 以下以計算數學式為例說明堆疊的應用 假設我們要計算數學式 A + B*C 的值, 依四則運算的規則, 要先計算 B*C 的值後再加上 A 若用電腦計算 A + B*C, 不能單單地只從左至右計算, 需先將此算式轉換成 後序算式 (Postfix Expression), 亦即將運算符號放到其運算對象的後方 例如 A+B*C 的後序算式為 ABC*+ 41
17-2-1 佇列與堆疊 若給了一個後序算式, 我們就能利用堆疊算出其值 從左至右輸入後序算式, 當輸入的不是運算符號時, 就將其加入堆疊中 ; 若輸入的是運算符號, 就連續從堆疊中刪除兩個資料, 並以此二資料作為這運算符號的運算對象計算之, 然後將計算結果再加入堆疊中 如此這般直到算式輸入完畢, 最後位於堆疊頂端的資料就是此算式的值 42
17-2-1 佇列與堆疊 若現在要計算後序算式 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) 頂端
17-2-1 佇列與堆疊 當輸入 `*' 時, 從堆疊刪除 `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) 頂端
17-2-1 佇列與堆疊 最後輸入 `+' 時, 從堆疊刪除 `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) 頂端
17-2-2 樹與二元樹 下圖是一張具有樹狀結構的家譜 李一是大家的共同祖先, 其後有李二 李三和李四, 李二之後有李五, 李三之後有李六 李七和李八, 李四之後有李九, 而李七之後有李十 整張圖就像是以李一為樹根向外生長的一棵樹 46
17-2-2 樹與二元樹 樹 (Tree) 是一群有限個但至少一個 節點 (Node) 所成的集合, 其中某個節點被指定為樹根 (Root) 除了樹根以外的節點可分為 T 1,..., T n 等 n 個不相交的集合 (n 0), 而且每個集合也是一棵樹 T 1,..., T n 稱為樹根的 子樹 (Subtree) 若節點 N 沒有子樹, 則稱節點 N 為 樹葉 (Leaf) 節點 N 的子樹的樹根稱為節點 N 的 孩子 (Child), 而 N 稱為其孩子的 父母 (Parent) 47
17-2-2 樹與二元樹 以右圖為例 : 節點 有李一... 李十, 樹根是李一 T1, T 2, T 是李一的三棵子樹, 其樹根分別為李二 李三和李四 李五 李六 李十 李八和李九都是 樹葉 李一的孩子有李二 李三和李四, 李二 李三和李四的父母都是李一 48
17-2-2 樹與二元樹 二元樹 (Binary Tree): 是每個節點至多兩個孩子的樹 ( 如下圖 ) 我們稱節點左邊的孩子為左孩子, 右邊的為右孩子 49
17-2-2 樹與二元樹 用右圖的 LCHILD RCHILD 和 DATA 三個欄位表示節點 其中 LCHILD 和 RCHILD 分別是節點的左孩子和右孩子,DATA 是原來的節點資料 50
17-2-2 樹與二元樹 則可將圖 : 表示 改成 51
17-2-2 樹與二元樹 圖 17.1 是用所謂的 鏈結串列 (Linked List) 來表示二元樹 鏈結串列也可以用陣列表示 宣告 Data Lchild 和 Rchild 三個陣列, 先將節點資料存入陣列 Data 中, 然後一一將節點的左孩子及右孩子在位於陣列 Data 的註標值分別填入到陣列 Lchild 和 Rchild 中 圖 17.1 的陣列表示方式如圖 17.14 所示 52
17-2-2 樹與二元樹 追蹤 (Traversal) 樹上的節點是對樹狀結構相當重要的運算 追蹤樹上的節點, 就是拜訪每個節點恰好一次, 而其追蹤的結果就是拜訪節點的順序 追蹤方式可分 : 中序追蹤 後序追蹤 前序追蹤 以下將介紹二元樹的各種追蹤方式 5
17-2-2 樹與二元樹 中序追蹤 (Inorder Traversal): 若樹只有一個節點 a, 定義此樹之中序追蹤為 a 對二元樹的中序追蹤是先以中序追蹤拜訪樹根的左子樹, 再拜訪樹根, 然後以中序追蹤拜訪樹根的右子樹 各子樹又依此定義遞迴 (Recursive) 追蹤下去 54
17-2-2 樹與二元樹 以右圖的二元樹為例 樹根 `+' 的左子樹的中序追蹤為 A; 因為節點 `*' 的左 右子樹的中序追蹤分別為 B 和 C, 所以樹根 `+' 的右子樹的中序追蹤為 B*C 最後得知中序追蹤為 : A + B * C 55
17-2-2 樹與二元樹 以右圖的二元樹為例 : 以拜訪順序 : 左 中 右追蹤此樹 可知其中序追蹤是 DBEHAFCG 56
17-2-2 樹與二元樹 前序追蹤 (Preorder Traversal): 若樹只有一個節點 a, 定義其前序追蹤為 a 對二元樹的前序追蹤是先拜訪樹根, 再以前序追蹤拜訪樹根的左子樹, 然後以前序追蹤拜訪樹根的右子樹 各子樹又依此定義遞迴的追蹤下去 57
17-2-2 樹與二元樹 以右圖為例 : 以拜訪順序 : 中 左 右追蹤此樹 可得前序追蹤為 : ABDEHCFG 58
17-2-2 樹與二元樹 以右圖為例 : 以拜訪順序 : 中 左 右追蹤此樹 可得前序追蹤為 : +A*BC 59
17-2-2 樹與二元樹 後序追蹤 (Postorder Traversal): 若樹只有一個節點 a, 定義其後序追蹤為 a 對二元樹的後序追蹤是先以後序追蹤拜訪樹根的左子樹, 再以後序追蹤拜訪樹根的右子樹, 然後拜訪樹根 各子樹又依此定義遞迴的追蹤下去 60
17-2-2 樹與二元樹 以右圖為例 : 以拜訪順序 : 左 右 中追蹤此樹 可得前序追蹤為 : DHEBFGCA 61
17-2-2 樹與二元樹 以右圖為例 : 以拜訪順序 : 左 右 中追蹤此樹 可得前序追蹤為 : ABC*+ 62
17-2-2 樹與二元樹 二元樹還能用來表示廣泛使用的 Huffman 碼之 解碼樹 (Decode Tree) 以下圖為例 : 樹根 0 1 0 a 0 1 b 1 c d 6
17-2-2 樹與二元樹 下圖是 a b c d 四個字元的解碼樹 以 0 代表左分支, 以 1 代表右分支, 從樹根沿著分支走到各節點的路徑 可分別記為 : a:000 b:001 0 樹根 1 d c:01 0 1 d:1 c 以此路徑當作編碼, 當要傳送資料時, 依此編碼方式轉換資料, 而接收端在收到後利用此圖解碼之, 可還原成原始資料 0 a 1 b 64
17-2-2 樹與二元樹 如何找出解碼樹 : 假設字母 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 0.1 0.2 0. 0.4 (a) 65
17-2-2 樹與二元樹 其後的每一步驟如右圖 (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 0.1 0.2 0. 0.4 (a) ab 0. c d a b 0. 0.4 (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
17- 基礎演算法 本節將介紹以下兩個主題 : 17--1 排序 17--2 搜尋 67
17--1 排序 排序問題 (Sorting Problem) 是將資料依據其 大小 " 由小至大或由大至小排好, 例如將考卷依分數從高至低排好 以下將介紹四個排序法 1. 插入排序法 2. 氣泡排序法. 謝耳排序法 4. 兩兩合併排序法 68
17--1-1 插入排序法 插入排序法 (Insertion Sort) 利用下述技巧將資料排序好 假設 2 9 16 18 26 是一群由左至右依小至大順序排序好的整數資料 若 15 要在維持排序順序之條件下加入此群資料內, 可以將 15 直接插入 9 和 16 之間 如此 16 18 和 26 三個資料就要向右移一個位置, 使得 9 之後空出一個位置讓 15 填入, 最後得到 2 9 15 16 18 26 的排序結果 ( 如右圖 ) 69
17--1-1 插入排序法 如右圖將 8 25 1 49 0 五個整數資料依序放入陣列 D 中 一開始設定 I = 2,N = 5 將 D[I] 依排序順序插入 D[1] 至 D[I 1] 的資料群中, 完畢後將 I 加 1 重複上述動作, 直到 I >N 70
17--1-1 插入排序法 下圖是一個插入排序演算法 程式的 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
17--1-2 氣泡排序法 氣泡排序法 (Bubble Sort) 是利用相鄰資料兩兩相比而完成資料的排序 如果給了 N 個資料, 其排序過程分為 N 1 回合, 第 I 回合將第 I 大的資料像氣泡般的 浮現 " 至其排序的位置 如下圖將 8 49 25 49 1 五個整數資料依序放入陣列 D 中
17--1-2 氣泡排序法 用氣泡排序法將這五個資料由小到大排序好 首先要把最大者從左向右推到到 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: 1 2 4 5 8 49 25 0 1 8 49 25 0 1 8 25 49 0 1 8 25 0 49 1 8 25 0 1 49 不交換交換不交換不交換不
17--1-2 氣泡排序法 找出最大數後, 然後就要找出次大數並放於 D[4] 內 同樣的, 從 D[1] 開始, 讓兩個相鄰的資料相比, 把較大者放到右方, 而較小者放到左方 最後在 D[4] 內的 8 就是這五個資料的次大者 D: 1 2 4 5 8 25 0 1 49 25 8 0 1 49 25 0 8 1 49 25 0 1 8 49 交換 交換 交換
17--1-2 氣泡排序法 右圖是浮現第三大數的過程 相同的, 利用前述的方法可找出第三大數並放於 D[] 最後將 0 放於 D[] 內 D: 1 2 4 5 25 0 1 8 49 25 0 1 8 49 不交換 交換不 25 1 0 8 49 交換不
17--1-2 氣泡排序法 最後就是找出第四大數並放於 D[2] 內 之後陣列 D 的內容為 1 25 0 8 49, 是由小到大的順序 D: 1 2 4 5 25 1 0 8 49 1 25 0 8 49 交換不
17--1-2 氣泡排序法 下圖是一個氣泡排序演算法 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
17--1- 兩兩合併排序法 兩兩合併排序法 (2-Way Merge Sort) 是先將資料分成幾個排序好的串列, 然後把串列兩兩合併成更大的已排序串列, 直到合併成包含所有資料的已排序串列為止
17--1- 兩兩合併排序法 如右圖要排序 10 個整數資料 先分成 10 個只有一個資料的串列, 然後兩兩合併成擁有兩個資料的串列 接著又合併成有 4 個資料的串列, 依此做下去, 直到合併成包含 10 個資料的串列
17--1- 兩兩合併排序法 合併方法是將兩個已排序好的資料串列 A 與 B 合併成為一排序好的串列 C 其方法是分別從 A 和 B 中依小到大的順序取出第一數, 比較此二數, 將較小數放入 C 中, 並從較小數的來源串列中取出下一個數, 然後再與先前的較大數比較 如此比較及讀取資料下去, 直到有一方的資料都已放入 C 中, 最後將另一方未放入 C 內的資料依序放入 C
17--1- 兩兩合併排序法 如右圖, 陣列 A 和 B 的內容都是依小到大排序好的三個整數 現在我們要把這兩個資料串列合併到陣列 C 內, 還要保證陣列 C 的內容一樣是由小到大排序好的
17--1- 兩兩合併排序法 一開始比較 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 的索引指標向前推進
17--1- 兩兩合併排序法 再比較 A[2] 和 B[2] 因為 B[2] 較小, 所以將 B[2] 放入 C[]( 如圖 17.0), 陣列 B 及 C 的索引指標向前推進 然後比較 A[2] 與 B[], 此時 B[] 較小, 所以放入 C[4]( 如圖 17.1)
17--1- 兩兩合併排序法 現在陣列 B 的資料都已放入 C, 所以把 A[2] 和 A[] 依序放入 C ( 如圖 17.2) 最後完成合併陣列 A 與 B 於陣列 C
17--1- 兩兩合併排序法 下圖的演算法 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
17--2 搜尋 在一堆資料裏尋找某特定的資料謂之 搜尋 (Searching) 以下將陸續介紹 : 循序搜尋 二分搜尋 二元搜尋樹 等常用搜尋法
17--2 搜尋 循序搜尋 (Sequential Search) 又稱 線性搜尋 (Linear Search), 依據資料儲存順序從頭至尾尋找下去 如下圖, 陣列 D 中有六個整數資料 若要尋找的資料為 25, 從 D[1] 開始比對, 然後 D[2], 一直到 D[] 才找到 但如果要找的是 40, 就要經歷 D[1], D[2],..., D[6] 六次比對才找到
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
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 再與新搜尋範圍的中間數比對, 如此遞迴地搜尋下去
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 中
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
17--2- 二元搜尋樹 二元搜尋樹 (Binary Search Tree) 是二元樹的結構, 但是樹中的每一節點資料都不小於它的左孩子, 也不大於它的右孩子 將資料先存於此特殊的二元搜尋樹, 之後可利用此樹做資料的搜尋
17--2- 二元搜尋樹 若有 18 26 11 0 24 5 1 等七個整數資料, 我們依據輸入順序建立一二元樹 第一個輸入的數 18 當作樹根 ( 如圖 17.6) 接下來輸入的數從樹根的節點資料開始與之相比 若比節點資料大, 就再和其右孩子相比 ( 如果沒有右孩子, 就將新輸入的數當作其右孩子 ) 若比節點資料小, 就再和其左孩子相比 ( 如果沒有左孩子, 就將新輸 入的數當作其左孩子 ) 18 圖 17.6
17--2- 二元搜尋樹 圖 17.7 圖 17.8 圖 17.9 圖 17.40 圖 17.41 和圖 17.42 分別是輸入 26 11 0 24 5 和 1 後二元樹的變化 最後在圖 17.42 上得到的二元樹就是這七個資料的二元搜尋樹 18 18 26 11 26 圖 17.7 圖 17.8 18 18 18 11 26 11 26 0 24 0 圖 17.9 圖 17.40 18 11 26 1 24 0 11 26 24 0 圖 17.41 5 5 圖 17.42
17--2- 二元搜尋樹 假設搜尋的資料為 KEY, 從二元搜尋樹之樹根的節點資料開始與 KEY 相比 若相等, 就找到了 ; 若 KEY 比節點資料大, 而且此節點又沒有右孩子, 表示 KEY 不在資料內, 否則就再和其右孩子相比 ; 若比節點資料小, 而且此節點又沒有左孩子, 表示 KEY 不在資料內, 否則就再和其左孩子相比
17--2- 二元搜尋樹 例如在圖 17.42 的二元搜尋樹上找尋 KEY, 假設 KEY 為 1 開始時 KEY 與樹根 18 相比, 因為 KEY < 18, 所以再與其左孩子節點 11 相比 又因 KEY > 11, 再與節點 11 的右孩子節點 1 相比, 結果就找到了 KEY 的確在這些資料中 18 11 26 1 24 0 圖 17.4 2 5
17--2- 二元搜尋樹 但當 KEY=12 時, 開始與樹根 18 相比, 因為 KEY < 18, 所以再與其左孩子節點 11 相比 又因 KEY > 11, 再與節點 11 的右孩子節點 1 相比 因為 KEY < 1, 而且節點 1 又沒有左孩子, 表示 KEY 不在這些資料中 18 11 26 1 24 0 圖 17.4 2 5
17-4 演算法分析與策略 演算法 (Algorithm) 就是解決問題的方法 例如兩個整數相加的問題, 其演算法是先做個位數字的相加, 再做十位數字的相加, 接著是百位數, 依此類推 完整的演算法包括明確的輸出入資料和詳細且有限的執行步驟 98
17-4-1 算法分析 圖 17.4 描繪出在電腦上解決問題的基本架構 演算法以程式描述後在電腦上執行, 資料輸入至程式後, 經過程式對資料的運算, 最後產生解答 資料 演算法 ( 程式 ) 圖 17.4 解答 99
17-4-1 算法分析 假設演算法 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
17-4-1 算法分析 而演算法 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
17-4-1 算法分析 時間複雜度常用 階次 (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 2 + 10N 2N 2 稱 N 2 為 N 2 + 10N 的漸進上限 102
17-4-1 算法分析 接著介紹 Ω 階次 若存在某固定正變數 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
17-4-1 算法分析 若 g (n) = O ( f (n)) 且 g (n) = Ω ( f (n)), 則稱 f (n) 為 g (n) 的 真正階次 (Exact Order), 記為 g (n) = θ ( f (n)) 104
17-4-1 算法分析 表 17.1 顯示多種 f (n) 函數的數值, 當 n 足夠大時,2 n > n > n 2 > nlogn > n > logn n 1 2 4 8 16 2 64 128 256 512 f(n) 2 n n n 2 nlogn n logn 2 1 1 0 1 0 4 8 4 0.602059991 2 0.01029996 16 64 16 2.40829965 4 0.602059991 256 512 64 7.224719896 8 0.90089987 6556 4096 256 17-26591972 16 1.20411998 4294967296 2768 1024 48.1647991 2 1.505149978 1.84467E+19 262144 4096 115.595518 64 1.806179974.40282E+8 2097152 1684 269.7228761 128 2.10720997 1.15792E+77 16777216 6556 616.509411 256 2.40829965 1.408E+154 14217728 262144 187.14622 512 2.709269961 105
17-4-1 算法分析 如果 f (n) = c p (n), 其中 c 為常數,p (n) 為 n 的 多項式函數 (Polynomial Function) ( 如 n, n 2 + 10, log 2 n, nlog 2 n), 則稱 f (n) 為 指數函數 (Exponential Function) 例如 2 n n 4 logn 等函數都是指數函數 因為指數函數的數值上升速度相當快, 所以時間複雜度為指數函數階次的演算法, 在資料量足夠多時, 需要相當長的時間才能解得答案 106
17-4-1 算法分析 若演算法的時間複雜度是 O (p (n)), 其中 p (n) 為 n 的多項式函數, 則稱此演算法為 多項式時間演算法 (Polynomial-Time Algorithm) 若問題 P 能用多項式時間演算法解得答案, 則問題 P 就能用電腦在合理時間內求得答案, 在電腦上是 可解 (Tractable) 的問題 例如排序及搜尋等問題就是此類問題 107
17-4-1 算法分析 表 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
17-4-1 算法分析 若可解問題 P 的演算法 A 的時間複雜度為 t, 而解問題 P 的演算法最少需要 t 時間, 則稱演算法 A 是解問題 P 的 最佳演算法 (Optimal Algorithm) 像排序 n 個數的問題已證明在 比較與交換模式 (compare-and-exchange model) 下最少需要 Ω (nlog 2 n) 時間, 而兩兩合併排序法的時間複雜度也是 O (nlog 2 n), 所以兩兩合併排序法是最佳排序演算法 109
17-4-1 算法分析 若問題 P 到目前為止仍無法以多項式時間演算法解得答案, 也就是無法於電腦上在合理時間內求得答案, 我們稱問題 P 為 難解問題 (Intractable Problem) 有許多的應用問題是屬於這類的問題, 舉例說明如下 : 1. 旅行推銷員問題 (Travelling Salesman Problem) 有各城市間的公路交通圖, 請找出一條從某城市出發, 經過每個城市一次再回到該城市的最小長度的交通路線 110
17-4-1 算法分析 2. 圖形塗色問題 (Graph-Coloring Problem) 給一由頂點 (Vertex) 及邊 (Edge) 構成的圖形, 在有邊相連的兩頂點不能有相同顏色的限制下來對頂點塗色, 請問所需的顏色個數最少是多少?. 裝箱問題 (Bin-Packing Problem) 有 n 個不可分解的貨物, 其大小分別為 S 1,..., S n, 0 < S i 1, 若每個箱子的容量為 1, 請問將這 n 個貨物放入箱子內所需的最小箱子個數為何? 111
17-4-1 算法分析 目前要找出難解問題的 真正解答 (exact solution) 是相當耗時的, 因為目前還沒有人能提出在當今電腦架構下任何快速的演算法以求得真正解答 然而有些難解問題是能以多項式時間演算法求得接近解答的 逼近解 (approximate solution) 112
17-4-2 個別擊破策略 個別擊破策略 (Divide-and-Conquer Method) 的主要精神是將原來的問題 P 分解成 2 個或多個子問題, 待個別解決這些子問題後再經由 合併 (Merge) 處理, 整理出原來問題的答案, 而分割後的子問題是資料量較小的問題 P 因此在解子問題時又可遞迴應用上述的方法, 經由分割及合併的過程得到解答 前一章介紹的二分搜尋法就是採用個別擊破策略 11
17-4-2 個別擊破策略 兩兩合併排序法也可視為是個別擊破的策略 如圖 17.44 所示, 一開始就將資料分割成兩部分處理, 然後再遞迴細分各資料直至不能細分為止, 接著就兩兩合併成排序的序列, 慢慢的將分割的資料合併成排序的序列, 最後得到所有資料的排序結果 10 6 27 17 2 4 5 56 10 6 27 17 2 4 5 56 10 6 27 17 2 4 5 56 10 6 27 17 2 4 5 56 6 10 17 27 4 2 56 5 6 10 17 27 4 5 2 56 分割分割分割合併合併合併 4 5 6 10 17 27 2 56 圖 17.44 114
17-4-2 個別擊破策略 讓我們回到排序的問題上 假設陣列 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
17-4-2 個別擊破策略 接著介紹如何將 4 放到 D[4] 及將小於 4 的數集中在 D[1] 至 D[] 內, 而大於 4 的數則集中在 D[5] 至 D[7] 內 116
17-4-2 個別擊破策略 令 i = 2,j = 7 從 D[i] 開始向右找到第一個比 D[1] 大的數, 以 i 紀錄其陣列的索引 從 D[ j] 開始向左找到第一個不大於 4 的數, 以 j 紀錄其陣列索引 117
17-4-2 個別擊破策略 若 i < j, 則交換 D[i] 與 D[ j] 的內容, 並繼續前述的左右搜尋 ; 若 i j, 則交換 D[1] 與 D[ j] 的內容, 並停止搜尋 118
17-4-2 個別擊破策略 雖然快速排序法的最差時間複雜度為 O (n 2 ) ( 其中 n 為資料個數 ), 因為其一般狀況時間複雜度為 O (nlog 2 n), 還是相當實用的排序方法 119
17-4- 貪婪策略 貪婪策略 (Greedy Method) 常用來解決 最佳化問題 (Optimization Problem) 貪婪法是最直接的解法, 每次的決策都是朝向目前 最好 " 的方向前進, 而且不回頭 120
17-4- 貪婪策略 舉例來說, 某一個銀行出納櫃檯要服務 n 個顧客, 銀行的目標是希望顧客在櫃檯等待的平均時間要最少 解決之道是每次都從尚未服務的顧客中, 選擇需要服務時間最短的顧客來服務, 如此就可達到預期目標 像這樣每次都選擇最小服務時間的策略就是一種貪婪策略 121
17-4- 貪婪策略 假設有 5 個顧客 A, B, C, D, E 幾乎同時到達銀行櫃檯, 其所需服務時間如表 17. 根據貪婪演算法, 銀行櫃檯將依序服務 B, D, E, C, A 顧客在櫃檯等待的平均時間為 [1 + (1 + 2) + (1 + 2 + ) + (1 + 2 + + 4) + (1 + 2 + + 4 + 5) ] / 5 = 7 顧客所需服務時間 A 5 B 1 C 4 D 2 E 122
17-4- 貪婪策略 再介紹一個可用貪婪策略解決的 背包問題 (Knapsack Problem) 假設有多個可分解的物件和一只限重 W 的背包, 每件物件有其重量及其被選取放入背包內的利益 請問要如何將物件放進背包內而使得獲得的利益最大? 解決的方法是每次在限重的情形下, 選取尚未放入的物件中擁有最大的利益與重量的比值之物件放入背包內 12
17-4- 貪婪策略 設背包限重 100, 有 A, B, C, D, E 共五個物件, 其資料如表 17.4 物件重量利益利益 / 重量 A 10 20 2.0 B 20 0 1.5 C 0 66 2.2 D 40 40 1.0 E 50 60 1.2 124
17-4- 貪婪策略 因為物件 C 的利益 / 重量最高, 所以將物件 C 放入背包內, 此時背包的重量為 0 物件個數累計利益重量 C 1 66 0 125
17-4- 貪婪策略 接著從物件 A, B, D, E 中挑出其利益 / 重量最高的物件 A 放入背包內, 這時背包的重量為 0+10=40 物件個數累計利益重量 C 1 66 0 A 1 86 40 126
17-4- 貪婪策略 接下來, 從物件 B, D, E 中挑出其利益 / 重量最高的物件 B 裝入背包內, 之後背包的重量為 40 + 20 = 60 物件 個數 累計利益 重量 C 1 66 0 A 1 86 40 B 1 116 60 127
17-4- 貪婪策略 再從剩下的物件 D 和 E 中選出其利益 / 重量最高的物件 E 由於物件 E 整個放入背包內會超過重量 100, 所以物件 E 只能放入 0.8 個 物件 個數 累計利益 重量 C 1 66 0 A 1 86 40 B 1 116 60 E 0.8 164 100 表 17.5 128
17-4- 貪婪策略 放入以後得總重量為 60 + 50 0.8 = 100 最後得到的利益為 66 + 20 + 0 + 60 0.8 = 164 物件裝入背包的情形整理於表 17.5 物件 個數 累計利益 重量 C 1 66 0 A 1 86 40 B 1 116 60 E 0.8 164 100 表 17.5 129
17-4- 貪婪策略 接著介紹 最小擴展樹 (Minimum Spanning Tree) 問題 圖 17.47 是由 頂點 (Vertex) 及 邊 (Edge) 構成的圖形, 其中圓圈代表頂點, 連接兩頂點的線為邊, 而且每個邊都有非負 (nonnegtive) 的 加權 (Weight) ( 例如頂點 V 與頂點 V 5 間的邊之加權為 5) 4 V 1 V 2 6 1 7 V 5 5 2 V 4 V 8 10
17-4- 貪婪策略 由於圖 17.47 的邊都無方向, 稱圖 17.47 的圖形為 無向圖 (Undirected Graph) V 1 6 1 7 V 4 4 V 5 5 8 V 2 V 2 11
17-4- 貪婪策略 定義無向圖的 路徑 (Path) 為頂點的序列, 其中序列裡每個頂點與其後一個頂點之間必有邊相連 例如圖 17.47 中 [V 1, V 5, V 2 ] 是一條從頂點 V 1 到頂點 V 2 的路徑 4 V 1 V 2 6 1 7 V 5 5 2 V 4 V 8 12
17-4- 貪婪策略 若無向圖的任兩頂點都存在一條路徑, 則稱此圖為 聯通圖 (Connected Graph) 例如圖 17.47 就是聯通圖 從某頂點出發回到該頂點的路徑稱為 迴圈 (Cycle) 例如圖 17.47 的 [V 1, V 5, V 2, V 1 ] 路 6 徑就是迴圈 一個沒有迴圈的圖形稱為 無迴圈圖 (Acyclic Graph) 4 V 1 1 7 V 5 5 V 4 8 V 2 V 2 1
17-4- 貪婪策略 定義 樹 (Tree) 為聯通的無迴圈圖 若圖形 G 的頂點所成的集合為 V, 邊所成的集合為 E, 以 G = (V, E) 表示圖形 G 定義圖形 G = (V, E) 的 擴展樹 (Spanning Tree) T = (V, E) 是包括所有 G 的頂點的樹, 其中 E' 是 E 的子集合 例如圖 17.48 (a) 及 (b) 都是圖 17.47 的擴展樹 V 1 6 1 7 V 4 V 1 6 1 7 V 4 V 5 5 8 V 5 5 V 2 2 V 圖 17.48 14 V 2 2 V
17-4- 貪婪策略 接著介紹以貪婪策略設計的 Kruskal 演算法 假設要求圖形 G = (V, E) 的最小擴展樹 此演算法依據邊的加權由小到大的順序考慮該邊是否為最小擴展樹的邊 若邊 e 加入後不會產生迴圈, 則邊 e 為最小擴展樹的一員 ; 反之, 邊 e 就不是最小擴展樹的一員 如此重複直到建構出最小擴展樹 詳細的步驟分述於下 : 15
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
17-4- 貪婪策略 用 (a, b) 表示頂點 a 與頂點 b 的邊 以找圖 17.47 的最小擴展樹為例, 將圖 17.47 的邊依加權排序後得 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
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 1 1 6 V 4 V 5 V 2 2 V (g) 加入 (V 1, V 4 ) 18
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 1 1 6 V 4 V 5 V 2 V 2 (g) 加入 (V 1, V 4 ) 19
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 1 1 6 V 4 V 5 V 2 2 V (g) 加入 (V 1, V 4 ) 140
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 1 1 6 V 4 V 5 V 2 V 2 (g) 加入 (V 1, V 4 ) 141
17-4- 貪婪策略 而後因 e 6 = (V 1,V 4 ) 加入 T 後不產生迴圈, 所以將 (V 1,V 4 ) 加入 T 中 ( 圖 17.49(g)) 此時 T 為 G 的擴展樹, 停止演算法 最後得到的圖 17.49(g) 就是圖 17.47 的最小擴展樹 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
17-4- 貪婪策略 接著介紹 最短路徑問題 (Shortest Path Problem) 下圖是 S A B T 四個地點的交通路線, 各路線分別標上距離 : 10 15 S 40 A 0 B 60 T 25 50 20 14
17-4- 貪婪策略 假設要求從 S 到 T 的最短路徑長度 令 D (a, b) 表示從 a 到 b 的最短路徑長度 從上圖, 可知 D (S, T) = D (S, A) +D (A, B) +D (B, T) = 10 + 15 + 20 = 45 如此只要利用貪婪策略就能得到答案 但是此貪婪策略並不適用於所有的最短路徑問題 144
17-4- 貪婪策略 例如要找下圖的 D (S, T ), 則 D (S, T ) = 24 + 20 = 44, 此結果不等於 D (S, A) + D (A, B) + D (B, T) = 45 10 15 S 40 A 0 B 60 T 25 50 20 24 圖 17.51 145
17-4-4 動態規劃 先前介紹的個別擊破策略是遞迴地將問題分成較小的問題後分別求得解答, 然後合併每個小部分的答案成為完整的答案, 是屬於由上至下 (Top- Down) 的計算策略 例如要計算下面的 Fibonacci 函數 f (n): f (0) = 0 f (1) = 1 f (n) = f (n 1) + f (n 2), n 2 146
17-4-4 動態規劃 若要計算 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) 圖 17.52 其中 f (), f (2), f (1), f (0) 被重複計算許多次, 如果能先依序將 f (0), f (1),f (2), f (), f (4) 的結果計算出來並儲存於表格或陣列, 就可避免重複計算, 增進計算速度 147
17-4-4 動態規劃 以陣列 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
17-4-4 動態規劃 二項式係數 (Binomial Coefficient) 的定義為 當 n, k 的值不小時,n! 及 k! 是很大的天文數字, 非常難計算 修改此定義, 重新以遞迴關係定義於下: 149
17-4-4 動態規劃 陣列 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
17-4-4 動態規劃 接下來介紹有向圖的 最短路徑問題 (Shortest Path Problem) 下圖是一個 有向的 (Directed) 且加權的的圖形, 其中圓圈代表頂點, 而連接兩頂點的線稱為邊 2 1 V 1 V 4 V 2 1 5 6 7 4 V 151
17-4-4 動態規劃 每個邊都有方向也有對應的非負的加權, 例如有一個從頂點 V 1 至頂點 V 2 的邊, 其加權為 1 路徑是一個頂點序列, 其中序列裡每個頂點到其後一個頂點的邊一定存在 例如 [V 1, V, V 2 ] 就是一條從頂點 V 1 至頂點 V 2 的路徑 2 V 2 1 4 1 V 1 5 6 V 152 7 V 4
17-4-4 動態規劃 設定路徑的長度為路徑上所有的邊的加權的和 例如路徑 [V 1, V, V 2 ] 的長度為 6 + 4 = 10 假設邊的加權不為負數, 最短路徑問題是要去找出在有向及加權的圖形上任兩頂點的最短路徑 2 V 2 1 1 V 1 5 6 7 V 4 4 V 15
17-4-4 動態規劃 假設圖形有 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
17-4-4 動態規劃 經過集合 {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
17-4-4 動態規劃 對圖 17.59 的圖形求最短路徑, 計算過程的 d 0, d 1,, d 4 表格列於圖 17.54 d 0 1 2 4 d 1 1 2 4 1 0 1 6 2 1 0 1 6 2 2 1 0 2 1 0 7 5 4 0 5 4 0 7 4 7 0 4 4 7 0 156
17-4-4 動態規劃 d 2 1 2 4 d 1 2 4 1 0 1 6 2 1 0 1 6 2 2 1 0 7 2 1 0 7 5 4 0 7 5 4 0 7 4 4 7 0 4 4 7 0 d 4 1 2 4 1 0 1 6 2 2 1 0 7 5 4 0 7 4 4 7 0 157
17-4-4 動態規劃 假設 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