Đề tài Thuật toán chia để trị

MỤC LỤC THUẬT TOÁN CHIA ĐỂ TRỊ (Divide to Conquer) Có lẽ thuật toán được sử dụng nhiều nhất, quan trọng nhất là kỹ thuật ″Chia để Trị″. Kỹ thuật này sẽ chia bài toán hiện thời thành N bài toán nhỏ hơn, thực hiện lời giải cho từng bài toán nhỏ này và từ đó xây dựng thuật toán cho bài toán lớn tổng hợp. Ví dụ cho các thuật toán này là Sắp xếp Trộn(1) hoặc Tìm kiếm Nhị phân(2). 1) Khái niệm: Chia để trị là một trong những phương pháp thiết kế giải thuật cơ bản bao gồm các thao tác: Chia: Chia bài toán cần giải thành một loạt các bài toán con độc lập. Trị: Đòi hỏi việc giải các bài toán con thu được. Tổng hợp: Thực hiện việc xây dựng lời giải của bài toán đặt ra từ các lời giải của bài toán con. 2) Sơ đồ chung: Sơ đồ chung của thuật toán chia để trị (Divide and Conquer) gồm 3 thành phần: - Chia (Divide): Chia bài toán cần giải S ra thành các bài toán con S1, S2, S3, ... - Trị (Conquer): Giải các bài toán con một cách đệ quy. - Tổng hợp (Combine): Tổng hợp lời giải của bài toán S1, S2, S3, ... thành lời giải của bài toán S. Để phân tích độ phức tạp của thuật toán có thể sử dụng công thứ đệ quy. Vấn đề đặt ra là cần giải các bài toán con độc lập bằng cách nào? Đó là vấn đề trung tâm của bài toán. 3) Thuật toán β: Giả sử chúng ta có thuật toán α để giải bài toán kích thước dữ liệu vào n với thời gian bị chặn bởi cn2 (c: hằng số). Xét thuật giải β để giải chính bài toán đó bằng cách: - Bước 1: Chia bài toán cần giải thành 3 bài toán con với kích thước n/2. - Bước 2: Giải 3 bài toán bằng thuật toán α. - Bước 3 Tổng hợp lời giải của 3 bài toán con để thu được lời giải của bài toán. * Tính đúng đắn của thuật toán β Giả sử bước 3 đòi hỏi thời gian dn(d: hằng số). Gọi: T α(n) = thời gian của thuật toán α. T β(n) = thời gian của thuật toán β. Ta có: T α(n) = cn2 (theo giả thuyết) T β(n) = 3.T α(n/2) + dn = ¾.cn2 + dn. Nếu: dn 4. d/c thì thuật toán β nhanh hơn thuật toán α. Do 4.d/c là hằng số nên với n đủ lớn ta luôn có n > 4. d/c. Điều đó cho thấy việc sử dụng thuật toán β để giải bài toán đặt ra bằng cách chia nó thành các bài toán con có kích thước càng ngày càng nhỏ đến khi thu được bài toán con kích thước n0 < 4.d/c sẽ thu được hiệu quả cao. 4) Sơ đồ thuật toán chia để trị: procedure Divide_and_Conquer(n); begin if n ≤ n0 then Giải bài toán một cách trực tiếp; else begin Chia bài toán thành r bài toán con có kích thước n/k; for (mỗi bài toán trong r bài toán con) do Divide_and_Conquer(n/k); Tổng hợp lời giải của r bài toán con để thu được lời giải của bài toán; end; end; 5) Một số ví dụ 5.1) Bài toán tháp Hà Nội  Để minh họa rõ hơn cho kỹ thuật này chúng ta hãy xét một ví dụ quen thuộc đó là bài toán ″Tháp Hà Nội″. Giả sử có 3 cọc A, B, C. Ban đầu tại A đặt một số đĩa với thứ tự trên nhỏ dưới to như hình vẽ. Yêu cầu của bài toán là chuyển toàn bộ số đĩa trên sang cọc B, trong quá trình chuyển được phép sử dụng đĩa C, mỗi lần chuyển đúng 01 đĩa và luôn bảo đảm nguyên tắc đĩa nhỏ nằm trên đĩa to trong suốt quá trình chuyển. Bài toán Tháp Hà Nội trên có thể giải với thuật toán ″thông minh″ sau: Giả sử ta đặt 3 cọc trên tại các đỉnh của một tam giác đều. Tại bước với số lượt là lẻ, ta chuyển đĩa nhỏ nhất sang cọc bên cạnh theo chiều kim đồng hồ, tại bước đi với số lượt là chẵn, ta thực hiện một thao tác bất kỳ nhưng không đụng đến cái đĩa nhỏ nhất. Các bạn dễ dàng kiểm tra rằng đó là một thuật toán đúng, tuy nhiên nó rất khó hiểu, khó tổng quát sang các trường hợp khác. Ta hãy thử vận dụng tư duy của thuật toán ″Chia để Trị″ đối với bài toán Tháp Hà Nội này. Bài toán chuyển N đĩa từ A sang B có thể chia thành 2 bài toán nhỏ hơn với kích thước N-1 như sau: (a) Chuyển N-1 đĩa đầu tiên từ A sang C (giữ nguyên trạng thái của đĩa thứ N tại A). (b) Chuyển đĩa thứ N từ A sang B và chuyển N-1 đĩa từ C sang B. Chú ý rằng khi thực hiện bài toán (b) phần chuyển N-1 đĩa từ C sang B ta có thể dùng lại hoàn toàn thuật toán của bài (a) nhưng với vị trí thay đổi giữa A và C và tất nhiên bỏ qua sự có mặt của đĩa thứ N trong A hay B. Với cách tư duy như vậy, việc mô phỏng thuật toán sẽ tương đối khó do nó phải gọi đệ qui đến chính nó nhưng cách làm trên thật là dễ hiểu và cho phép chúng ta áp dụng cho nhiều lớp bài toán khác. Chúng ta hãy xét một vài ví dụ. 5.2) Bài toán nhân các số tự nhiên lớn Xét bài toán nhân 2 số tự nhiên n-bit X và Y. Bài toán nhân 2 số tự nhiên n-bit (n chữ số) đã được dạy trong nhà trường phổ thông với độ phức tạp O(n2)(3). Bây giờ chúng ta sẽ xét lại bài toán này với kỹ thuật Chia để Trị. Ta phân tách mỗi số X, Y thành 2 phần, mỗi phần n/2 bit. Để cho đơn giản ta sẽ luôn xét n là lũy thừa của 2. X, Y sẽ được phân tích thành 2 phần n/2-bit như sau: X = A | B (X = A2n/2 + B) Y = C | D  (Y = C2n/2 + D) Khi đó tích XY sẽ có dạng: XY = AC2n + (AD+BC)2n/2 + BD (1) Dựa trên công thức (1) ta có thể suy luận đơn giản như sau cho việc tính tích XY: chúng ta sẽ tính 4 phép nhân với các số n/2-bit là AC, AD, BC và BD, sau đó thực hiện 3 phép cộng với các số 2n-bit, cuối cùng là 2 phép chuyển chữ số (2 phép nhân với lũy thừa của 2) Các phép cộng và phép chuyển chữ số đều được thực hiện với thời gian O(n), do đó ta thu được công thức tính độ phức tạp của phép toán trên T(n) là: T(1) = 1 T(n) = 4T(n/2) + C.n (C-const) (2) Công thức (2) cho ta T(n) = O(n2) và như vậy ta chưa thu được kết quả gì mới so với phương pháp tính từ nhà trường phổ thông. Bây giờ ta biến đổi công thức (1) dưới dạng: XY = AC2n + ((A-B)(D-C) + AC + BD)2n/2 + BD (2) Công thức (2) mặc dù phức tạp hơn (1) nhưng chúng có thể được tính bởi: - 3 phép nhân n/2-bit: AC, BD và (A-B)(D-C). - 6 phép +,- các số n/2-bit. - 2 phép chuyển chữ số (nhân với lũy thừa của 2). Do vậy với cách tính trên ta có công thức sau tính độ phức tạp của thuật toán này: T(1) = 1 T(n) = 3T(n/2) + C.n (C-const) (3) Công thức (3) cho ta Như vậy ta đã thu được một kết quả mới cho việc thực hiện phép nhân 2 số tự nhiên n-bit với thuật toán mạnh hơn phép nhân bình thường đã học trong nhà trường (4). 5.3) Bài toán tạo lịch thi đấu Tennis Giả sử cần lập một lịch thi đấu Tennis cho n = 2k vận động viên (VĐV). Mỗi vận động viên phải thi đấu với lần lượt n-1 vận động viên khác, mỗi ngày thi đấu 1 trận. Như vậy n-1 là số ngày thi đấu tối thiểu phải có. Chúng ta cần lập lịch thi đấu bằng cách thiết lập ma trận có n hàng, n-1 cột. Giá trị số tại vị trí (i,j) (hàng i, cột j) chỉ ra vận động viên cần thi đấu với vận động viên i trong ngày thứ j. Sử dụng kỹ thuật Chia để Trị, chúng ta hãy lập lịch thi đấu cho nửa (n/2) số vận động viên đầu tiên. Bằng việc sử dụng lời gọi đệ qui chúng ta đưa bài toán về trường hợp chỉ có 2 VĐV. Chúng ta minh họa bằng trường hợp n=8. Lịch thi đấu cho 4 người đầu tiên của danh sách chiếm nửa trái trên của ma trận (4 hàng, 3 cột). Phần nửa trái dưới (4 hàng, 3 cột) của ma trận là lịch thi đấu của 4 VĐV còn lại (từ 5 đến 8). Phần này thu được từ nửa trái trên bằng cách cộng 4 vào mỗi phần tử tương ứng của ma trận. Để điền nốt các phần còn lại của ma trận chúng ta chỉ cần xác định lịch thi đấu giữa các VĐV với số thấp (≤n/2) với các VĐV với số cao (≥n/2). Để làm việc này chúng ta xếp các VĐV từ 1 đến n/2 đấu lần lượt với các VĐV số cao vào ngày 4. Các ngày còn lại thu được từ ngày 4 bằng cách hoán vị vòng quanh các VĐV với số thứ tự cao. Quá trình điền số được mô tả trong hình 2. Các bạn có thể tổng quát quá trình này cho trường hợp tổng quát n=2k bất kỳ. 5.6) Giải và cài đặt bài toán Mảng con lớn nhất Bài toán mảng con lớn nhất: Mảng a’ = {ap, ..., aq} với 1<=p,q<=n được gọi là mảng con của a. Ta gọi trọng lượng của mảng con là tổng các phần tử của nó. Cho mảng số a = {a1, a2, ..., an}. Vấn đề đặt ra là trong số các mảng con của a hãy tìm mảng con có trọng lượng lớn nhất. Mảng như vậy gọi là mảng con lớn nhất. Để đơn giản chỉ xét bài toán trọng lượng của mảng con lớn nhất (không cần tìm vị trí của p và q). 5.6.1) Thuật toán chia để trị tìm mảng con lớn nhất gồm các thao tác: Chia: Chia mảng a thành 2 mảng con với chênh lệch độ dài là ít nhất, ký hiệu là aL và aR. Trị: Tính mảng con lớn nhất của mỗi nửa một cách đệ quy. Gọi wL và wR là trọng lượng của các mảng con lớn nhất của aL và aR tương ứng. Tổng hợp: Thoạt tiên có thể nghĩ đến kết quả cần tìm là max(wL,wR). Tuy nhiên phải tính đến tình huống mảng con lớn nhất nằm đè nên điểm chia. 5.6.2) Thuật toán chia để trị tìm mảng con lớn nhất function MaxSubVector(a, i, j); begin if i=j then MaxSubVector := a[i] else begin m := (i+j)/2; wL := MaxSubVector(a, i, m); wR := MaxSubVector(a,m+1,j); wM := MaxVector(a, i, m) + MaxVector(a, m+1, j); MaxS ubVector := max(wL, wR, wM); end; end; 5.6.3) Thuật toán MaxVector(a, i, j): function MaxVector(a, i, j); begin maxsum := -∞; sum := 0; for k:=j downto i do begin sum := sum + a[k]; maxsum := max(sum, maxsum); end; MaxVector := maxsum; end; 5.6.4) Cài đặt chương trình #include #include #include /*nhập dữ liệu*/ void nhap(int n,int *a) { int i; printf("nhap cac phan tu"); for(i=0;i<=n-1;i++) { printf("a[%d]=",i); scanf("%d",&a[i]); } } /*Hiển thị dữ liệu đã nhập */ void hienthi(int n,int *a) { int i; for(i=0;i<=n-1;i++) { printf("a[%d]=%d",i,a[i]); printf("\n"); } } /*Hàm mảng con lớn nhất để đưa ra mảng con có giá trị lớn nhất bằng bao nhiêu*/ int mangconlonnhat(int n,int *a) { int i,j,k,max,s; max=a[0]; for(i=0;i<=n-1;i++) for(j=0;j<=n-1;j++) { s=0; for(k=i;k<=j;k++) s=s+a[k]; if(s>max) max=s; else max=max; } return max; } main() { int n ,a[5]; printf("nhap so phan tu can nhap"); scanf("%d",&n); nhap(n,a); hienthi(n,a); printf("gia tri lon nhat la %d",mangconlonnhat(n,a)); getch(); } *Sử dụng thuật toán chia để trị #include #include #include /*Tìm giá trị lớn nhất của 3 số*/ int max1(int a1,int b1,int c1) { int d[3]; int i; int max2; d[1]=a1; d[2]=b1; d[3]=c1; max2=d[1]; for(i=1;i<=3;i++) if(d[i]>max2) max2=d[i]; else max2=max2; return max2;} /*Tìm giá trị lớn nhất của 2 số*/ int max3(int a2, int b2) { int max4; if(a2<b2) max4=b2; else max4=a2; if(a2==b2) max4=a2; return max4; } /*nhập dữ liệu là các phần tử của mảng*/ void nhap(int n1,int *a) { int i; int t; printf("nhap cac phan tu"); for(i=1;i<=n1;i++) { printf("\na[%d]=",i); scanf("%d",&t); a[i]=t; } } /*hiển thị dữ liệu*/ void hienthi(int n2,int *a) { int i; for(i=1;i<=n2;i++) { printf("a[%d]=%d",i,a[i]); printf("\n"); } } /*hàm trả ra giá trị lớn nhất của mảng con*/ int maxsubvector(int *a,int i,int j) { int maxsubvector1; int wl; int wr; int wm; int m; if (i==j) maxsubvector1=a[i]; else { m=(j+i)/2; wl=maxsubvector(a,i,m); wr=maxsubvector(a,m+1,j); wm=maxvector(a,i,m)+maxvector(a,m+1,j); maxsubvector1=max1(wl,wr,wm); } return maxsubvector1; } int maxvector(int *a,int i,int j) { int k; int maxvector1; int maxsum=0; int sum=0; for(k=j;k>=i;k--) { sum=sum+a[k]; maxsum=max3(sum,maxsum); } maxvector1=maxsum; return maxvector1; } main() { int n ; int a[1000]; printf("nhap n"); scanf("%d",&n); nhap(n,a); hienthi(n,a); printf("ma tran con lon nhat la %d",maxsubvector(a,1,n)); getch(); } 5.6.5) Phân tích hiệu quả của thuật toán: Thời gian tính của MaxVector(a,i,j) là O(m) với m = j-i+1. Gọi T(n) là thời gian tính của thuật toán. Để đơn giản ta giả thuyết rằng n có dạng n = 2i. Ta có: T(1) = 1. Khi n>1, thuật toán sẽ chia mảng ra làm 2 nửa kích thước n/2 và thực hiện 2 lệnh gọi đệ quy đối với 2 nửa, mỗi lệnh thực hiện với thời gian T(n/2). Việc tính wM đòi hỏi thời gian: n/2 + n/2 = n. Vì vậy: T(n) = 2T(n/2) +n. Theo nguyên lý Master: T(n) = O(nlogn).