Bài giảng Lý thuyết tổ hợp - Chương 3: Bài toán liệt kê tổ hợp

Toán rời rạcPhần thứ nhấtLÝ THUYẾT TỔ HỢPCombinatorial Theory Fall 2009Toán rời rạcNội dungChương 0. Mở đầuChương 1. Bài toán đếmChương 2. Bài toán tồn tại Chương 3. Bài toán liệt kê tổ hợpChương 4. Bài toán tối ưu tổ hợpChương 3BÀI TOÁN LIỆT KÊToán rời rạcToán rời rạcNỘI DUNGGiới thiệu bài toánThuật toán và độ phức tạpPhương pháp sinhThuật toán quay luiGiíi thiÖu bµi to¸nBài toán đưa ra danh sách tất cả cấu hình tổ hợp thoả mãn một số tính chất cho trước được gọi là bài toán liệt kê tổ hợp. Do số lượng cấu hình tổ hợp cần liệt kê thường là rất lớn ngay cả khi kích thước cấu hình chưa lớn:Số hoán vị của n phần tử là n! Số tập con m phần tử của n phần tử là n!/(m!(n-m)!Do đó ần có quan niệm thế nào là giải bài toán liệt kê tổ hợpGiíi thiÖu bµi to¸nBài toán liệt kê tổ hợp là giải được nếu như ta có thể xác định một thuật toán để theo đó có thể lần lượt xây dựng được tất cả các cấu hình cần quan tâm. Một thuật toán liệt kê phải đảm bảo 2 yêu cầu cơ bản:Không được lặp lại một cấu hình,không được bỏ sót một cấu hình.Toán rời rạcChương 3. Bài toán liệt kêGiới thiệu bài toánThuật toán và độ phức tạpPhương pháp sinhThuật toán quay luiKhái niệm bài toán tính toánĐịnh nghĩa. Bài toán tính toán F là ánh xạ từ tập các xâu nhị phân độ dài hữu hạn vào tập các xâu nhị phân độ dài hữu hạn: F : {0, 1}*  {0, 1}*.Ví dụ: Mỗi số nguyên x đều có thể biểu diễn dưới dạng xâu nhị phân là cách viết trong hệ đếm nhị phân của nó.Hệ phương trình tuyến tính Ax = b có thể biểu diễn dưới dạng xâu là ghép nối của các xâu biểu diễn nhị phân của các thành phần của ma trận A và vectơ b.Đa thức một biến: P(x) = a0 + a1 x + ... + an xn, hoàn toàn xác định bởi dãy số n, a0, a1, ..., an, mà để biểu diễn dãy số này chúng ta có thể sử dụng xâu nhị phân. Khái niệm thuật toánĐịnh nghĩa. Ta hiểu thuật toán giải bài toán đặt ra là một thủ tục xác định bao gồm một dãy hữu hạn các bước cần thực hiện để thu được đầu ra cho một đầu vào cho trước của bài toán.Thuật toán có các đặc trưng sau đây:Đầu vào (Input): Thuật toán nhận dữ liệu vào từ một tập nào đó.Đầu ra (Output): Với mỗi tập các dữ liệu đầu vào, thuật toán đưa ra các dữ liệu tương ứng với lời giải của bài toán.Chính xác (Precision): Các bước của thuật toán được mô tả chính xác.Khái niệm thuật toánHữu hạn (Finiteness): Thuật toán cần phải đưa được đầu ra sau một số hữu hạn (có thể rất lớn) bước với mọi đầu vào.Đơn trị (Uniqueness): Các kết quả trung gian của từng bước thực hiện thuật toán được xác định một cách đơn trị và chỉ phụ thuộc vào đầu vào và các kết quả của các bước trước.Tổng quát (Generality): Thuật toán có thể áp dụng để giải mọi bài toán có dạng đã cho.Độ phức tạp của thuật toánĐộ phức tạp tính toán của thuật toán được xác định như là lượng tài nguyên các loại mà thuật toán đòi hỏi sử dụng. Có hai loại tài nguyên quan trọng đó là thời gian và bộ nhớ. Việc tính chính xác được các loại tài nguyên mà thuật toán đòi hỏi là rất khó. Vì thế ta quan tâm đến việc đưa ra các đánh giá sát thực cho các đại lượng này.Trong giáo trình này ta đặc biệt quan tâm đến đánh giá thời gian cần thiết để thực hiện thuật toán mà ta sẽ gọi là thời gian tính của thuật toán.Độ phức tạp của thuật toánRõ ràng: Thời gian tính phụ thuộc vào dữ liệu vào. Ví dụ: Việc nhân hai số nguyên có 3 chữ số đòi hỏi thời gian khác hẳn so với việc nhân hai số nguyên có 3*109 chữ số!Định nghĩa. Ta gọi kích thước dữ liệu đầu vào (hay độ dài dữ liệu vào) là số bít cần thiết để biểu diễn nó.Ví dụ: Nếu x, y là đầu vào cho bài toán nhân 2 số nguyên, thì kích thước dữ liệu vào của bài toán là n = log |x| + log |y| .Ta sẽ tìm cách đánh giá thời gian tính của thuật toán bởi một hàm của độ dài dữ liệu vào.Phép toán cơ bảnĐo thời gian tính bằng đơn vị đo nào?Định nghĩa. Ta gọi phép toán cơ bản là phép toán có thể thực hiện với thời gian bị chặn bởi một hằng số không phụ thuộc vào kích thước dữ liệu. Để tính toán thời gian tính của thuật toán ta sẽ đếm số phép toán cơ bản mà nó phải thực hiện. Các loại thời gian tínhChúng ta sẽ quan tâm đến:Thời gian tối thiểu cần thiết để thực hiện thuật toán với mọi bộ dữ liệu đầu vào kích thước n. Thời gian như vậy sẽ được gọi là thời gian tính tốt nhất của thuật toán với đầu vào kích thước n. Thời gian nhiều nhất cần thiết để thực hiện thuật toán với mọi bộ dữ liệu đầu vào kích thước n. Thời gian như vậy sẽ được gọi là thời gian tính tồi nhất của thuật toán với đầu vào kích thước n. Thời gian trung bình cần thiết để thực hiện thuật toán trên tập hữu hạn các đầu vào kích thước n. Thời gian như vậy sẽ được gọi là thời gian tính trung bình của thuật toán.Ký hiệu tiệm cậnAsymptotic Notation Q, O, WĐược xác định đối với các hàm nhận giá trị nguyên không âmDùng để so sánh tốc độ tăng của hai hàmĐược sử dụng để mô tả thời gian tính của thuật toánThay vì nói chính xác, ta có thể nói thời gian tính là, chẳng hạn, Q(n2)Ký hiệu  (g(n)) = {f(n) | tồn tại các hằng số c1, c2 và n0 sao cho 0  c1g(n)  f(n)  c2g(n), với mọi n  n0 } Đối với hàm g(n) cho trước, ta ký hiệu (g(n)) là tập các hàmTa nói rằng g(n) là đánh giá tiệm cận đúng cho f(n)Ví dụ10n2 - 3n = Q(n2)Với giá trị nào của các hằng số n0, c1, và c2 thì bất đẳng thức sau đây là đúng với n ≥ n0: c1n2 ≤ 10n2 - 3n ≤ c2n2Ta có thể lấy c1 bé hơn hệ số của số hạng với số mũ cao nhất, còn c2 lấy lớn hơn hệ số này, chẳng hạn: c1=9 n0 nào đóTa có: 2n2 ≥ 2n khi n ≥ 1 và n2 ≥ 1 khi n ≥ 1Vì vậy n2 + 2n + 1 ≤ 4*n2 với mọi n ≥ 1Như vậy hằng số c = 4, và n0=1Ví dụ: Ký hiệu O lớnRõ ràng: Nếu f(n) là O(n2) thì nó cũng là O(nk) với k > 2.Chứng minh: f(n) = n2 + 2n + 1O(n).Phản chứng. Giả sử trái lại, khi đó phải tìm được hằng số c và số n0 để cho: n2 + 2n + 1 ≤ c*n khi n ≥ n0Suy ra n2 n0 nào đóTa có: n2 - 2000n  0.5*n2 với mọi n ≥ 10000(vì n2 - 2000n - 0.5*n2 = 0.5*n2 - 2000n = n(0.5*n -2000)  0 khi n ≥ 10000)Như vậy hằng số c = 1, và n0=1Ví dụ: Ký hiệu Rõ ràng: Nếu f(n) là (n2) thì nó cũng là (nk) với k bCách nói về thời gian tínhNói “Thời gian tính là O(f(n))” hiểu là: Đánh giá trong tình huống tồi nhất (worst case) là O(f(n)). Thường nói: “Đánh giá thời gian tính trong tình huống tồi nhất là O(f(n))”Nghĩa là thời gian tính trong tình huống tồi nhất được xác định bởi một hàm nào đó g(n)Î O(f(n))“Thời gian tính là W(f(n))” hiểu là: Đánh giá trong tình huống tốt nhất (best case) là W(f(n)). Thường nói: “Đánh giá thời gian tính trong tình huống tốt nhất là W(f(n))”Nghĩa là thời gian tính trong tình huống tốt nhất được xác định bởi một hàm nào đó g(n) Î W(f(n))Đồ thị của một số hàm cơ bảnTên gọi của một số tốc độ tăngHàmTên gọilog nlogntuyến tínhn log nn log nn2bình phươngn3bậc 32nhàm mũnk (k là hằng số dương)đa thứcToán rời rạcVí dụ phân tích thuật toánVí dụ. Xét thuật toán tìm kiếm tuần tự để giải bài toán Đầu vào: n và dãy sốs1, s2, . . . , sn.Đầu ra: Vị trí phần tử có giá trị key hoặc là n+1 nếu không tìm thấy. function Linear_Search(s,n,key); begin i:=0; repeat i:=i+1; until (i>n) or (key = si); Linear_Search := i; end;Toán rời rạcVí dụ phân tích thuật toánCần đánh giá thời gian tính tốt nhất, tồi nhất, trung bình của thuật toán với độ dài đầu vào là n. Rõ ràng thời gian tính của thuật toán có thể đánh giá bởi số lần thực hiện câu lệnh i:=i+1 trong vòng lặp repeat. Nếu s1 = key thì câu lệnh i:=i+1 trong thân vòng lặp repeat thực hiện 1 lần. Do đó thời gian tính tốt nhất của thuật toán là (1).Nếu key không có mặt trong dãy đã cho, thì câu lệnh i:= i+1 thực hiện n lần. Vì thế thời gian tính tồi nhất của thuật toán là O(n).Toán rời rạcVí dụ phân tích thuật toánCuối cùng, ta tính thời gian tính trung bình của thuật toán. Nếu key tìm thấy ở vị trí thứ i của dãy (key = si) thì câu lệnh i := i+1 phải thực hiện i lần (i = 1, 2, ..., n), Nếu key không có mặt trong dãy đã cho thì câu lệnh i := i+1 phải thực hiện n lần. Từ đó suy ra số lần trung bình phải thực hiện câu lệnh i := i+1 là [(1 + 2 + . . . + n) + n] /(n+1) = [n(n+1)/2 + n]/(n+1).Ta có n/4  [n(n+1)/2 + n]/(n+1)  n. với mọi n  1.Vậy thời gian tính trung bình của thuật toán là (n).Toán rời rạcChương 3. Bài toán liệt kêGiới thiệu bài toánThuật toán và độ phức tạpPhương pháp sinhThuật toán quay lui3. PHƯƠNG PHÁP SINH3.1. Sơ đồ thuật toán3.2. Sinh các cấu hình tổ hợp cơ bảnSinh xâu nhị phân độ dài nSinh tập con m phần tử của tập n phần tửSinh hoán vị của n phần tửSƠ ĐỒ THUẬT TOÁNPhương pháp sinh có thể áp dụng để giải bài toán liệt kê tổ hợp đặt ra nếu như hai điều kiện sau được thực hiện:1) Có thể xác định được một thứ tự trên tập các cấu hình tổ hợp cần liệt kê. Từ đó có thể xác định được cấu hình đầu tiên và cấu hình cuối cùng trong thứ tự đã xác định.2) Xây dựng được thuật toán từ cấu hình chưa phải là cuối cùng đang có, đưa ra cấu hình kế tiếp nó. Thuật toán nói đến trong điều kiện 2) được gọi là Thuật toán Sinh kế tiếpThuật toán sinhprocedure Generate;Begin ; Stop:=false; while not stop do begin ; if (cấu hình đang có chưa là cuối cùng) then i. Dãy mới thu được sẽ là dãy cần tìm.Ví dụXét dãy nhị phân độ dài 10: b = 1101011111. Ta có i = 5. Do đó, đặt b5 = 1, và bi = 0, i = 6, 7, 8, 9, 10, ta thu đươc xâu nhị phân kế tiếp là 1101100000. 1101011111 1 1101100000Thuật toán sinh xâu kế tiếpprocedure Next_Bit_String;(* Sinh xâu nhị phân kế tiếp theo thứ tự từ điển của xâu đang có b1 b2 ... bn  1 1 ... 1 *)begin i:=n; while bi = 1 do begin bi = 0; i:=i-1; end; bi := 1;end;Sinh các tập con m phần tử của tập n phần tử Sinh các tập con m phần tử của tập n phần tử Bµi to¸n ®Æt ra lµ: Cho X = {1, 2, ... , n}. H·y liÖt kª c¸c tËp con m phÇn tö cña X. Mçi tËp con m phÇn tö cña X cã thÓ biÓu diÔn bëi bé cã thø tù gåm m thµnh phÇn a = (a1, a2, ... , am) tho¶ m·n 1  a1 aj+1 do j:=j-1; (* Tìm ak là số nhỏ nhất còn lớn hơn aj ở bên phải aj *) k:=n; while aj > ak do k:=k-1; Swap(aj, ak); (* đổi chỗ aj với ak *) (* Lật ngược đoạn từ aj+1 đến an *) r:=n; s:=j+1; while r>s do begin Swap(ar, as); (* đổi chỗ ar với as *) r:=r-1; s:= s+1; end;end;Chương 3. Bài toán liệt kêGiới thiệu bài toánThuật toán và độ phức tạpPhương pháp sinhThuật toán quay lui61Chương 3. Bài toán liệt kê3. THUẬT TOÁN QUAY LUIBacktracking AlgorithmNỘI DUNG3.1. Sơ đồ thuật toán3.2. Liệt kê các cấu hình tổ hợp cơ bảnLiệt kê xâu nhị phân độ dài nLiệt kê tập con m phần tử của tập n phần tửLiệt kê hoán vị3.3. Bài toán xếp hậuSƠ ĐỒ THUẬT TOÁNThuật toán quay lui (Backtracking Algorithm) là một thuật toán cơ bản được áp dụng để giải quyết nhiều vấn đề khác nhau. Bài toán liệt kê (Q): Cho A1, A2,..., An là các tập hữu hạn. Ký hiệu X = A1 A2  ... An = { (x1, x2, ..., xn): xi  Ai , i=1, 2, ..., n}. Giả sử P là tính chất cho trên X. Vấn đề đặt ra là liệt kê tất cả các phần tử của X thoả mãn tính chất P: D = { x = (x1, x2, ..., xn)  X: x thoả mãn tính chất P }.Các phần tử của tập D được gọi là các lời giải chấp nhận được. Ví dụTÊt c¶ c¸c bµi to¸n liÖt kª tæ hîp c¬ b¶n ®Òu cã thÓ ph¸t biÓu d­íi d¹ng bµi to¸n (Q)Bµi to¸n liÖt kª x©u nhÞ ph©n ®é dµi n dÉn vÒ viÖc liÖt kª c¸c phÇn tö cña tËp Bn = {(x1, ..., xn): xi  {0, 1}, i=1, 2, ..., n}.Bµi to¸n liÖt kª c¸c tËp con m phÇn tö cña tËp N = {1, 2, ..., n} ®ßi hái liÖt kª c¸c phÇn tö cña tËp: S(m,n) = {(x1,..., xm)Nm: 1 ≤ x1 else Backtrack(k+1); end; end; Lệnh gọi để thực hiện thuật toán quay lui là: Bactrack(1)Hai vấn đề mấu chốtĐể cài đặt thuật toán quay lui giải các bài toán tổ hợp cụ thể ta cần giải quyết hai vấn đề cơ bản sau:Tìm thuật toán xây dựng các tập UCV Sk.Tìm cách mô tả các tập này để có thể cài đặt thao tác liệt kê các phần tử của chúng (cài đặt vòng lặp qui ước for y  Sk do).Hiệu quả của thuật toán liệt kê phụ thuộc vào việc ta có xác định được chính xác các tập UCV này hay không.Chú ýNếu chỉ cần tìm một lời giải thì cần tìm cách chấm dứt các thủ tục gọi đệ qui lồng nhau sinh bởi lệnh gọi Backtrack(1) sau khi ghi nhận được lời giải đầu tiên. Nếu kết thúc thuật toán mà ta không thu được một lời giải nào thì điều đó có nghĩa là bài toán không có lời giải.Chú ýThuật toán dễ dàng mở rộng cho bài toán liệt kê trong đó lời giải có thể mô tả như là bộ (a1, a2, ..., an,...) độ dài hữu hạn, tuy nhiên giá trị của độ dài là không biết trước và các lời giải cũng không nhất thiết phải có cùng độ dài. Khi đó chỉ cần sửa lại câu lệnh if k = n then else Backtrack(k+1); thành if then else Backtrack(k+1);Cần xây dựng hàm nhận biết (a1, a2, ..., ak) đã là lời giải hay chưa. Cây liệt kê lời giải theo thuật toán quay luiGốc (lời giải rỗng)x1(x1)x2(x1, x2)Tập UCV S1Tập UCV S2 khi đã có (x1)Tập UCV S2 khi đã có (x1, x2)LiÖt kª x©u nhÞ ph©n ®é dµi nLiÖt kª x©u nhÞ ph©n ®é dµi nBµi to¸n liÖt kª x©u nhÞ ph©n ®é dµi n dÉn vÒ viÖc liÖt kª c¸c phÇn tö cña tËp Bn = {(x1, ..., xn): xi  {0, 1}, i=1, 2, ..., n}.Ta xÐt c¸ch gi¶i quyÕt hai vÊn ®Ò c¬ b¶n ®Ó cµi ®Æt thuËt to¸n quay lui:Râ rµng ta cã S1 = {0, 1}. Gi¶ sö ®· cã x©u nhÞ ph©n cÊp k-1 (b1, ..., bk-1), khi ®ã râ rµng Sk = {0,1}. Nh­ vËy, tËp c¸c UCV vµo c¸c vÞ trÝ cña lêi gi¶i ®­îc ®· x¸c ®Þnh.Để cài đặt vòng lặp liệt kê các phần tử của Sk, dễ thấy là ta có thể sử dụng vòng lặp for trên PASCAL: for y:= 0 to 1 do hoặc trên C: for (y=0;y#include #include int n, count;int b[20];void Ghinhan() { int i, j; count++; printf(“Xau thu %i. ",count); for (i=1 ; i#include #include int n, m, count;int a[20];void Ghinhan() { int i, j; count++; printf("Tap con thu %i. ",count); for (i=1 ; i#include #include int n, count;int b[20];int Ghinhan() { int i, j; count++; printf("Hoan vi thu %i. ",count); for (i=1 ; i#include int n, count;int a[20];int Ghinhan() { int i; count++; printf("%i. ",count); for (i=1; i<=n;i++) printf("%i ",a[i]); printf("\n");}int UCVh(int j, int k) {/* UCVh nhận giá trị 1 khi và chỉ khi j  Sk */ int i; for (i=1; i<k; i++) if ((j==a[i])||(fabs(j-a[i])==k-i)) return 0; return 1;}int Hau(int i){ int j; for (j=1; j<=n; j++) if (UCVh(j, i)){ a[i] = j; if (i == n) Ghinhan(); else Hau(i+1); }}int main() { printf("Input n = "); scanf("%i",&n); printf("\n==== RESULT ====\n"); count = 0; Hau(1); if (count == 0) printf("No solution!\n"); getch(); printf("\n Press Enter to finish... "); getchar(); }110Toán rời rạc - NĐNChú ýRõ ràng là bài toán xếp hậu không phải là luôn có lời giải, chẳng hạn bài toán không có lời giải khi n=2, 3. Do đó điều này cần được thông báo khi kết thúc thuật toán.Thuật toán trình bày ở trên là chưa hiệu quả. Nguyên nhân là ta đã không xác định được chính xác các tập UCV vào các vị trí của lời giải.Thuật toán làm việc như thế nàoThuật toán làm việc như thế nàoROW 1, COL 1Thuật toán làm việc như thế nàoROW 1, COL 11đã đặtXếp con hậu ở dòng 1 vào vị trí cột 1Thuật toán làm việc như thế nàoROW 1, COL 11đã đặtROW 2, COL 1Thử xếp con hậu ở dòng 2 vào vị trí cột 1Thuật toán làm việc như thế nàoROW 1, COL 11đã đặtROW 2, COL 2Thử xếp con hậu ở dòng 2 vào vị trí cột 2Thuật toán làm việc như thế nàoROW 1, COL 11đã đặtROW 2, COL 3Thử xếp con hậu ở dòng 2 vào vị trí cột 3Thuật toán làm việc như thế nàoROW 1, COL 12đã đặtROW 2, COL 3Chấp nhận xếp con hậu ở dòng 2 vào vị trí cột 3Thuật toán làm việc như thế nàoROW 1, COL 12đã đặtROW 2, COL 3ROW 3, COL 1Thử xếp con hậu ở dòng 3 vào cột đầu tiênThuật toán làm việc như thế nàoROW 1, COL 12đã đặtROW 2, COL 3ROW 3, COL 2Thử cột tiếp theoThuật toán làm việc như thế nàoROW 1, COL 12đã đặtROW 2, COL 3ROW 3, COL 3Thử cột tiếp theoThuật toán làm việc như thế nàoROW 1, COL 12đã đặtROW 2, COL 3ROW 3, COL 4Thử cột tiếp theoThuật toán làm việc như thế nào...không có vị trí đặt con hậu ở dòng 3.ROW 1, COL 12đã đặtROW 2, COL 3ROW 3, COL 4Thuật toán làm việc như thế nào Quay lại dịch chuyển con hậu ở dòng 2ROW 1, COL 11đã đặtROW 2, COL 3Thuật toán làm việc như thế nàoĐẩy con hậu ở dòng 2 sang cột thứ 4.ROW 1, COL 11đã đặtROW 2, COL 4Thuật toán làm việc như thế nàoXếp được con hậu ở dòng 2 ta tiếp tục xếp con hậu ở dòng 3ROW 1, COL 12đã đặtROW 2, COL 4Thuật toán làm việc như thế nàoThử xếp con hậu ở dòng 3 vào cột 1ROW 1, COL 12đã đặtROW 2, COL 4Thuật toán làm việc như thế nàoThử xếp con hậu ở dòng 3 vào cột 2ROW 1, COL 12đã đặtROW 2, COL 4Thuật toán làm việc như thế nàoXếp được con hậu ở dòng 3 ta tiếp tục xếp con hậu ở dòng 4: Thử cột 1ROW 1, COL 12đã đặtROW 2, COL 4Thuật toán làm việc như thế nàoThử xếp được con hậu ở dòng 4 vào cột 2ROW 1, COL 12đã đặtROW 2, COL 4Thuật toán làm việc như thế nàoThử xếp được con hậu ở dòng 4 vào cột 3ROW 1, COL 12đã đặtROW 2, COL 4Thuật toán làm việc như thế nàoThử xếp được con hậu ở dòng 4 vào cột 4ROW 1, COL 12đã đặtROW 2, COL 4Thuật toán làm việc như thế nàoKhông xếp được con hậu ở dòng 4ROW 1, COL 12đã đặtROW 2, COL 4Thuật toán làm việc như thế nàoQuay lại tìm vị trí mới cho con hậu ở dòng 3: Thử cột 3ROW 1, COL 12đã đặtROW 2, COL 4Thuật toán làm việc như thế nàoQuay lại tìm vị trí mới cho con hậu ở dòng 3: Thử cột 4ROW 1, COL 12đã đặtROW 2, COL 4Thuật toán làm việc như thế nàoKhông có cách xếp mới cho con hậu ở dòng 3ROW 1, COL 12đã đặtROW 2, COL 4Thuật toán làm việc như thế nàoQuay lại tìm cách xếp mới cho con hậu ở dòng 2: Không có ROW 1, COL 12đã đặtROW 2, COL 4Thuật toán làm việc như thế nàoQuay lại tìm cách xếp mới cho con hậu ở dòng 1: Chuyển sang cột 2 ROW 1, COL 12đã đặtROW 2, COL 4Mét lêi gi¶i cña bµi to¸n xÕp hËu khi n = 8 140Toán rời rạc - NĐN The End141Questions?Toán rời rạc