Nội dung

Bài 3: Bài toán liệt kê tổ hợp BÀI 3: BÀI TOÁN LIỆT KÊ TỔ HỢP Giới thiệu Bài học này trình bày nội dung bài toán liệt kê tổ hợp, bài toán này quan tâm đến tất cả các cấu hình có thể có, vì thế lời giải của nó cần được biểu diễn dưới dạng thuật toán “vét cạn” tất cả các cấu hình. Lời giải trong từng trường hợp cụ thể sẽ được máy tính giải quyết nhờ chạy một chương trình cài đặt theo thuật toán đã tìm. Bài toán liệt kê thường được “làm nền” cho nhiều bài toán khác. Hiện nay, một số bài toán tổ hợp vẫn chưa có cách nào giải ngoài cách giải liệt kê. Khó khăn chính của cách giải này là có quá nhiều cấu hình, tuy nhiên tính khả thi của phương pháp liệt kê ngày càng được nâng cao nhờ sự tiến bộ nhanh chóng về chất lượng của máy tính điện tử. Nội dung Mục tiêu  Giới thiệu bài toán liệt kê tổ hợp Sau khi học bài này, các bạn có thể:  Nắm được yêu cầu của bài toán liệt kê tổ hợp.  Sử dụng thuật toán quay lui trong việc thực hiện bài toán liệt kê tổ hợp.  Liệt kê được một số câu hình cơ bản như: liệt kê dãy nhị phân, liệt kê hoán vị, liệt kê tổ hợp. Sử dụng các kiến thức của bài toán liệt kê trong việc giải quyết một số tình huống thực tế.  Trình bày thuật toán quay lui  Liệt kê một số cấu hình cơ bản Thời lượng học  6 tiết v1.0 69 Bài 3: Bài toán liệt kê tổ hợp TÌNH HUỐNG DẪN NHẬP Tình huống “Tìm cách xếp 8 quân Hậu trên bàn cờ Vua sao cho không có quân nào ăn được quân nào”. Câu hỏi Có bao nhiêu cách xếp hậu thỏa mãn yêu cầu của bài toán và đó là những cách nào? 70 v1.0 Bài 3: Bài toán liệt kê tổ hợp 3.1. Giới thiệu bài toán Bài toán liệt kê tổ hợp nhằm lần lượt đưa ra từng cấu hình sao cho không bỏ sót và không trùng lặp. Như vậy, khác với những cách giải thông thường, trong đó trình bày các lập luận, chứng minh, hay các tính toán qua các công thức, lời giải của bài toán này phải được trình bày dưới dạng thuật toán, trong đó chỉ ra các bước xây dựng từng cấu hình thỏa mãn điều kiện đã nêu. Vào thời chưa có máy tính, hoặc máy tính còn dưới dạng sơ khai, việc liệt kê chủ yếu nhờ vào sức thủ công, vì thế kết quả rất hạn chế. Khi đó, việc liệt kê chỉ được thực hiện trên những bài toán kích thước không đáng kể, nhằm minh họa một số khái niệm hay kiểm chứng một vài kết quả đơn giản. Hiện nay, với sự phát triển mạnh mẽ của máy tính, tốc độ lên tới hàng triệu phép tính trong một giây, việc liệt kê nhờ máy tính ngày càng khả thi và giải pháp liệt kê ngày càng được chú ý, nhất là nhờ nó mà một số bài toán tồn đọng hàng thế kỷ đã được giải quyết. Với sự hỗ trợ của máy tính, bài toán liệt kê thường được làm nền để giải quyết những bài toán tổ hợp khác (các bài toán đếm, tồn tại, tối ưu) trong những tình huống không còn lựa chọn tốt hơn. Khó khăn chính của bài toán này là số cấu hình thường quá lớn mà việc chờ đợi kết quả vượt quá khả năng ngay cả khi thực thi bằng máy tính. Để khắc phục khó khăn này, một mặt con người cố gắng xây dựng những thuật toán hữu hiệu, một mặt nâng cao khả năng xử lý của máy tính. Việc nghiên cứu chế tạo các máy tính có nhiều bộ xử lý đồng thời với việc phát triển các giải thuật song song chắc chắn sẽ nâng cao tính khả thi của những bài toán liệt kê lên rất nhiều. Bài này giới thiệu một thuật toán cơ bản mang tính phổ dụng của toán hữu hạn cho phép liệt kê các cấu hình và cách cài đặt nó bằng một chương trình trên máy tính. 3.2. Thuật toán quay lui Thuật toán quay lui thực chất là thuật toán duyệt tất cả các khả năng xây dựng cấu hình sao cho không bỏ sót và không trùng lặp. Thông thường một cấu hình được biểu diễn dưới dạng một bộ có thứ tự (x1, x2, ..., xn), trong đó các thành phần được xác định từ những tập giá trị (hữu hạn) nào đấy, thỏa mãn những điều kiện đề ra. Nội dung của thuật toán quay lui là lần lượt xác định các thành phần của cấu hình bắt đầu từ thành phần đầu tiên. Để xác định một thành phần, ta thử tất cả các giá trị khả dĩ cho nó trong trạng thái các thành phần trước đấy đã được xác định. Vì thế, thích hợp hơn cả là phát biểu thuật toán này bằng quy nạp. Giả sử đã xác định được các thành phần x1, x2, ..., xi − 1. Dưới đây là bước xác định thành phần xi (bước thử thứ i). Gọi Si là tập các giá trị thử cho xi (gọi là tập đề cử, nó được xác định từ những điều kiện của cấu hình). Duyệt tất cả các giá trị j thuộc Si và thử nó cho xi. Xảy ra hai tình huống:  Có một j mà việc thử cho xi là chấp nhận được (dựa vào các điều kiện của cấu hình). Khi đó gán j cho xi. Nếu i = n (xi là thành phần cuối) thì liệt kê được một cấu hình (sau đó duyệt j tiếp, nếu hết, lùi lại bước trước để thử giá trị khác cho xn − 1), trái lại sang bước i + 1 để xác định thành phần kế tiếp.  Mọi j thuộc Si đều không được chấp nhận. Khi đó lùi về bước trước để thử giá trị khác cho xi − 1. v1.0 71 Bài 3: Bài toán liệt kê tổ hợp Để không bỏ sót, tập giá trị đề cử Si cho xi cần phải xem xét một cách cẩn thận, mặc dù không phải giá trị đề cử nào cũng chấp nhận được, nhưng nếu bỏ sót giá trị đề cử thì sẽ dẫn đến bỏ sót cấu hình. Để không trùng lặp, trong mỗi bước tìm kiếm, ta phải lưu lại những thông tin cần thiết để khi lùi lại, không thử những giá trị đã thử rồi. Những thông tin này cần được cất giữ theo cơ chế vào sau, ra trước (ngăn xếp). Để cài đặt, tốt hơn cả là dùng một ngôn ngữ lập trình cho phép gọi đệ quy. Với những ngôn ngữ này, ta tận dụng được cơ chế ngăn xếp của việc đệ quy mà không phải tự tổ chức lấy ngăn xếp. Điều này làm việc viết chương trình trở nên đơn giản rất nhiều. Hiện nay các ngôn ngữ thuật toán được cài đặt trên máy tính như C, Pascal đều có khả năng này. Nội dung của thuật toán quay lui có thể mô tả qua thủ tục đệ quy dưới đây (viết mô phỏng theo ngôn ngữ Pascal): Thuật toán quay lui PROCEDURE TRY (i: INTEGER); VAR j: INTEGER; BEGIN FOR (j thuộc Si) DO IF (chấp nhận j) THEN BEGIN xi := j; IF (i = n) THEN TRY(i+1); END; END; (ghi nhận một cấu hình) ELSE Thủ tục TRY(i) xác định xi bằng cách duyệt tất cả các giá trị đề cử cho nó (vòng lặp FOR). Trong thủ tục có khai báo biến địa phương j dùng để duyệt các giá trị đề cử (không mất tính tổng quát, ta có thể giả thiết các giá trị này là nguyên). Khi xác định xong xi, việc tiến hành bước tiếp được thực hiện bằng lời gọi đệ quy TRY(i+1). Khi xong vòng lặp duyệt, thủ tục TRY(i) kết thúc, và trở về vòng lặp duyệt của TRY(i−1) để tiếp tục thử các giá trị đề cử khác cho xi−1. Vòng lặp đệ quy lồng nhau của TRY(i) 72 v1.0 Bài 3: Bài toán liệt kê tổ hợp Trong TRY(i), mệnh đề (chấp nhận j) là một biểu thức lôgic, không những phụ thuộc j mà trong nhiều tình huống còn phụ thuộc vào các giá trị đã thử ở những bước trước, vì thế để tính biểu thức này, ta cần tổ chức thêm những biến phụ (được khai báo toàn cục) ghi nhận sự thay đổi trạng thái của bài toán sau mỗi bước tìm kiếm (vì thế các biến này được gọi là các biến trạng thái). Độ phức tạp của những biến này phụ thuộc vào độ phức tạp của cấu hình cần liệt kê. Nếu có mặt những biến như vậy, trong TRY(i) cần thêm vào các khối lệnh (ghi nhận trạng thái mới), (trả về trạng thái cũ), nhằm cập nhật lại giá trị của các biến này tại những nơi thích hợp, như đề nghị dưới đây: Vòng lặp đệ quy lồng nhau của Try(i) PROCEDURE TRY (i: INTEGER); VAR j: INTEGER; BEGIN FOR (j thuộc Si) DO IF (chấp nhận j) THEN BEGIN xi := j; (ghi nhận trạng thái mới); IF (i = n) THEN (ghi nhận một cấu hình) ELSE TRY(i+1); (trả về trạng thái cũ); END; END; TRY(i) được khởi động bằng lời gọi TRY(1) trong chương trình chính. Khi TRY(1) kết thúc, quá trình liệt kê được hoàn tất. Dĩ nhiên, trước khi gọi TRY(1), trong chương trình chính cần phải gọi các thủ tục nhập dữ liệu và khởi gán các giá trị ban đầu. Cũng nên thiết kế một thủ tục làm nhiệm vụ (ghi nhận một cấu hình) được gọi trong TRY(i), nhằm xử lý cấu hình nhận được cho phù hợp với yêu cầu của bài toán (có thể đưa ra màn hình, ghi ra file, hoặc áp dụng một thao tác nào đấy trên cấu hình này). Chẳng hạn, nếu dùng liệt kê để giải bài toán đếm, thì thủ tục này đơn giản là tăng biến đếm lên một đơn vị (biến đếm cần được khởi gán 0), nếu chỉ cần chứng minh có cấu hình (bài toán tồn tại), thì khi nhận được cấu hình đầu tiên, ta có thể kết thúc ngay. Thứ tự liệt kê các cấu hình phụ thuộc vào thứ tự duyệt các giá trị đề cử cho mỗi thành phần. Thông thường các giá trị đề cử được sắp xếp tăng dần, khi đó các biểu diễn cấu hình sẽ được xếp theo thứ tự từ điển. Tên gọi thuật toán quay lui, xuất phát từ chính nội dung của nó. Thuật toán này cũng được biết đến với tên gọi thuật toán thử-sai. Cũng chú ý rằng, trên đây chỉ là mô hình có tính chất định hướng cho việc xây dựng chương trình thực hiện thuật toán quay lui. Nội dung cụ thể của nó phụ thuộc vào kết quả phân tích cấu hình, trong đó việc tổ chức dữ liệu để mô tả cấu hình, việc xác định các tập đề cử, việc xây dựng các biến trạng thái và biểu thức kiểm tra giá trị thử, ... đóng một vai trò quan trọng trong việc quyết định chất lượng của chương trình. Ngoài việc nắm vững ngôn ngữ được dùng, người lập trình cần phải có những kiến thức toán học nhất định, liên quan đến vấn đề đang xét. v1.0 73 Bài 3: Bài toán liệt kê tổ hợp Mục dưới đây đưa ra một số thí dụ minh họa việc dùng thuật toán quay lui để liệt kê một số cấu hình đơn giản, trong đó các chương trình đều được cài đặt theo cùng khuôn dạng như sau: Ví dụ: Thuật toán quay lui PROCEDURE INIT; PROCEDURE OUT; PROCEDURE TRY(i: INTEGER); BEGIN (* chương trình chính*) INIT; TRY(1); END. Thủ tục INIT nhập dữ liệu và khởi gán các giá trị ban đầu, thủ tục OUT đếm và đưa ra cấu hình x1, x2, ..., xn mỗi khi xây dựng xong, thủ tục TRY(i) thực hiện việc xác định xi bằng đệ quy. Trong các thủ tục trên, thủ tục TRY(i) là quan trọng nhất. Vì thế trong các thí dụ minh họa, chủ yếu chúng tôi trình bày việc phân tích và thiết kế thủ tục này. 3.3. Liệt kê một số cấu hình đơn giản 3.3.1. Liệt kê dãy nhị phân Một dãy nhị phân độ dài n (còn được gọi là chuỗi n bit) là một bộ có thứ tự gồm n thành phần (x1, x2, ..., xn) trong đó mỗi thành phần xi nhận một trong hai giá trị 0, 1. Trong bài toán đếm ta đã biết số các dãy nhị phân độ dài n là 2n, bây giờ ta giải bài toán liệt kê tất cả các dãy nhị phân độ dài n bằng cách viết một chương trình theo mô hình đã cài đặt. Theo định nghĩa dãy nhị phân, giá trị đề cử cho xi là {0, 1}, việc chọn giá trị 0 hay 1 cho thành phần này mặc nhiên được chấp nhận, không phụ thuộc vào các giá trị của các thành phần trước đấy. Đây là trường hợp mà TRY(i) có dạng đơn giản nhất, trong đó không có các khối (chấp nhận j), (ghi nhận trạng thái mới), (trả về trạng thái cũ). Thuật toán tìm kiếm quay lui các dãy nhị phân PROCEDURE TRY (i: INTEGER); VAR j: INTEGER; BEGIN FOR j := 0 TO 1 DO BEGIN xi := j; IF (i = n) THEN OUT ELSE TRY(i+1); END; END; 74 v1.0 Bài 3: Bài toán liệt kê tổ hợp Các bước tìm kiếm quay lui các dãy nhị phân độ dài 3 có thể mô tả bởi cây liệt kê dưới đây: 1 0 0 0 1 0 1 0 1 0 1 1 0 1 Kết quả chạy chương trình với n = 3, ta được 23 = 8 dãy nhị phân theo thứ tự như sau: 1) 0 0 0 5) 1 0 0 2) 0 0 1 7) 1 0 1 3) 0 1 0 8) 1 1 0 4) 0 1 1 9) 1 1 1 3.3.2. Liệt kê hoán vị Một hoán vị của các phần tử 1, 2, ..., n là một cách xếp thứ tự của các phần tử đó. Như thế ta có thể biểu diễn hoán vị đang xét như một bộ có thứ tự gồm n thành phần (x1, x2, ..., xn) trong đó các thành phần xi lấy những giá trị khác nhau trên tập {1, 2, ..., n}. Từ đó nhận được tập đề cử cho xi là {1, 2, ..., n} và điều kiện chấp nhận j cho xi là j không được trùng với các giá trị đã gán cho các thành phần trước đấy (j chưa được dùng). Để kiểm tra điều kiện này, ta xây dựng các biến lôgic bj (j = 1, 2, ..., n), đóng vai trò các biến trạng thái, trong đó mỗi biến bj kiểm soát trạng thái của j với quy ước bj bằng TRUE nếu j chưa được dùng và bj bằng FALSE nếu trái lại. Khi đó, mệnh đề (chấp nhận j) sẽ là (bj) và các câu lệnh (ghi nhận trạng thái mới), (trả về trạng thái cũ) sẽ tương ứng với các lệnh gán (bj := FALSE) và (bj := TRUE). Các biến trạng thái bj cần phải được khởi gán tất cả bằng TRUE trước khi gọi TRY(1). Thuật toán tìm kiếm quay lui các hoán vị PROCEDURE TRY (i: INTEGER); VAR j: INTEGER; BEGIN FOR j := 1 TO n DO IF (bj) THEN BEGIN xi := j; bj := FALSE; IF (i = n) THEN OUT ELSE TRY(i+1); bj := TRUE; END; END; Các bước tìm kiếm quay lui các hoán vị độ dài 3 có thể mô tả bởi cây liệt kê dưới đây: v1.0 75 Bài 3: Bài toán liệt kê tổ hợp 1 3 2 1 2 3 3 2 1 3 2 1 3 1 2 Kết quả chạy chương trình với n = 3, ta được 3! = 6 hoán vị theo thứ tự như sau: 1) 1 2 3 4) 2 3 1 2) 1 3 2 5) 3 1 2 3) 2 1 3 7) 3 2 1 3.3.3. Liệt kê tổ hợp Một tổ hợp chập m của n phần tử {1, 2, ..., n} (m ≤ n) là một tập con m phần tử của tập đã cho. Mỗi tập con như vậy được biểu diễn dưới dạng một bộ không kể thứ tự (x1, x2, ..., xm) gồm m thành phần nhận những giá trị khác nhau từ tập {1, 2, ..., n}. Như thế các thành phần của nó phải được ràng buộc thêm điều kiện: 1 ≤ x1 < x2 < ... < xm ≤ n. Nhận xét rằng để điều kiện trên thỏa mãn, cần và đủ là tại mỗi bước thử thứ i (i = 1, 2, ..., m) giá trị của xi phải thỏa mãn: xi−1+1 ≤ xi ≤ n−m+i (bổ sung x0 = 0) từ đó nhận được tập đề cử cho xi là {xi−1+1, ..., n−m+i} và mọi giá trị thuộc tập này đều mặc nhiên được chấp nhận. Với tập đề cử đã chọn, TRY(i) trở thành đơn giản giống như trường hợp liệt kê dãy nhị phân. PROCEDURE TRY (i: INTEGER); VAR j: INTEGER; BEGIN FOR j := xi−1+1 TO n−m+i DO BEGIN xi := j; IF (i = m) THEN OUT ELSE TRY(i+1); END; END; Các bước tìm kiếm quay lui các tổ hợp chập 2 của 4 có thể mô tả bởi cây liệt kê dưới đây: 1 2 3 2 4 3 3 4 4 Kết quả chạy chương trình với m = 2, n = 4 ta được C42  6 tổ hợp theo thứ tự như sau: 1) 1 2 2) 1 3 3) 1 4 76 4) 2 3 5) 2 4 6) 3 4 v1.0 Bài 3: Bài toán liệt kê tổ hợp 3.4. Một số liệt kê khác Trong mục này, ta sẽ xét một số bài toán liệt kê có liên quan đến các quân cờ mà việc xây dựng các cấu hình của chúng là những thí dụ điển hình của thuật toán quay lui. 3.4.1. Bài toán xếp Hậu Nội dung bài toán như sau: “Tìm cách xếp 8 quân Hậu trên bàn cờ Vua sao cho không có quân nào ăn được quân nào”. Lời giải được tìm kiếm bằng cách xếp dần các quân Hậu, sao cho quân Hậu mới xếp không nằm ở vị trí bị các quân Hậu đã xếp khống chế. Nếu không tìm được một vị trí như vậy, cần xếp lại quân Hậu trước. Thực chất cách giải này là thử lần lượt tất cả vị trí để xếp Hậu và khi cần thiết thì quay lui. Rõ ràng là cách giải này có thể áp dụng cho mọi kích thước n (bàn cờ n×n và n quân Hậu) và đưa ra được tất cả các cách xếp có thể. Ta sẽ lập một chương trình, theo mô hình quay lui đã trình bày, liệt kê tất cả các cách xếp Hậu, thỏa mãn điều kiện đã nêu, với kích thước n cho trước. Đầu tiên là việc biểu diễn cách xếp Hậu. Đánh số cột và dòng của bàn cờ từ 1 đến n. Vì quân Hậu ăn theo dòng nên mỗi dòng xếp đúng một quân Hậu (quân Hậu i bầy vào dòng i, i = 1, 2, ..., n). Như thế vị trí của các quân Hậu được xác định nếu biết tọa độ cột của chúng. Điều này gợi ý biểu diễn mỗi cách xếp Hậu như là một bộ có thứ tự (x1, x2, ..., xn) trong đó xi là tọa độ cột của quân Hậu i. Khi đó, tập đề cử cho xi sẽ là {1, 2, ..., n}. Giá trị j thử cho xi được chấp nhận khi và chỉ khi ô (i, j) không bị các quân Hậu trước chiếu đến (còn tự do). Trạng thái của ô (i, j) cần được xác định trước khi thử giá trị j cho xi. Điều này được thực hiện bằng cách tổ chức các biến trạng thái thích hợp, suy từ luật ăn quân của quân Hậu (ngang, dọc và hai đường chéo): 1 2 .. .. j 1 .. .. n đường chéo x+y = i+j 2 .. i ● .. .. .. đường chéo x−y = i−j n Các ô bị khống chế bởi quân Hậu ở ô (i, j) Để ô (i, j) là tự do, cần hội các điều kiện: dòng i tự do, cột j tự do và hai đường chéo qua (i, j) là tự do. Các dòng không cần xét vì mỗi dòng chỉ có đúng một quân Hậu. Để kiểm soát các cột, ta đưa vào các biến lôgic a1, a2, ..., an trong đó aj bằng TRUE nếu cột j còn tự do và bằng FALSE nếu trái lại. Các đường chéo có hai dạng: phương trình x + y = k và phương trình x − y = k (x là tọa độ dòng, y là tọa độ cột, k là hằng số). Với đường chéo dạng x + y = k, giá trị của k biến thiên từ 2 đến 2n, vì thế để kiểm soát chúng ta đưa vào các biến lôgic b2, b3, ..., b2n trong đó bk bằng TRUE nếu đường chéo này còn tự do và bằng FALSE nếu trái lại. Với đường chéo dạng x − y = k, v1.0 77 Bài 3: Bài toán liệt kê tổ hợp giá trị của k biến thiên từ 1 − n đến n − 1, vì thế để kiểm soát chúng ta đưa vào các biến lôgic c1−n, c2−n, ..., cn−1 (chú ý giá trị chỉ số có thể âm) trong đó ck bằng TRUE nếu đường chéo này còn tự do và bằng FALSE nếu trái lại. Khi đó điều kiện (chấp nhận j cho xi) sẽ là biểu thức lôgic (aj AND bi+j AND ci−j), câu lệnh (ghi nhận trạng thái mới) sẽ là các lệnh gán (aj: = FALSE; bi+j: = FALSE; ci−j: = FALSE) và câu lệnh (trả về trạng thái cũ) sẽ là các lệnh gán (aj: = TRUE; bi+j: = TRUE; ci−j: = TRUE). Các biến trạng thái aj (j = 1, ..., n), bk (k = 2, ..., 2n), ck (k = 1−n, ..., n−1) cần được khởi gán TRUE trước khi gọi TRY(1). PROCEDURE TRY (i: INTEGER); VAR j: INTEGER; BEGIN FOR j := 1 TO n DO IF (aj AND bi+j AND ci−j) THEN BEGIN xi := j; aj := FALSE; bi+j := FALSE; ci−j := FALSE; IF (i = n) THEN OUT ELSE TRY(i+1); aj := TRUE; bi+j := TRUE; ci−j := TRUE; END; END; Các bước tìm kiếm quay lui các cách xếp 4 quân Hậu trên bàn cờ kích thước 4 có thể mô tả bởi cây liệt kê dưới đây: 1 4 3 2 2 3 4 1 1 4 3 2 4 1 2 3 Kết quả chạy chương trình với n = 4 ta được 2 cách xếp Hậu theo thứ tự sau: ● ● ● ● ● ● ● ● 1) (2, 4, 1, 3) 2) (3, 1, 4, 2) Với n = 8 (bàn cờ thông thường), chương trình cho 92 lời giải. Cách xếp đầu tiên tìm được là: 78 v1.0