Microsoft PowerPoint - ALGOY96CH04 [相容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - ALGOY96CH04 [相容模式]"

牺巩印
5 years ago
Views:

1 演算法方式總覽 1. The Divide-and-Conquer Strategy ( 各個擊破 ) (binary Searching Quick Sort. ) 2. The Greedy Method( 貪婪演算法 ) (Prim MST Kruskal MST Djikstra's algorithm) 3. Dynamic Programming( 動態演算法 ) ( 二項式係數矩陣連乘最佳二元搜尋樹 ) 4. Trace Back ( 回溯 ) ( 圖形著色漢米爾迴路 ) 5. Branch-and-Bound ( 樹的追蹤 ) 1

2 CH4 The Divide-and-Conquer Strategy ( 各個擊破 ) 2

3 各個擊破演算法簡介 1. 將ㄧ個問題切成兩個或以上的較小問題, 分別來解決 2. 如果較小的問題可以被解決的, 即原問題的解可以藉由合併小問題的答案獲得 3. 是一種由上而下 (top-down) 的解題方式 4. 類似遞迴程式的方法解決問題 3

4 Divide-and-Conquer 問題介紹 1. 二元搜尋法 2. 合併搜尋法 3. Divide-and-conquer 技巧 4. 快速排序法 ( 分割交換排序法 ) 5. strassen 的矩陣相乘演算法 6. 大整數的計算 7. 何時不能使用 Divide-and-Conquer 4

5 Recursive( 遞迴 ) 1. 一個副程式或函數重複的呼叫自己本身, 稱為遞迴 (Recursive) 2. 利用遞迴解決問題, 既經濟又方便 3. 可用遞迴來解決的問題, 那它也一定可轉成利用非遞迴的方式解決之 4. 撰寫遞迴時, 千萬小心, 一定要有一個結束點, 否則後果嚴重 5. 遞迴在執行時, 會藉助堆疊將呼叫本身函數的下一個敘述位址儲存起來, 待執行完結束點後, 再將堆疊的資料一一的彈出來處理 5

6 遞迴設計步驟 1. 發展從一個或多個較小實例的解中得到較大實例的解之方式 2. 決定分割為較小實例的終止條件 3. 決定終止條件時的解 6

7 階乘求 n!, 一般可能用的規則 : n! = n * (n-1)!; 利用迴圈 : ans = 1; for (i = 2; i <= n; i++) ans = ans * i; 利用遞迴 : int fact(int n) { int x, y; if (n == 0) return(1); x = n-1; y = fact(x); return(n*y); } /* end fact */ // boundary condition 7

8 遞迴呼叫流程圖 n=4 int fact(int n) { int x, y; if (n == 0) // boundary condition return(1); x = n-1; y = fact(x); return(n*y); } /* end fact */ fact(4) y=fact(3) n=3 Fact(3)=6 fact(3) y=fact(2) n=2 n=1 n=0 Fact(2)=2 fact(2) y=fact(1) Fact(1)=1 fact(1) y=fact(0) Fact(0)=1 fact(0) Return(1) Fact(4)=24 8

9 遞迴呼叫流程圖練習 :fact(5) 的呼叫過程, 遞迴呼叫流程圖為何? n=5 int fact(int n) { int x, y; if (n == 0) // boundary condition return(1); x = n-1; y = fact(x); return(n*y); } /* end fact */ 9

10 遞迴推疊圖 (The recursive stack) 呼叫過程 : f4 f3 f2 f1 f0 10

11 N x y (i)printf( %d, fact(3)) The stack at various times during execution. (An asterisk indicates an uninitialized value.) 11

12 12

13 費氏數列費氏數列 (Fibonacci number): f(0) = 0;* f(1) = 1; f(2) = f(1) + f(0); f(3) = f(2) + f(1); : f(n) = f(n-1) + f(n-2); 利用遞迴範例 : int fib(int n) { int x, y; if (n <= 1) return(n); x = fib(n-1); y = fib(n-2); return(x+y); } /* end fib */ 13

14 fib(4) x=fib(3) n=3 fib(3)=2 fib(3) x=fib(2) 遞迴呼叫流程圖 n=2 fib(2)=1 fact(2) x=fib(1) y=fact(0) n=1 fib(1)=1 n=0 fib(0)=0 fib(1) Return(1) fib(0) Return(0) y=fib(1) n=1 fib(1)=1 fib(1) Return(1) n=4 y=fib(2) fib(4)=3 n=2 fib(2)=1 fact(2) x=fib(1) y=fact(0) n=1 fib(1)=1 n=0 fib(0)=0 fib(1) Return(1) fib(0) Return(0) int fib(int n) { int x, y; if (n <= 1) return(n); x = fib(n-1); y = fib(n-2); return(x+y); } /* end fib */ 14

15 遞迴推疊圖 (The recursive stack) 呼叫過程 : f4 f3 f2 f2 f1 f1 f0 f1 f0 15

16 遞迴推疊圖練習 :fib(5) 的呼叫過程, 請用樹狀結構來表示 n=5 int fib(int n) { int x, y; if (n <= 1) return(n); x = fib(n-1); y = fib(n-2); return(x+y); } /* end fib */ 16

17 遞迴推疊圖呼叫過程 : f5 f4 f3 f3 f2 f2 f1 f2 f1 f1 f0 f1 f0 f1 f0 17

18 18

19 19

20 何時不要使用遞迴? 遞迴雖然可以使用少數幾行的敘述就可以解決一些複雜的問題, 但有些問題會使用更多的執行時間以費氏數列為例 : 遞迴之複雜度為 O(2 n ), 而迴圈只要 O(n) 約需時 2 n/2 20

21 小結以階乘為例 : 無論使用遞迴或迴圈, 複雜度階為 O(n) 但遞迴需要較大的記憶體空間由於非遞迴使用了較多的區域變數 (local variable), 所以直覺上似乎遞迴會較好. 然而因為遞迴使用了更多的時間存放暫時的結果, 所以實際上遞迴可能花更多時間結論 : 1. 執行過程像一棵灌木 1.1 重複動作太多的, 如 : 費氏數列, 不適用遞迴 1.2 若重複動作很少時, 如 :N 個皇后, 則適用遞迴 2. 執行過程不像灌木, 而是一直線的前進與後退, 如 : 階乘, 亦不適用遞迴 3. 以迴圈會使程式困難設計時, 可考慮用遞迴 21

22 A general divide-and-conquer algorithm Step 1: If the problem size is small, solve this problem directly; otherwise, split the original problem into 2 sub-problems with equal sizes. Step 2: Recursively solve these 2 sub-problems by applying this algorithm. Step 3: Merge the solutions of the 2 subproblems into a solution of the original problem. 22

23 各個擊破演算法設計步驟 1. 分割 (Divide) 一個較大問題實例成為一個或多個較小的實例 2. 解出每個較小實例的答案 (Conquer), 除非實例已經分割到足夠小的地步, 否則使用遞迴來解 3. 必要的話, 將兩個較小實例的解答合併 (Combine) 以獲得原始問題實例解答 23

24 二元搜尋法 (Binary Search) 二元搜尋是應用於已排序好的資料, 每次取所選定範圍資料的中位數 (middle) 來做比較 24

25 二元搜尋法方法假設串列依鍵值大小排列, 使得 list[0].key <= list[1].key <=...<= list[n-1].key 此法是由比較 searchnum 和 list[middle] 開始, 其中 middle = ( n-1 ) / 2 其搜尋的結果可能有三種 1. searchnum = list[middle].key 在此種情形下, 搜尋成功地結束 2. searchnum < list[middle].key 此種情況, 放棄介於 list[middle] 和 list[n-1] 之間的記錄, 繼續搜尋介於 list[0] 和 list[middle - 1] 之間的記錄 3. searchnum > list[middle].key 此種情況, 放棄介於 list[0] 和 list[middle] 之間的記錄, 繼續搜尋介於 list[middle+1] 和 list[n - 1] 之間的記錄 25

26 ( 二元 ) 設計步驟 1. 分割待搜尋陣列 2. 利用判斷尋找值是否位於這個子陣列中, 使用遞迴方式來完成, 由分割子陣列的解答求得 1. 分割 (Divide) 大實例成為多個小實例 2. 解小實例 (Conquer) 可能再遞迴, 至分割到足夠小的地步 3. 合併 (Combine) 小實例的解答以獲得大實例解答 26

27 二元搜尋法 ( 遞迴版 ) 27

28 28

29 最差情況的時間複雜度 ( 二元搜尋法, 遞迴版 ) 基本運算 :x 與 S[mid] 的比較輸入大小 :n, 陣列中的項目數量 O(n)=logn 29

30 合併排序法 Two-way merging 1. 指的是將兩個已排序的陣列合併成一個已排序的陣列 2. 構想為將兩個或兩個以上已排序好的檔案, 合併成一個大的已排序好的檔案 3. 而在一維陣列的資料中, 我們可以首先將資料分為兩個兩個一組, 每組排序好後再合併為四個四個一組, 然後再八個八個一組, 依此類推 Input 第 1 回合第 2 回合第 3 回合

31 設計步驟 1. 分割待排序陣列成為兩個具有 n/2 個項目的子陣列 2. 藉由排序以解答每個子陣列, 除非陣列夠小, 否則使用遞迴方式來完成 3. 將子陣列合併成一個已排序的陣列以合併子陣列的解答 1. 分割 (Divide) 大實例成為多個小實例 2. 解小實例 (Conquer) 可能再遞迴, 至分割到足夠小的地步 3. 合併 (Combine) 小實例的解答以獲得大實例解答 31

32 合併排序 32

33 33

34 合併 34

35 35

36 最差情況的時間複雜度 ( 合併 ) 基本運算 : 比較 U[i] 與 V[ j ] 輸入大小 :h 與 m, 分別為兩輸入陣列的項目個數 W(h,m) 為 merge() 的時間複雜度 W(h,m)=h+m+1 36

37 最差情況的時間複雜度 ( 整個合併排序 ) 基本運算 : 發生在 merge 中的比較輸入大小 :n, 陣列 S 中的項目個數 W(n): mergesort() 的複雜度 W(n)= W(h) + W(m) + h+m-1 = 將 U 排序所花的時間 + 將 V 排序所花的時間 +U 與 V 合併所花的時間 37

38 38

39 遞迴方程式範例 B.19 T(n) = T(n/2) +n-1 T(1) = 0 Let n = 2 k, t k = T(2 k ) t k = 2t k k -1 39

40 general solution: t k = c 1 +c 2 2 k +c 3 k2 k let T(2 k )=t k, n=2, lg n = k T(n) = c 1 +c 2 n +c 3 nlg n Initial condition: T(1)=0, T(2)=1, T(4)=4, T(n) = nlg n (n-1) 40

41 定理 B.3 非同質線性遞迴方程式 a 0 t n + a 1 t n a k t n-k = b n p(n) 轉換成同質線性遞迴方程式, 具特徵方程式 (a 0 r k + a 1 r k a k r )(r-b) d+1 = 0 d 為 p(n) 的次數 41

42 t k = 2t k k -1 t k - 2t k-1 = 2 k -1 b=2,d=0 for 2 k, b=1,d=0 for 1 (1r-2) (r-2) 0+1 (r-1) 0+1 = (r-1) (r-2) 2 t k = c 1 1 k +c 2 2 k +c 3 k2 k 42

43 快速排序 (Quicksort) 1. 又稱為劃分交換排序 (partition exchange sorting) 2. 就平均時間而言, 快速排序是所有排序中最佳的 3. O(n log n); 不穩定性排序 43

44 快速排序 44

45 樞紐 (pivot) 45

46 分割 46

47 分割 47

48 樞紐 48

49 分割時間複雜度 (Partition) 1. 基本運算 : 發生在 merge 中的比較 2. 輸入大小 :n=high-low+1, 也就是在子陣列中的項目數因為除第一個項目外, 每個項目都會被比較 T(n)=n-1 因此我們使用 n 來代表子陣列的大小而非陣列 S 的大小只有當 partition 在最上層被呼叫時, 它才代表 S 的大小 49

50 快速排序最差情況的時間複雜度 (QuickSort) 基本運算 : 在 paritition 副程式中,S[i] 與 pivotitem 的比較輸入大小 :n, 陣列 S 中的項目數是 QuickSort 的最差情況 (Big O) 50

51 平均情況的時間複雜度 ( 快速排序 ) 基本運算 : 在 paritition 副程式中,S[i] 與 pivotitem 的比較輸入大小 :n, 陣列 S 中的項目數 51

52 練習 1. finding the maximum of a set S of n numbers 2. 給下列陣列 S, 請用各個擊破演算法設計找出最大的數 3. 29,14,15,1,6,10,32,12 52

53 設計步驟 1. 分割待排序陣列成為兩個具有 n/2 個項目的子陣列 2. 藉由排序以解答每個子陣列, 除非陣列夠小, 否則使用遞迴方式來完成 3. 將子陣列的答案比較找出一個最大數以合併子陣列的解答 1. 分割 (Divide) 大實例成為多個小實例 2. 解小實例 (Conquer) 可能再遞迴, 至分割到足夠小的地步 3. 合併 (Combine) 小實例的解答以獲得大實例解答 53

54 練習結果 54

55 Time complexity Time complexity: T(n)= 2T(n/2)+1 1 Calculation of T(n):, n>2, n 2 Assume n = 2 k, T(n) = 2T(n/2)+1 = 2(2T(n/4)+1)+1 = 4T(n/4)+2+1 : =2 k-1 T(2)+2 k =2 k-1 +2 k =2 k -1 = n-1 55

56 一般的矩陣相乘演算法 void mul(int a[ ][ ], int b[ ][ ], int c[ ][ ], int n) { int i, j, k, sum; for (i=0; i < n; i++) for (j=0; j < n; j++) { sum = 0; for (k=0; k < n; k++) sum = sum+a[i][k]*b[k][j]; c[i][j] = sum; } } 矩陣相乘 O(n 3 ) Strassen 將較大矩陣分成較小矩陣進行乘法運算在大矩陣相乘時, 複雜度比直接矩陣相乘的 O(n 3 ) 好 56

57 Strassen 矩陣相乘設計 2x2 矩陣,C=A*B c 11 c 12 = a 11 a 12 * b 11 b 12 c 21 c 22 a 21 a 22 b 21 b 22 Strassen 法需要 7 次乘法,18 次加法 / 減法. 直接法需要 8 次乘法,4 次加法 / 減法. 57

58 C = m 1 + m 4 - m 5 +m 7, m 3 + m 5 m 2 + m 4, m 1 + m 3 - m 2 +m 6 m 1 = (a 11 + a 22 )(b 11 + b 22 ) m 2 = (a 21 + a 22 )b 11 m 3 = a 11 (b 12 - b 22 ) m 4 = a 22 (b 21 - b 11 ) m 5 = (a 11 + a 12 )b 22 m 6 = (a 21 - a 11 )(b 11 + b 12 ) m 7 = (a 12 - a 22 )(b 21 + b 22 ) 58

59 nxn 矩陣,C=A*B C 11 C 12 = A 11 A 12 * B 11 B 12 C 21 C 22 A 21 A 22 B 21 B 22 59

60 C = M 1 + M 4 - M 5 +M 7, M 3 + M 5 M 2 + M 4, M 1 + M 3 - M 2 +M 6 M 1 = (A 11 + A 22 )(B 11 + B 22 ) M 2 = (A 21 + A 22 )B 11 M 3 = A 11 (B 12 - B 22 ) M 4 = A 22 (B 21 - B 11 ) M 5 = (A 11 + A 12 )B 22 M 6 = (A 21 - A 11 )(B 11 + B 12 ) M 7 = (A 12 - A 22 )(B 21 + B 22 ) 60

61 nxn 矩陣,C=A*B C 11 C = C 21 C M 1 =

62 Strassen 演算法 62

63 Strassen的時間複雜度分析基本運算一個基本的乘法輸入大小 n 也就是這些矩陣的列數與欄數 T(n) = 7T(n/2) 當n>1且n為2的乘冪時 T(1) = 1 T(n) = nlg 7 n2.81 (n2.81) 63

64 大整數的乘法 567,832 = 567x 位數 3位數 3位數 9,423,723 = 9423x 位數 4位數 3位數 u = x 10m + y n位數 n/2 位數 n/2 位數 m= n/2 u = x 10m + y, v = w 10m + z uv = (x 10m + y)(w 10m + z) = xw 102m + (xz+wy) 10m + yz 64

65 大整數乘法 65

66 最差情況的時間複雜度(大整數的乘法) 基本運算當相加相減或執行時一位數字(以十進位表示)的操作輸入大小也就是兩個大整數u v的位數 66

67 何時不能使用Divide-and-Conquer 1. 一個大小為n的個體被分成兩個或更多大小接近n的個體 2. 一個大小為n的個體被分成n個大小為 n/c的個體其中c為常數參考何時不要使用遞迴 P13 67

<5B BECBB0EDB8AEC1F25D312D34B0AD5FC3E2BCAEBCF6BEF7C0DAB7E F31702E504446>

<5B BECBB0EDB8AEC1F25D312D34B0AD5FC3E2BCAEBCF6BEF7C0DAB7E F31702E504446> : 2 = 3 4? 0 an ordered set of unambiguous, executable steps that produces a result and terminates in a finite time (computational theory) ( ) 5 6 (C-) int min, max; float degree, b; char ch, token; /,,,