Bài 2 · Tập tối đại

GenMax — tìm các tập tối đại

GenMax đi tìm các tập tối đại, tức là những tập phổ biến lớn nhất, không thể mở rộng thêm mà vẫn phổ biến. Nó dò theo lối quay lui, và để khỏi làm việc thừa, nó luôn kiểm tra trước xem một nhánh có nằm gọn trong một tập tối đại đã tìm được hay chưa; nếu rồi thì cắt bỏ cả nhánh.

1. Ý tưởng chung

Một tập gọi là tối đại khi nó phổ biến nhưng mọi cách thêm một mặt hàng vào đều khiến nó không còn phổ biến nữa. Đây là cách lưu gọn nhất, tuy không giữ lại độ phổ biến của từng tập con.

GenMax dò theo lối quay lui. Với một phần đầu đang xét, nó giữ một danh sách các mặt hàng có thể thêm vào mà vẫn phổ biến; ta tạm gọi đó là danh sách mở rộng. Nó chọn một mặt hàng trong danh sách, nối vào phần đầu để đi sâu hơn, rồi lại lập danh sách mở rộng mới cho phần đầu dài hơn đó.

Mẹo quan trọng để chạy nhanh, gọi là kiểm tra bao trùm: trước khi lao vào một nhánh, hãy thử ghép phần đầu hiện tại với toàn bộ các mặt hàng còn lại trong danh sách mở rộng. Nếu cái tập gộp đó đã nằm gọn trong một tập tối đại tìm được từ trước, thì chắc chắn nhánh này không cho ra tập tối đại nào mới, ta cắt bỏ luôn cho đỡ mất công.

2. Hai quy tắc cần nhớ

Lập danh sách mở rộng

Để biết một mặt hàng có còn ghép được với phần đầu hay không, ta lấy phần chung của danh sách giao dịch giữa hai bên rồi đếm. Nếu số đó còn đạt ngưỡng phổ biến thì mặt hàng đó được giữ trong danh sách mở rộng.

Cắt tỉa bằng kiểm tra bao trùm

Nếu phần đầu, sau khi nối thêm tất cả các mặt hàng còn lại của danh sách mở rộng, lại là tập con của một tập tối đại đã có, thì bỏ cả nhánh. Còn khi một phần đầu đi sâu mà danh sách mở rộng cạn sạch, thì chính phần đầu đó là một tập tối đại mới, miễn là nó chưa bị tập nào bao trùm.

3. Giải mẫu từng bước

Vẫn bảng dữ liệu quen thuộc, ngưỡng phổ biến bằng ba, thứ tự xét là A, D, T, W rồi C.

Bước một — lập danh sách mở rộng cho phần đầu A.

Ta thử ghép A với từng mặt hàng đứng sau. Ghép với D cho phần chung chỉ là giao dịch 4 và 5, độ phổ biến hai, không đạt ngưỡng nên loại. Ghép với T cho độ phổ biến ba, giữ lại. Ghép với W cho độ phổ biến bốn, giữ lại. Ghép với C cho độ phổ biến bốn, giữ lại. Vậy danh sách mở rộng của A gồm ba mặt hàng: T, W và C.

Bước hai — đi sâu theo AT, rồi ATW, rồi ATWC.

Bắt đầu từ AT. Danh sách mở rộng của AT gồm W và C, vì cả ATW lẫn ATC đều còn độ phổ biến ba. Đi tiếp theo ATW, ta thấy còn thêm được C để thành ATWC với độ phổ biến ba. Đến ATWC thì không còn mặt hàng nào để thêm nữa, danh sách mở rộng cạn sạch, nên ATWC chính là một tập tối đại. Viết lại cho gọn theo thứ tự chữ cái, đó là ACTW, độ phổ biến ba.

Bước ba — quay lui và cắt tỉa các nhánh con của A.

Bây giờ xét nốt các nhánh còn lại bắt nguồn từ A. Tập ATC nằm gọn trong ACTW nên bị cắt. Nhánh AW, khi gộp hết phần còn lại sẽ thành ACW, cũng nằm gọn trong ACTW nên bị cắt. Nhánh AC tương tự, là tập con của ACTW nên cũng bị cắt. Như vậy toàn bộ nhánh A đã xong, vì A, T, W, C đều đã nằm trong ACTW.

Bước bốn — nhánh D, rồi DW, rồi DWC.

Danh sách mở rộng của D: ghép với T cho độ phổ biến hai nên loại; ghép với W cho độ phổ biến ba nên giữ; ghép với C cho độ phổ biến bốn nên giữ. Đi sâu theo DW, ta thấy còn thêm được C để thành DWC với độ phổ biến ba; đến đây danh sách mở rộng cạn, nên DWC là một tập tối đại, viết gọn là CDW, độ phổ biến ba. Còn nhánh DC thì nằm gọn trong CDW nên bị cắt.

Bước năm — các nhánh T, W, C đều bị cắt.

Nhánh T, khi gộp hết phần còn lại, cho tập CTW, vốn là con của ACTW nên bị cắt. Nhánh W cho CW, cũng nằm trong ACTW nên bị cắt. Nhánh C chỉ là một mặt hàng, đương nhiên cũng là con của ACTW nên bị cắt. Không còn nhánh nào nữa.
Kết quả: hai tập tối đại

ACTW và CDW, cả hai cùng có độ phổ biến ba. Mọi tập phổ biến khác đều là con của một trong hai tập này.

4. Bài tập tự luyện

Dùng bảng P, ngưỡng phổ biến bằng hai. Năm giao dịch: giao dịch một có B, C, M; giao dịch hai có B, E; giao dịch ba có B, C, E, M; giao dịch bốn có C, E, O; giao dịch năm có B, C, E, M. Sau khi loại O, thứ tự xét là M, B, C, E.

Bài một. Danh sách mở rộng của phần đầu B gồm những gì?

B có mặt ở các giao dịch 1, 2, 3, 5. Ghép B với C cho phần chung là 1, 3, 5, độ phổ biến ba, giữ lại. Ghép B với E cho phần chung là 2, 3, 5, độ phổ biến ba, giữ lại. Vì B đứng sau M trong thứ tự, ta không ghép ngược lại với M ở nhánh này. Vậy danh sách mở rộng của B gồm C và E.

Bài hai. Hãy tìm mọi tập tối đại của bảng P.

Bắt đầu từ M. Danh sách mở rộng của M gồm B, C và E (ghép M với B được độ phổ biến ba, với C được ba, với E được hai). Đi sâu theo MB, danh sách mở rộng của nó gồm C và E; tiếp tục theo MBC rồi thêm E, ta được MBCE với độ phổ biến hai, và danh sách mở rộng cạn sạch. Vậy ta có một tập tối đại, viết gọn là BCEM, độ phổ biến hai. Mọi nhánh còn lại, như B, C, hay E, đều nằm gọn trong BCEM nên đều bị cắt. Kết luận: chỉ có một tập tối đại duy nhất là BCEM.