Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 12: Các chiến lược thiết kế thuật toán

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 12: Các chiến lược thiết kế thuật toán

1. Bài 12: Các chiến lược thiết kế thuật toán Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Cấu trúc dữ liệu và giải thuật HKI, 2013-2014
2. Nội dung chính 1. Ý tưởng các chiến lược 2. Ví dụ minh họa 2 diepht@vnu
3. Các chiến lược 1. Chia-để-trị 4. Tham ăn  divide-and-conquer  greedy method 2. Quy hoạch động 5. Các thuật toán ngẫu  dynamic programming nhiên 3. Quay lui  randomized /  backtracking probabilistic algorithm Mỗi chiến lược có các tính chất riêng và chỉ thích hợp cho một số dạng bài toán nào đó. 3 diepht@vnu
4. Ý tưởng  Chia-để-trị  Tham ăn  Chia bài toán thành các bài  Thực hiện từng bước một. Tại toán kích thước nhỏ có thể giải mỗi bước, chọn phương án quyết độc lập. Sau đó kết hợp được xem là tốt lúc đó. nghiệm các bài toán kích thước  Không phải tất cả các thuật nhỏ thành nghiệm bài toán gốc toán tham ăn đều cho kết quả  Thuật toán đệ quy tối ưu toàn cục  Quy hoạch động  Các chiến lược khác  Giải bài toán lớn dựa vào kết  Quay lui quả bài toán con. Tránh lặp lại  Thuật toán ngẫu nhiên việc giải cùng một bài toán con bằng cách lưu nghiệm các bài toán con trong một bảng  Thuật toán lặp 4 diepht@vnu
5. Thuật toán tiêu biểu  Chia-để-trị  Tìm dãy con chung của  Tìm kiếm nhị phân hai dãy số (longest (binary search) common subsequence)  Sắp xếp trộn (merge  Tham ăn sort)  Xây dựng mã Huffman  Sắp xếp nhanh (quick (Huffman encoding) sort)  Tìm cây bao trùm nhỏ  Quy hoạch động nhất (minimum spanning  Tìm dãy con tăng dài tree) nhất (longest increasing subsequence)  Bài toán ba lô (backpacker/knapsack)  Bài toán người bán hàng (traveling salesman) 5 diepht@vnu
6. Các thuật toán Chương 16 Giáo trình STT Bài toán Thuật toán 1 Tìm kiếm trên mảng được sắp chia-để trị 2 Bài toán Tháp Hà Nội chia-để trị 3 Sắp xếp chia-để trị 4 Tìm max, min chia-để trị 5 Tính n! chia-để trị 6 Tìm số Fibonacci thứ n quy hoạch động 7 Sắp đồ vật vào ba lô quy hoạch động, tham ăn 8 Tìm dãy con chung của 2 dãy số quy hoạch động 9 Bài toán 8 con hậu vét cạn, quay lui, thuật toán Las Vegas 6 diepht@vnu
7. Các thuật toán Chương 16 Giáo trình STT Bài toán Chiến lược 10 Bài toán người bán hàng vét cạn, tham ăn 11 Tìm dãy con có tổng cho trước quay lui 12 Tính gần đúng số Pi thuật toán ngẫu nhiên 13 Tính gần đúng tích phân xác định thuật toán ngẫu nhiên 14 Phần tử đa số thuật toán ngẫu nhiên 7 diepht@vnu
8. Tìm kiếm nhị phân 8 diepht@vnu
9. Lược đồ của kỹ thuật chia-để-trị DivideConquer (A,x) // tìm nghiệm x của bài toán A. { if (A đủ nhỏ) Solve (A); else{ Chia bài toán A thành các bài toán con A1, A2, , Am; for (i = 1; i <= m ; i ++) DivideConquer (Ai , xi); Kết hợp các nghiệm xi của các bài toán con Ai (i=1, , m) để nhận được nghiệm x của bài toán A; } } 9 diepht@vnu
10. Tìm kiếm nhị phân Algorithm binarySearch(x, A, first, last): Input: search keyword x and array A of Items with two ends marked by indexes first and last Output: true if x in A, false otherwise if first > last then return false mid  (first + last) / 2 if x = A[mid].key then return true else if x < A[mid].key then binarySearch(x, A, first, mid - 1) else binarySearch(x, A, mid + 1, last) 10 diepht@vnu
11. Tìm kiếm nhị phân A  1 3 4 6 8 9 11 chỉ số  0 1 2 3 4 5 6 A = (1, 3, 4, 6, 8, 9, 11); x = 4. search(x, A).  binarySearch(x, A, first, last)  binarySearch(x, A, 0, 6)  So x với A[3]. x nhỏ hơn.  binarySearch(x, A, 0, 2)  So x với A[1]. x lớn hơn.  binarySearch(x, A, 2, 2)  So x với A[2]. Bằng. Trả về true. 11 diepht@vnu
12. 12 diepht@vnu
13. 13 diepht@vnu
14. Tìm số Fibonacci thứ n 14 diepht@vnu
15. Tìm số Fibonacci thứ n đệ quy  F = F + F Algorithm Fib(n) n n-1 n-2 Input n  F0 =0, F1 =1 Output số Fibonacci thứ n  0, 1, 1, 2, 3, 5, 8, 13, 21, 34 if n = 0 then return 0 else if n = 1 then return 1  Thủ tục tính đệ quy trực tiếp thực else hiện chậm do tính lặp nhiều lần. return Fib(n – 2) + Fib(n – 1) F(6) = 8 F(5) F(4) F(4) F(3) F(3) F(2) F(3) F(2) F(2) F(1) F(2) F(1) F(1) F(0) F(2) F(1) F(1) F(0) F(1) F(0) F(1) F(0) F(1) F(0) 15 diepht@vnu
16. Phân tích  Có bao nhiêu phép cộng?  Tỉ lệ vàng F 15+ n+1 ≈=φ ≈1.61803 Fn 2 n  Suy ra Fn ≈ 1.6  Cây đệ quy có các lá bằng 0 hoặc 1, do đó có tổng cộng khoảng 1.6n phép cộng  Thời gian thực hiện là hàm mũ 16 diepht@vnu
17. Fibonacci(n) quy hoạch động  Ta có thể tìm Fn trong thời gian tuyến tính bằng cách ghi nhớ nghiệm các bài toán con – tức là dùng quy hoạch động  Tính toán từ dưới-lên (bottom-up)  Đánh đổi bộ nhớ để lấy thời gian!  Theo cách này, tại thời điểm bất kì cần ghi nhớ 2 giá trị Algorithm Fibonacci(n) Input n Output số Fibonacci thứ n F00 F1 1 for i  2 to n do Fi Fi-1 + Fi-2 17 diepht@vnu
18. Fibonacci(n) = ? Phương án Thời gian? Không gian? Đệ quy Quy hoạch động, dùng mảng fib[1000] Quy hoạch động không dùng mảng 18 diepht@vnu
19. Tìm dãy con tăng dài nhất 19 diepht@vnu
20. Tìm dãy con tăng dài nhất  Hãy tìm dãy con tăng dài nhất của một dãy số cho trước  Ví dụ  dãy được cho là { 14, 1, 17, 2, 16, 17, 3, 15, 4, 1, 5, 18, 13, 6, 7, 19, 8, 12, 1, 9, 10, 8 }  thì dãy con tăng dài nhất là { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }  Giải bài toán này như thế nào?  Vì sao bài toán này là bài toán quy hoạch động? 20 diepht@vnu
21. Quy hoạch động  Quy hoạch động không phải là một thuật toán.  Quy hoạch động không phải là một phong cách lập trình.  Quy hoạch động là một lớp các bài toán có tính chất:  Các bài toán con gối nhau (overlapping subproblems) và  Cấu trúc con tối ưu (optimal substructure)  các lời giải tối ưu cho các bài toán con có thể được sử dụng để tìm lời giải tối ưu cho bài toán toàn cục  Ví dụ: Để tìm dãy con tăng dài nhất, ta xét 2 bài toán  Tìm dãy con tăng dài nhất kết thúc tại phần tử thứ k  Tìm dãy dài nhất trong những dãy đã cho 21 diepht@vnu
22. Tìm dãy con tăng dài nhất: bài toán con (1/2) s1 14 ? s2 1 ?  Dãy gốc S = { 14, 1, 17, 2, 16, 17, s3 17 ? 3, 15, 4, 1, 5, 18, 13, 6, 7, 19, 8, s4 2 ? 12, 1, 9, 10, 8 } s5 16 ? s6 17 ?  Bài toán con: Tìm dãy con s7 3 ? tăng dài nhất kết thúc tại s8 15 ? phần tử thứ k s9 4 ? s10 1 ?  Thuật toán s11 5 ?  Nếu tất cả các phần tử trước k s12 18 ? đều >= S[k], trả về dãy con chỉ s13 13 ? chứa S[k] s14 6 ?  Nếu có t phần tử đứng trước k s15 7 ? nhỏ hơn S[k], gọi W là dãy dài s16 19 ? nhất trong các dãy con tăng kết s17 8 ? s18 12 ? thúc tại các phần tử này. Trả về W s19 1 ? ∪ S[k] s20 9 ? s21 10 ? s22 8 ? 22 diepht@vnu
23. Tìm dãy con tăng dài nhất: bài toán con (2/2) s1 14 {14} s2 1 {1}  Dãy gốc S = { 14, 1, 17, 2, 16, 17, s3 17 {14|1, 17} 3, 15, 4, 1, 5, 18, 13, 6, 7, 19, 8, s4 2 {1, 2} 12, 1, 9, 10, 8 } s5 16 {1, 2, 16} s6 17 {1, 2, 16, 17}  Bài toán con: Tìm dãy con s7 3 {1, 2, 3} tăng dài nhất kết thúc tại s8 15 {1, 2, 3, 15} phần tử thứ k s9 4 {1, 2, 3, 4} s10 1 {1}  Thuật toán s11 5 {1, 2, 3, 4, 5}  Nếu tất cả các phần tử trước k s12 18 {1, 2, 3, 4, 5, 18} đều >= S[k], trả về dãy con chỉ s13 13 {1, 2, 3, 4, 5, 13} chứa S[k] s14 6 {1, 2, 3, 4, 5, 6}  Nếu có t phần tử đứng trước k s15 7 {1, 2, 3, 4, 5, 6, 7} nhỏ hơn S[k], gọi W là dãy dài s16 19 {1, 2, 3, 4, 5, 6, 7, 19} nhất trong các dãy con tăng kết s17 8 {1, 2, 3, 4, 5, 6, 7, 8} s18 12 {1, 2, 3, 4, 5, 6, 7, 8, 12} thúc tại các phần tử này. Trả về W s19 1 {1} ∪ S[k] s20 9 {1, 2, 3, 4, 5, 6, 7, 8, 9} s21 10 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} s22 8 {1, 2, 3, 4, 5, 6, 7, 8} 23 diepht@vnu
24. Quy hoạch động: Cấu trúc chung 1. Đưa ra cách tính nghiệm của các bài toán con đơn giản 2. Tìm công thức xây dựng nghiệm của bài toán thông qua nghiệm của các bài toán con 3. Thiết kế bảng để lưu nghiệm của các bài toán 4. Tính nghiệm của các bài toán từ nhỏ đến lớn 5. Xây dựng nghiệm của bài toán cần tìm từ bảng 24 diepht@vnu
25. Bài toán ba lô: mỗi loại chỉ có 1 đồ vật
26. Bài toán ba lô  Có N đồ vật, đồ vật i có khối lượng wi và giá trị ti . Một tên trộm có 1 chiếc ba lô có thể mang được không quá M kg. Hãy tìm cách mang một số đồ vật để tổng giá trị lấy được là lớn nhất. Biết rằng, wi nguyên dương nhỏ hơn 101, M nguyên dương nhỏ hơn 1001.  Ví dụ N = 5, M = 10 i A B C D E wi 1 3 5 7 9 ti $100 $200 $301 $400 $500 26 diepht@vnu
27. Bài toán ba lô: bài toán con  Khảo sát các tập con các đồ vật:  nếu có các đồ vật { i0, i1 in } thì  ta xét tập con các đồ vật i0 ik.  Khảo sát tất cả khối lượng cực đại nhỏ hơn:  nếu khối lượng cực đại của bài toán gốc là m thì  với mỗi số nguyên w trong khoảng 0 m, tìm giá trị cực đại của tập con của i0 ik có khối lượng < w. 27 diepht@vnu
28. Bài toán ba lô: Lời giải quy hoạch động for mọi ô [x, y] if x = 0 và y = 0 then cell[x, y] = 0kg $0 {} Đồ vật Khối lượng Giá trị else A 1kg $100 gọi m là đồ vật thêm vào ở cột y B 3kg $200 gọi w là khối lượng của m C 5kg $301 if w > khối lượng cực đại của hàng D 7kg $400 cell[x, y] = cell[x, y-1] E 9kg $500 else cell[x, y] = max {cell[x, y-1], (cell[x-w, y-1] U {m})} tập rỗng A A/B A/B/C A/B/C/D A/B/C/D/E kg ≤ 0 ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} kg ≤ 1 ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} kg ≤ 2 ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} kg ≤ 3 ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} kg ≤ 4 ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} kg ≤ 5 ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} kg ≤ 6 ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} kg ≤ 7 ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} kg ≤ 8 ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} kg ≤ 9 ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} kg ≤ 10 ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} 28 diepht@vnu
29. Bài toán ba lô: Lời giải quy hoạch động for mọi ô [x, y] if x = 0 và y = 0 then cell[x, y] = 0kg $0 {} Đồ vật Khối lượng Giá trị else A 1kg $100 gọi m là đồ vật thêm vào ở cột y B 3kg $200 gọi w là khối lượng của m C 5kg $301 if w > khối lượng cực đại của hàng D 7kg $400 cell[x, y] = cell[x, y-1] E 9kg $500 else cell[x, y] = max {cell[x, y-1], (cell[x-w, y-1] U {m})} tập rỗng A A/B A/B/C A/B/C/D A/B/C/D/E kg ≤ 0 0kg $0 {} 0kg $0 {} 0kg $0 {} 0kg $0 {} 0kg $0 {} 0kg $0 {} kg ≤ 1 0kg $0 {} 1kg $100 {A} 1kg $100 {A} 1kg $100 {A} 1kg $100 {A} 1kg $100 {A} kg ≤ 2 0kg $0 {} 1kg $100 {A} 1kg $100 {A} 1kg $100 {A} 1kg $100 {A} 1kg $100 {A} kg ≤ 3 0kg $0 {} 1kg $100 {A} 3kg $200 {B} 3kg $200 {B} 3kg $200 {B} 3kg $200 {B} kg ≤ 4 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 4kg $300 {A, B} 4kg $300 {A, B} 4kg $300 {A, B} kg ≤ 5 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 5kg $301 {C} 5kg $301 {C} 5kg $301 {C} kg ≤ 6 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 6kg $401 {A,C} 6kg $401 {A,C} 6kg $401 {A,C} kg ≤ 7 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 6kg $401 {A,C} 6kg $401 {A,C} 6kg $401 {A,C} kg ≤ 8 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 8kg $501 {B,C} 8kg $501 {B,C} 8kg $501 {B,C} kg ≤ 9 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 9kg $601 {A, B, C} 9kg $601 {A, B, C} 9kg $601 {A, B, C} kg ≤ 10 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 9kg $601 {A, B, C} 9kg $601 {A, B, C} 9kg $601 {A, B, C} 29 diepht@vnu
30. Bài toán ba lô  Có cần thiết phải ghi lại khối lượng, giá trị và danh sách đồ vật trong từng ô?  Có cần thiết phải lưu lại toàn bộ các ô trong một mảng 2 chiều lớn?  Thời gian thực hiện của thuật toán này? 30 diepht@vnu
31. Bài toán ba lô: số lượng mỗi loại không hạn chế 31 diepht@vnu
32. Các thuật toán  Quy hoạch động: Giáo trình, tr.422  Tham ăn: Giáo trình, tr.437 32 diepht@vnu
33. Bài tập 1. Giải bài toán ba lô sau dùng quy hoạch động: max 0.5x1 + 4x2 + 3x3 biết x1 + 3x2 + 2x3 ≤ 5 2. Giải bài toán trên dùng thuật toán tham ăn. 33 diepht@vnu
34. Chuẩn bị tuần tới  Lý thuyết: Đọc chương 17 giáo trình (Sắp xếp)  Thực hành: Hàng ưu tiên và Thuật toán nén Huffman 34 diepht@vnu