PHÂN TÍCH THIẾT KẾ GIẢI THUẬT

GIẢI THUẬT ĐỆ QUY

TS. NGÔ QUỐC VIỆT 2015

Nội dung

1. Giới thiệu 2. Các giải thuật đệ quy 3. Bài tập 4. Hỏi đáp.

2 Ngô Quốc Việt

Giới thiệu

 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

3 Ngô Quốc Việt

Thiết kế giải thuật đệ quy

 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)

4 Ngô Quốc Việt

Tại sao dùng đệ quy

 Ư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.

5 Ngô Quốc Việt

Khi nào dùng đệ quy

 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) 6

Ngô Quốc Việt

Đệ quy tuyến tính

 Lời gọi đệ quy chỉ được gọi một lần trong hàm.

𝑛 = 0 𝑛 > 0, 𝑛 𝑐ℎẵ𝑛

 Ví dụ tính: 𝑎𝑛 =

𝑛 2

𝑛 > 0, 𝑛 𝑙ẻ

𝐴 𝑎𝑛/2 3𝑛 + 1 𝑎𝑛−1

return (n/2)*CalAn(A, n/2);

return (3*n+1)*CalAn(A, n-1);

int CalAn(int A, int n) { if(n==0) return A; else if(n > 0 && (n %2) ==0) else }

7 Ngô Quốc Việt

Đệ quy nhị phân

 Lời gọi đệ quy chỉ được gọi hai lần trong hàm.

fn_1= fiBo(n-1); fn_2= fiBo(n-2); res = fn_1+fn_2;

long res, fn_1, fn_2; if(n <= 1) return 1; else { } return res;

int fiBo(int n) { }

 Đệ 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ị”

8

Ngô Quốc Việt

Đệ quy lồng  Lời gọi hàm đệ quy được gọi trong vòng lặp

1

 Tính: 𝑥𝑛=

𝑛 = 0 𝑛2𝑥0 + 𝑛 − 1 2𝑥1 + ⋯ + 12𝑥𝑛−1 𝑛 > 0

res += (n-i)*(n-i)*calXn(i);

res = 0; for(i = 0; i < n; i ++ ) { }

long res, i; if(n == 0) res = 1; else { }

long calXn(int n) { }

9 Ngô Quốc Việt

Đệ quy hỗ tương

 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

 𝑥𝑛=

; 𝑦𝑛 =

𝑛 = 0 𝑛2 ∗ 𝑥𝑛−1 + 𝑦𝑛−1 𝑛 > 0

𝑛 = 0 𝑥𝑛−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 }

10 Ngô Quốc Việt

Tail Recursion = Iteration

 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:

11 Ngô Quốc Việt

Ví dụ tính giai thừa

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.

12 Ngô Quốc Việt

Ví dụ tính dãy Fibonacci

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ả.

13 Ngô Quốc Việt

Ví dụ tính dãy Fibonacci

Hỏi: độ phức tạp bằng bao nhiêu?

14 Ngô Quốc Việt

Ví dụ tính dãy Fibonacci

 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); }

15 Ngô Quốc Việt

Tìm tuyến tính

 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.

16 Ngô Quốc Việt

Tìm tuyến tính

1.

if the array is empty return -1

2. 3. else if first element matches target return index of first element

4. 5. else

return result of searching rest of the array,

6. excluding the first element

17 Ngô Quốc Việt

Tìm nhị phân

1.

2.

3.

4.

5.

6.

7.

8.

if array is empty return -1 as result else if middle element matches return index of middle element as result else if target < middle element return result of searching lower portion of array else return result of searching upper portion of array

18 Ngô Quốc Việt

Tìm nhị phân

19 Ngô Quốc Việt

Tháp Hà Nội

• 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:

20 Ngô Quốc Việt

Tháp Hà Nội

• 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ỏ.

21 Ngô Quốc Việt

Tháp Hà Nội-Minh hoạ với 3 đĩa

 Ký hiệu: cột A, B, C.

Dời đĩa trên cùng từ A sang B

22 Ngô Quốc Việt

Tháp Hà Nội-Minh hoạ với 3 đĩa

Dời đĩa trên cùng từ A sang C

Dời đĩa trên cùng từ B sang C

23 Ngô Quốc Việt

Tháp Hà Nội-Minh hoạ với 3 đĩa

Dời đĩa trên cùng từ A sang B

Dời đĩa trên cùng từ C sang A

24 Ngô Quốc Việt

Tháp Hà Nội-Minh hoạ với 3 đĩa

Dời đĩa trên cùng từ C sang B

đĩa Dời trên cùng từ A sang B

25 Ngô Quốc Việt

Tháp Hà Nội

 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.

26 Ngô Quốc Việt

Tháp Hà Nội

/* 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‟); }

27 Ngô Quốc Việt

Tháp Hà Nội

/* 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‟); }

28 Ngô Quốc Việt

Tháp Hà Nội – Thiết kế

 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.

29 Ngô Quốc Việt

Tháp Hà Nội – Thiết kế

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”.

30 Ngô Quốc Việt

Tháp Hà Nội

Giải thuật:

a. Move(n-1, src, aux, dest); b. Move(1, src, dest, aux); c. Move(n-1, aux, dest, src);

Display “Move the top disk from “, src, “ to “, dest.

0. Receive n, src, dest, aux. 1. If n > 1: Else End if.

31 Ngô Quốc Việt

Tháp Hà Nội

// ... 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; }

32 Ngô Quốc Việt

Tháp Hà Nội-4 đĩa 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

33 Ngô Quốc Việt

Tháp Hà Nội-Phân tích

𝑛 𝑖=0

Số đĩa cần chuyển 1 3 7 15 31

2i-1 264-1 (a big number) ~ 244 giây (giả sử

Độ phức tạp: 𝑇 𝑛 = 2𝑇 𝑛 − 1 + 1 = 2𝑖 = 2𝑛 − 1 n 1 2 3 4 5 ... i 64

máy tính chạy 220 lệnh/giây)

Xấp xỉ 211 thế kỷ để chạy xong 34

Ngô Quốc Việt

Bài toán đếm ô bất thường

 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.

35 Ngô Quốc Việt

Bài toán đếm ô bất thường

 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: <1,4> (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 ô <1,4>?

36 Ngô Quốc Việt

Bài toán đếm ô bất thường

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

37 Ngô Quốc Việt

Bài toán đếm ô bất thường int countCells(color grid[ROWS][COLS], int r, int c) { if (r < 0 || r >= ROWS || c < 0 || 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); } }

38 Ngô Quốc Việt

Bài tập

 Viết chương trình (vòng lặp, và đệ quy) để tìm số hạng

3

2 + 𝑎𝑛−2

thứ n của dãy xác định bởi: 𝑎0 = 1, 𝑎1 = 3, 𝑎2 = 5, 𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−1

39 Ngô Quốc Việt

Giải Bài tập

40 Ngô Quốc Việt

Đệ quy quay lui-Minh hoạ bằng bài toán 8 con hậu

 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.

41 Ngô Quốc Việt

Bài toán 8 con hậu-Dựa trên kinh nghiệm

 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.

42 Ngô Quốc Việt

Bài toán 8 con hậu-Đệ quy quay lui (backtracking)

 Đặ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: http://www.math.utah.edu/~alfeld/queens/queens.html

43

Ngô Quốc Việt

Print(x);

n_Queens(i + 1);

x[i] = j; a[j] = b[i + j] = c[i - j] = false; if (i == n) else a[j] = b[i + j] = c[i - j] = true;

for (j = 1; j <= n; j++) if (a[j] && b[i + j] && c[i - j]) { }

Bài toán 8 con hậu-Đệ quy quay lui void n_Queens(i) { }

44 Ngô Quốc Việt

Bài toán hôn nhân bền vững

 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.

45 Ngô Quốc Việt

Hôn nhân bền vững-Giải thuật Gale and Shapley

 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

http://en.wikipedia.org/wiki/Stable_marriage_problem

46 Ngô Quốc Việt

Hôn nhân bền vững-Giải thuật Gale and Shapley

(m, w) become engaged

(m, w) become engaged m' becomes free

w = m's highest ranked woman to whom he has not yet proposed if w is free else some pair (m', w) already exists if w prefers m to m' else (m', w) remain engaged

Initialize all m ∈ M and w ∈ W to free while ∃ free man m who still has a woman w to propose to { }

function stableMatching { }

47 Ngô Quốc Việt

Khử đệ quy

 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.

48 Ngô Quốc Việt

Khử đệ quy-ví dụ quicksort

 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

49 Ngô Quốc Việt

Bài tập

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

50 Ngô Quốc Việt