Các chiến lược thiết kế thuật toán

PHẦN II. CÁC CHIẾN LƯỢC THIẾT KẾ THUẬT TOÁNCHƯƠNG III. MỘT SỐ KỸ THUẬT THIẾT KẾ THUẬT TOÁNBài 1. Chia để trịBài 2. Phương pháp tham lamBài 3. Quy hoạch độngCHƯƠNG III. MỘT SỐ KỸ THUẬT THIẾT KẾ THUẬT TOÁNNói chung khi thiết kế một giải thuật chúng ta thường dựa vào một số kĩ thuật nào đó. Một số kĩ thuật quan trọng để thiết kế giải thuật như: Chia để trị (Divide-and-Conquer), Quy hoạch động (dynamic programming),Kĩ thuật tham ăn (greedy techniques).CHƯƠNG IIIMỘT SỐ KỸ THUẬT THIẾT KẾ THUẬT TOÁNBài 1. Chia để trị1. Giới thiệu.Có thể nói rằng kĩ thuật quan trọng nhất, được áp dụng rộng rãi nhất để thiết kế các giải thuật có hiệu quả là kĩ thuật "chia để trị" (divide and conquer). Nội dung của nó là: Ðể giải một bài toán kích thước n, ta chia bài toán đã cho thành một số bài toán con có kích thước nhỏ hơn.Giải các bài toán con này rồi tổng hợp kết quả lại để được lời giải của bài toán ban đầu. CHƯƠNG IIIMỘT SỐ KỸ THUẬT THIẾT KẾ THUẬT TOÁNBài 1. Chia để trịÐối với các bài toán con, chúng ta lại sử dụng kĩ thuật chia để trị để có được các bài toán kích thước nhỏ hơn nữa.Quá trình trên sẽ dẫn đến những bài toán mà lời giải chúng là hiển nhiên hoặc đễ dàng thực hiện, ta gọi các bài toán này là bài toán cơ sở. CHƯƠNG IIIMỘT SỐ KỸ THUẬT THIẾT KẾ THUẬT TOÁNBài 1. Chia để trịTóm lại kĩ thuật chia để trị bao gồm hai quá trình: Phân tích bài toán đã cho thành các bài toán cơ sở.Tổng hợp kết quả từ bài toán cơ sở để có lời giải của bài toán ban đầu. CHƯƠNG IIIMỘT SỐ KỸ THUẬT THIẾT KẾ THUẬT TOÁNBài 1. Chia để trịChia: Chia lớn thành các bài toán con tương tự.Trị: Giải các bài toán con bằng đệ quy. Các bước Chia- Trị được lặp lại cho đến khi bài toán con đã̀ có lời giải.Kết hợp nghiệm (combaine): Nghiệm các bài toán con được kết hợp để cho nghiệm bài toán con lớn hơn.CHƯƠNG IIIMỘT SỐ KỸ THUẬT THIẾT KẾ THUẬT TOÁNBài 1. Chia để trịQuá trình thực hiện Chia-Để trị diễn ra theo hai bước:Bước chia để trị là đi “ từ trên xuống” (Top-Down) để xác định các lời gọi đệ quy.Bước kết hợp nghiệm thì đi từ dưới lên (Bottom-up), tại bước này thực hiện các tính toán và kết hợp nghiệm cho bài toán lớn hơn. CHƯƠNG IIIMỘT SỐ KỸ THUẬT THIẾT KẾ THUẬT TOÁNBài 1. Chia để trịSau đây là lược đồ của kỹ thuật chia-để-trị: Procedure 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 x thì việc tìm kiếm tiếp theo chỉ xét trên dãy k1, k2,..., kGiua–1Nếu kGiua x } L3 = { y in L : y = x } quicksort(L1) quicksort(L2) return concatenation of L1, L3, and L2 } }CHƯƠNG IIIMỘT SỐ KỸ THUẬT THIẾT KẾ THUẬT TOÁNBài 1. Chia để trịNhận xétSử dụng công cụ đệ quy:Rất chặt chẽ, dễ cài đặt.Thường đòi hỏi khối lượng tính toán rất lớn. Do nghiệm các bài toán con không được lưu trữ nên các bước sau, khi cần sử dụng thì phải tính lại. CHƯƠNG IIIMỘT SỐ KỸ THUẬT THIẾT KẾ THUẬT TOÁNBài 1. Chia để trị (Bài tập)Một số bài tập trang 46-48 (Giáo trình Nhập môn thuật toán).CHƯƠNG IIIMỘT SỐ KỸ THUẬT THIẾT KẾ THUẬT TOÁNBài 2. Phương pháp tham lam1. Giới thiệu.Bài toán tối ưu tổ hợp Là một dạng của bài toán tối ưu, nó có dạng tổng quát như sau: Cho hàm f(X) = xác định trên một tập hữu hạn các phần tử D. Hàm f(X) được gọi là hàm mục tiêu. Mỗi phần tử X ∈ D có dạng X = (x1, x2, .. xn) được gọi là một phương án. Cần tìm một phương án X ∈D sao cho hàm f(X) đạt min (max). Phương án X như thế được gọi là phương án tối ưu.CHƯƠNG IIIMỘT SỐ KỸ THUẬT THIẾT KẾ THUẬT TOÁNBài 2. Phương pháp tham lamKĩ thuật tham ăn thường được vận dụng để giải bài toán tối ưu tổ hợp bằng cách xây dựng một phương án X. Phương án X được xây dựng bằng cách lựa chọn từng thành phần Xi của X cho đến khi hoàn chỉnh (đủ n thành phần). Với mỗi Xi, ta sẽ chọn Xi tối ưu. Áp dụng kĩ thuật tham ăn sẽ cho một giải thuật thời gian đa thức, tuy nhiên nói chung chúng ta chỉ đạt được một phương án tốt chứ chưa hẳn là tối ưu. CHƯƠNG IIIMỘT SỐ KỸ THUẬT THIẾT KẾ THUẬT TOÁNBài 2. Phương pháp tham lamThường dùng để giải các bài toán tối ưu theo nghĩa tốt nhất có thể được mà do kích thước dữ liệu quá lớn không giải quyết bằng phương pháp duyệt toàn bộ được.Xây dựng cách chọn theo kiễu ăn tham.Xây dựng cấu trúc tối ưuCHƯƠNG IIIMỘT SỐ KỸ THUẬT THIẾT KẾ THUẬT TOÁNBài 2. Phương pháp tham lam2. Sơ đồ thuật toánProcedure Greedy;{*Giả sử C là tập các ứng cử viên*}beginS := ; {* S là lời giải xây dựng theo thuật toán *}While (C ) and not Solution(S) doBeginx a[i].Xét tất cả chỉ số j trong khoảng từ i+1 đến n mà a[j] >a[i], chọn ra chỉ số jmax có L[jmax] là lớn nhất. Do đó công thức truy hồi sẽ là: L[i] = L[jmax] +1. Trường hợp không tồn tại aj mà aj> ai thì đặt L[i] = 1CHƯƠNG IIIMỘT SỐ KỸ THUẬT THIẾT KẾ THUẬT TOÁNBài 3. Quy hoạch động(iiii) Truy vết Nếu cần đưa ra các phần tử của dãy con có độ dài dài nhất, cần tạo mảng T: T[i] =jmax để chỉ rằng dãy con dài nhất bắt đầu từ a[i] có phần tử thứ 2 là a[jmax].CHƯƠNG IIIMỘT SỐ KỸ THUẬT THIẾT KẾ THUẬT TOÁNBài 3. Quy hoạch động2.3. Bài toán biến đổi xâuCho X= x1x2xm và Y= y1y2...ynVới xâu X có thể sử dụng 03 phép toán: chèn thêm một kí tự vào một vị trí bất kì, xóa một kí tự bất kì, đổi một kí tự bất kì thành một kí tự tùy chọn.Yêu cầu: Sử dụng ít phép toán nhất để biến đổi u X thành YCHƯƠNG IIIMỘT SỐ KỸ THUẬT THIẾT KẾ THUẬT TOÁNBài 3. Quy hoạch độngBảng phương ánB[0..m, 0..n] làm bảng phương án, trong đó B[i,j] là số phép toán ít nhất để biến đổi xâu con X I ( prefix của X) thành xâu con Yj(prefix của Y).Cơ sở Xi là xâu rỗng ( i= 0), B[0,j] =j .Yj là xâu rỗng ( j= 0), CHƯƠNG IIIMỘT SỐ KỸ THUẬT THIẾT KẾ THUẬT TOÁNBài 3. Quy hoạch độngCông thức truy hồi- Nếu xi=yj thì B[i,j] = B[i-1,j-1] Nếu xiyj thì tại vị trí xi:+ Hoặc chèn vào sau xi một kí tự yj, khi đó B[i, j]= 1+B[i,j-1] + Hoặc thay xi bằng yj , khi đó là B[i, j]= 1+B[i-1,j-1] + Hoặc xóa xi, khi đó B[i, j]= 1+B[i-1,j] B[i,j] = min ( B[i-1,j-1], B[i-1,j], B[i, j-1]) +1CHƯƠNG IIIMỘT SỐ KỸ THUẬT THIẾT KẾ THUẬT TOÁNBài 3. Quy hoạch động(iiii)Truy vết ĐS B[n,m] chứa số lượng ít nhất các phép biến đổi. Khi cần chỉ rõ tại vị trí nào, cần sử dụng phép biến đổi nào ta xây dựng bảng T[1..m, 1..n] để ghi nhận truy vết đánh dấu B[i,j]CHƯƠNG IIIMỘT SỐ KỸ THUẬT THIẾT KẾ THUẬT TOÁNBài 3. Quy hoạch động (Bài tập)