Bài giảng Các chiến lược thiết kế thuật toán

Các chiến lược thiết kế thuật toán Top-down solution strategies Chia để trị (Divider and Conque) direct solution strategies Tham ăn (greedy) backtracking strategies Quay lui (simple backtracking) bottom-up solution strategies Quy hoạch động (Dynamic programming) randomized strategies 1. Chia để trị Phương pháp - áp dụng rộng rãi nhất Tư tưởng: Phân btoán cần giải thành btoán con. Btoán con lại được tiếp tục phân thành các btoán con nhỏ hơn, cứ thế cho đến khi nhận được btoán con hoặc là đã có thuật giải hoặc có thể dễ dàng đưa ra giải thuật. Kết hợp no các btoán con để nhận được no btoán cần giải. Top-down Btoán con có cùng dạng với btoán ban đầu, có cỡ nhỏ hơn đệ quy Phương pháp void DivideConquer(A, x) {//Tìm no x của bài toán A If A đủ nhỏ Solve(A); else { Phân A thành các bài toán con A1, A2, .., Am. For (i=1;i bk Trường hợp a=bk a0 do begin while sk  do begin chọn xk  Sk; Sk:=Sk - {xk}; if (x1,..,xk) là n0 then viết ra n0; k:=k+1 xác định Sk end; k:=k-1; end; End; {of Procedure} Ví dụ: bài toán 8 hậu n0 (x1, x2, .., x8), xi: tọa độ cột của quân hậu đứng ở hàng i (i=1,..,8), xi {1, 2..,8} Kô cùng cột xi  xj (i, xi) kô cùng đường chéo với (j, xj) thì |i-j||xi-xj| Nếu đã chọn được (x1, x2,.., xk-1) thì xk được chọn nếu thỏa xk  xi |xk-xi| |k-i| với 1  i  k-1 Procedure Queen; {Vector được bd bởi mảng x[1..8]. Với mỗi k, lần lượt cho x[k] nhận giá trị từ 1→8 và ktra các đk mà x[k] cần thỏa mãn, nếu kô thỏa OK=false thì tăng x[k] lên 1} Begin k:=1; x[k]:=0; While k > 0 do Begin x[k]:=x[k] + 1; ok:=false; while (x[k]x[k]) and (abs(x[i]- x[k])abs(i-k)) then i:=i+1 else ok:=false; end; If ok then if k=8 then In(x) else if k<8 then begin k:=k+1; x[k]:=0; end else k:=k-1; End;{of while} End; {of Procedure} Ví dụ: Liệt kê dãy nhị phân độ dài n Liệt kê tổ hợp chập m của {1, 2, .., n} Liệt kê các hoán vị của {1, 2, .., n} A là tập n số nguyên dương, M số nguyên dương cho trước. Tìm tập con S  A sao cho Ai (AiS)=M Quy hoạch động Quá trình phân chia gặp nhiều lần bài toán con, kỹ thuật top-down lặp lại → kém hiệu quả Giải bài toán con → kết hợp n0 bài toán con → được n0 cần giải Ví dụ: tính hệ số nhị thức C(k, n) C(i, j)=1 nếu i=0 hoặc i=j C(i, j)=C(i, j-1) + C(i-1, j-1) nếu 0<i<j Đệ quy Function Coef(k, n:integer):integer; Begin if (k=0) or (k=n) then Coef:=0 else Coef:=Coef(k, n-1) + Coef(k-1, n-1) End; Cụ thể: Coef(3, 5) Cách tiếp cận khác để tính C(k, n) ta tính C(i, j) với i < k, j < n xuất phát từ C(0, j)=1 với j  n. Dùng bảng để lưu các giá trị đã tính (tránh được tính lại nhiều lần) j 0 1 2 3 4 5 i 0 1 1 1 1 1 1 1 1 2 1 3 1 Begin for j:=1 to n do C[0, j]:=1; for i:=1 to k do begin C[i, i]:=1; for j:=i+1 to n do C[i, j]:=C[i, j-1] + C[i-1, j-1]; end; End; Quy hoạch động là kỹ thuật từ dưới lên (bottom-up) Tư tưởng: xuất phát từ những trường hợp riêng đơn giản nhất của bài toán, thường thấy ngay n0. Kết hợp n0 của chúng, nhận được n0 btoán con có cỡ lớn hơn Kết hợp n0 của btoán con này để nhận được n0 btoán lớn hơn nữa, cứ tiếp tục cho đến khi nhận được n0 bài toán đã cho. để giải bài toán bằng QHĐ, cần tiến hành những công việc sau: Tìm n0 btoán con đơn giản nhất Tìm ra CT (hay quy tắc) xây dựng n0 btoán con thông qua n0 của các btoán con cỡ nhỏ hơn. Tạo bảng lưu các n0 btoán con. Sau đó tính n0 các btoán con theo công thức đã tìm và lưu vào bảng. từ bảng đã làm đầy tìm cách xây dựng n0btoán Ví dụ:Bài toán xếp ba lô (new trộm, old trộm) Dãy con chung của 2 dãy số Bài toán người bán hàng Bài tập Tính số catalan Xét tích các số Mi (i=1,2,..,n): M=M1.M2..Mn. Hỏi có bao nhiêu cách chèn cặp dấu ngoặc vào tích này để được các cách bd khác nhau của tích này. ABCD: ((AB)C)D (AB)(CD) (A(BC))D A((BC)D) A(B(CD)) T(n)