Phân tích thiết kế thuật giải - Giải thuật đệ quy

GIẢI THUẬT ĐỆ QUY TS. NGÔ QUỐC VIỆT 2015 PHÂN TÍCH THIẾT KẾ GIẢI THUẬT Nội dung Ngô Quốc Việt 2 1. Giới thiệu 2. Các giải thuật đệ quy 3. Bài tập 4. Hỏi đáp. Giới thiệu Ngô Quốc Việt 3  Chương trình đệ quy là chương trình gọi đến chính nó.  Cần phải có điểm dừng chương trình/hàm (trường hợp suy biến)  Đệ quy tuyến tính  Đệ quy nhị phân  Đệ quy phi tuyến, đệ quy lồng  Đệ quy hỗ tương Thiết kế giải thuật đệ quy Ngô Quốc Việt 4  Tham số hoá bài toán.  Phân tích trường hợp chung (biểu diễn bài toán đồng dạng nhưng khác phạm vi hay kích thước giải quyết).  Xác định trường hợp dừng (suy biến) Tại sao dùng đệ quy Ngô Quốc Việt 5  Ưu điểm: giải thuật đệ quy đơn giản hơn không đệ quy khi giải quyết cùng một vấn đề => dễ thiết kế, hiểu, cài đặt và thay đổi.  Nhược điểm : gọi hàm liên tục (tốn nhiều thời gian và không gian bộ nhớ trong) Trong đó, vấn đề chủ yếu phát sinh do số lần gọi hàm có tham số, dẫn đến cần không gian lưu trữ trong stack. Khi nào dùng đệ quy Ngô Quốc Việt 6  Dùng đệ quy để thiết kế giải thuật khi muốn đơn giản về hình thức so với cách viết thông thường.  Thường được áp dụng cho các hàm có yếu tố lặp lại với ngữ cảnh thay đổi.  Kiểm tra nếu nó không sử dụng quá nhiều bộ nhớ trong. Một số ngôn ngữ (LISP, Scheme) sử dụng đệ quy để tạo vòng lặp, nhưng tiến hành theo cách hiệu quả (dạng tail recursion) Đệ quy tuyến tính Ngô Quốc Việt 7  Lời gọi đệ quy chỉ được gọi một lần trong hàm.  Ví dụ tính: 𝑎𝑛 = 𝐴 𝑛 = 0 𝑛 2 𝑎𝑛/2 𝑛 > 0, 𝑛 𝑐ℎẵ𝑛 3𝑛 + 1 𝑎𝑛−1 𝑛 > 0, 𝑛 𝑙ẻ int CalAn(int A, int n) { if(n==0) return A; else if(n > 0 && (n %2) ==0) return (n/2)*CalAn(A, n/2); else return (3*n+1)*CalAn(A, n-1); } Đệ quy nhị phân Ngô Quốc Việt 8  Lời gọi đệ quy chỉ được gọi hai lần trong hàm. int fiBo(int n) { long res, fn_1, fn_2; if(n <= 1) return 1; else { fn_1= fiBo(n-1); fn_2= fiBo(n-2); res = fn_1+fn_2; } return res; }  Đệ quy tuyến tính là trường hợp đặc biệt của đệ quy nhị phân  Ứng dụng để cài đặt giải thuật “chia để trị” Đệ quy lồng Ngô Quốc Việt 9  Lời gọi hàm đệ quy được gọi trong vòng lặp  Tính: 𝑥𝑛= 1 𝑛 = 0 𝑛2𝑥0 + 𝑛 − 1 2𝑥1 +⋯+ 1 2𝑥𝑛−1 𝑛 > 0 long calXn(int n) { long res, i; if(n == 0) res = 1; else { res = 0; for(i = 0; i < n; i ++ ) { res += (n-i)*(n-i)*calXn(i); } } } Đệ quy hỗ tương Ngô Quốc Việt 10  Gọi lại hàm thông qua hàm khác (hai hàm gọi qua lại lẫn nhau)  𝑥𝑛= 0 𝑛 = 0 𝑥𝑛−1 + 𝑦𝑛−1 𝑛 > 0 ; 𝑦𝑛 = 0 𝑛 = 0 𝑛2 ∗ 𝑥𝑛−1 + 𝑦𝑛−1 𝑛 > 0 long calXn(int n); long calYn(int n); long calXn(int n) { long res, i; if(n == 0) res = 1; else { res = calXn(n-1)+calYn(n-1); } return res } long calYn(int n) { long res, i; if(n == 0) res = 1; else { res = n*n*calXn(n-1)+calYn(n-1); } return res } Tail Recursion = Iteration Ngô Quốc Việt 11  Khi đệ quy chứa lệnh gọi chính nó ở cuối cùng, phía sau không còn lệnh nào nữa  Được gọi là tail recursion và hiệu quả như giải pháp lặp: Ví dụ tính giai thừa Ngô Quốc Việt 12 0! = 1 n! = n*(n-1)!, n>0 • Iterative solution 1: int iterFact (int n) { int result = 1; for (int k = 1; k <= n; k++) { result = result * k; } return result; } Bài tập tại lớp: hãy viết hàm đệ quy (và tail recursion) cho yêu cầu trên. Ví dụ tính dãy Fibonacci Ngô Quốc Việt 13 int fib (int n) { if (n <= 2) return 1; else return fib(n-1) + fib(n-2); } Dễ hiểu, nhưng không hiệu quả. Ví dụ tính dãy Fibonacci Ngô Quốc Việt 14 Hỏi: độ phức tạp bằng bao nhiêu? Ví dụ tính dãy Fibonacci Ngô Quốc Việt 15  Cách làm hiệu quả hơn: giữ lại số hiện hành, kết quả trước đó int fibonacci_start (int n) { return fibo(1, 0, n); } int fibo ( int curr, int prev, int n) { if (n <= 1) return curr; else return fibo(curr+prev, curr, n-1); } Tìm tuyến tính Ngô Quốc Việt 16  Giải thuật  Mỗi lần kiểm tra một phần tử.  Tìm từ đầu đến cuối.  Cơ sở để làm đệ quy: mảng rỗng  Trả về kết quả -1 ( not found).  Yếu tố khác: phần tử hiện hành trùng giá trị tìm.  Trả về chỉ mục của phần tử đang xét.  Cơ sở đệ quy: tìm phần còn lại, không bao gồm phần tử đang xét. Tìm tuyến tính Ngô Quốc Việt 17 1. if the array is empty 2. return -1 3. else if first element matches target 4. return index of first element 5. else 6. return result of searching rest of the array, excluding the first element Tìm nhị phân Ngô Quốc Việt 18 1. if array is empty 2. return -1 as result 3. else if middle element matches 4. return index of middle element as result 5. else if target < middle element 6. return result of searching lower portion of array 7. else 8. return result of searching upper portion of array Tìm nhị phân Ngô Quốc Việt 19 Tháp Hà Nội Ngô Quốc Việt 20 • Có ba cột tháp kim cương đặt ở cửa đền Brahma ở Hà Nội • Cột bên trái có 64 đĩa, mỗi đĩa kích thước khác nhau, được chồng lên nhau: Tháp Hà Nội Ngô Quốc Việt 21 • Muốn dời mọi đĩa từ tháp thứ nhất sang tháp thứ hai với sự hỗ trợ của tháp thứ ba • Mỗi lần chỉ di chuyển một đĩa, và đĩa lớn không được phép đặt lên trên đĩa nhỏ. Tháp Hà Nội-Minh hoạ với 3 đĩa Ngô Quốc Việt 22  Ký hiệu: cột A, B, C. Dời đĩa trên cùng từ A sang B Tháp Hà Nội-Minh hoạ với 3 đĩa Ngô Quốc Việt 23 Dời đĩa trên cùng từ A sang C Dời đĩa trên cùng từ B sang C Tháp Hà Nội-Minh hoạ với 3 đĩa Ngô Quốc Việt 24 Dời đĩa trên cùng từ A sang B Dời đĩa trên cùng từ C sang A Tháp Hà Nội-Minh hoạ với 3 đĩa Ngô Quốc Việt 25 Dời đĩa trên cùng từ C sang B Dời đĩa trên cùng từ A sang B Tháp Hà Nội Ngô Quốc Việt 26  Vấn đề cần giải quyết số lượng đĩa > 3.  Liệu có viết được giải thuật với các vòng lặp  được, nhưng hơi khó.  Giải quyết bằng đệ quy. Tháp Hà Nội Ngô Quốc Việt 27 /* hanoi.cpp * ... */ void Move(int n, char src, char dest, char aux); int main() { cout << “\n\nThe Hanoi Towers!\n\n” << “Enter how many disks: “; int numDisks; cin >> numDisks; Move(numDisks, „A‟, „B‟, „C‟); } Tháp Hà Nội Ngô Quốc Việt 28 /* hanoi.cpp * ... */ void Move(int n, char src, char dest, char aux); int main() { cout << “\n\nThe Hanoi Towers!\n\n” << “Enter how many disks: “; int numDisks; cin >> numDisks; Move(numDisks, „A‟, „B‟, „C‟); } Tháp Hà Nội – Thiết kế Ngô Quốc Việt 29  N=1 luôn làm được (trường hợp suy biến)  Quy nạp với N > 1 a. Đệ quy: dời N-1 đĩa từ “nguồn” sang “trung gian. Tháp Hà Nội – Thiết kế Ngô Quốc Việt 30 b. Dời đĩa còn lại từ “nguồn” sang “đích”. c. Đệ quy: dời N-1 đĩa từ “trung gian” sang “đích”. Tháp Hà Nội Ngô Quốc Việt 31 Giải thuật: 0. Receive n, src, dest, aux. 1. If n > 1: a. Move(n-1, src, aux, dest); b. Move(1, src, dest, aux); c. Move(n-1, aux, dest, src); Else Display “Move the top disk from “, src, “ to “, dest. End if. Tháp Hà Nội Ngô Quốc Việt 32 // ... void Move(int n, char src, char dest, char aux) { if (n > 1) { Move(n-1, src, aux, dest); Move(1, src, dest, aux); Move(n-1, aux, dest, src); } else cout << “Move the top disk from “ << src << “ to “ << dest << endl; } Tháp Hà Nội-4 đĩa Ngô Quốc Việt 33 The Hanoi Towers Enter how many disks: 4 move a disk from needle A to needle B move a disk from needle C to needle B move a disk from needle A to needle C move a disk from needle B to needle A move a disk from needle B to needle C move a disk from needle A to needle C move a disk from needle A to needle B move a disk from needle C to needle B move a disk from needle C to needle A move a disk from needle B to needle A move a disk from needle C to needle B move a disk from needle A to needle C move a disk from needle A to needle B move a disk from needle C to needle B Tháp Hà Nội-Phân tích Ngô Quốc Việt 34 Độ phức tạp: 𝑇 𝑛 = 2𝑇 𝑛 − 1 + 1 = 2𝑖 = 2𝑛 − 1𝑛𝑖=0 n Số đĩa cần chuyển 1 1 2 3 3 7 4 15 5 31 ... i 2i-1 64 264-1 (a big number) ~ 244 giây (giả sử máy tính chạy 220 lệnh/giây) Xấp xỉ 211 thế kỷ để chạy xong Bài toán đếm ô bất thường Ngô Quốc Việt 35  Desire: Xử lý ảnh hai chiều với các thông tin có từ  X-Ray  MRI  Satellite imagery  Etc.  Mục tiêu: xác định kích thước của vùng bất thường dựa trên màu sắc. Bài toán đếm ô bất thường Ngô Quốc Việt 36  Trắng  K  Xanh  ô bất thường  Blob == Những ô bất thường kề nhau (horizontal, vertical và diagonal) Người dùng nhập vị trí (x, y) của cell. o Vd: (chỉ số hàng, cột tính từ 0)  Chương trình trả về số ô trong blob o Vd: kích thước của blob chứa ô ? Bài toán đếm ô bất thường Ngô Quốc Việt 37 Algorithm count_cells(x, y): if (x, y) outside grid return 0 else if color at (x, y) normal return 0 else Set color at (x, y) to “Temporary” (normal) return 1 + sum of count_cells on neighbors Bài toán đếm ô bất thường Ngô Quốc Việt 38 int countCells(color grid[ROWS][COLS], int r, int c) { if (r = ROWS || c = COLS) { return 0; } else if (grid[r][c] != ABNORMAL) { return 0; } else { grid[r][c] = TEMPORARY; return 1 + countCells(grid,r-1,c-1) + countCells(grid,r-1,c) + countCells(grid,r-1,c+1) + countCells(grid,r,c+1) + countCells(grid,r+1,c+1) + countCells(grid,r+1,c) + countCells(grid,r+1,c-1) + countCells(grid,r,c- 1); } } Bài tập Ngô Quốc Việt 39  Viết chương trình (vòng lặp, và đệ quy) để tìm số hạng thứ n của dãy xác định bởi: 𝑎0 = 1, 𝑎1 = 3, 𝑎2 = 5, 𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−1 2 + 𝑎𝑛−2 3 Giải Bài tập Ngô Quốc Việt 40 Đệ quy quay lui-Minh hoạ bằng bài toán 8 con hậu Ngô Quốc Việt 41  Yêu cầu: các con hậu được đặt trên bàn cờ vua sao cho không “ăn” được lẫn nhau. Bài toán 8 con hậu-Dựa trên kinh nghiệm Ngô Quốc Việt 42  Nhận xét: mỗi con hậu phải ở trên một cột (domain knowledge)  Đặt con hậu vô mỗi hàng, cũng như chọn hàng cho từng con hậu  Đầu tiên, chọn ngẫu nhiên các hàng và hậu trên đó, sau đó mỗi vòng lặp di chuyển một con hậu sao cho không “ăn” lẫn nhau.  Tuy nhiên có thể dẫn tới trường hợp không tìm được lời giải vì trạng thái ngẫu nhiên ban đầu không tốt. Bài toán 8 con hậu-Đệ quy quay lui (backtracking) Ngô Quốc Việt 43  Đặt một “con hậu” ở hàng đầu tiên, sau đó ghi nhận cột và đường chéo của nó (vì hậu “ăn” ngang, dọc, xéo).  Đặt hậu khác vô hàng kế tiếp, sao cho không trùng cột hoặc đường chéo. Ghi nhận cột, đường chéo của hậu thứ hai này. Tiếp tục cho hàng kế.  Nếu không còn cột nào cho hậu ở hàng kế tiếp, buộc phải trở lại hàng trước đó và tìm chỗ khác cho hậu đã đặt (có khi xét ngược đến hàng đầu tiên).  Lặp lại quá trình trên cho cho các hàng còn lại.  Demo: Bài toán 8 con hậu-Đệ quy quay lui Ngô Quốc Việt 44 void n_Queens(i) { for (j = 1; j <= n; j++) if (a[j] && b[i + j] && c[i - j]) { x[i] = j; a[j] = b[i + j] = c[i - j] = false; if (i == n) Print(x); else n_Queens(i + 1); a[j] = b[i + j] = c[i - j] = true; } } Bài toán hôn nhân bền vững Ngô Quốc Việt 45  Tìm stable matching giữa hai tập, trong đó mỗi phần tử có ‘tiêu chuẩn thích’ khác nhau  Tìm cách ánh xã giữa từng phần tử giữa hai tập sao cho ‘thích’ gặp nhau nhiều nhất  Bài toán: Cho n man+n woman, mỗi người đánh số thứ tự thích những người khác giới tính. Ghép đôi từng cặp, sao cho tính ‘thích’ của họ là cao nhất. Hôn nhân bền vững-Giải thuật Gale and Shapley Ngô Quốc Việt 46  Mỗi man độc thân đề nghị woman thích nhất  Mỗi woman replies "maybe" man thích nhất and "no" cho các man còn lại.  Sau đó, woman chọn man cô thích nhất Hôn nhân bền vững-Giải thuật Gale and Shapley Ngô Quốc Việt 47 function stableMatching { Initialize all m ∈ M and w ∈ W to free while ∃ free man m who still has a woman w to propose to { w = m's highest ranked woman to whom he has not yet proposed if w is free (m, w) become engaged else some pair (m', w) already exists if w prefers m to m' (m, w) become engaged m' becomes free else (m', w) remain engaged } } Khử đệ quy Ngô Quốc Việt 48  Một số nnlt không hỗ trợ gọi đệ quy (COBOL, FORTRAN)  Mọi giải thuật đệ quy đều có thể chuyển thành giải thuật lặp. Hai phương pháp phổ biến.  Bổ sung thêm các biến lưu trữ các giá trị đã tính ở bước trước  Sử dụng stack để lưu trữ các kết quả trung gian  Không dễ dàng thực hiện khử đệ quy. Khử đệ quy-ví dụ quicksort Ngô Quốc Việt 49  Sử dụng stack để lưu trữ các chỉ số đầu+cuối của dãy con QuickSort không dùng đệ quy Bài tập Ngô Quốc Việt 50 1. Bài tập thực hành: xây dựng chương trình giải quyết bài toán toán hôn nhân bền vững. 2. Bài tập thực hành: xây dựng chương trình giải quyết bài toán toán 8 con hậu (nhóm 3 sinh viên). 3. Cài đặt các bài toán mergesort, quicksort, 8 hậu không dùng đệ quy