Quy hoạch động Bitmask

I. Khái niệm về "trạng thái" trong Quy hoạch động.

Để hiểu về bản chất của quy hoạch động, ta bắt buộc phải hiểu được trạng thái là gì.

Ví dụ cho một bài toán phổ biến như sau:

Một chú ếch xuất phát từ vị trí ~0~ trên trục ~OX~, khi đang ở vị trí ~i~ mỗi bước chú có thể nhảy tới vị trí ~i+1~, ~i+2~, ~i+3~. Hỏi có bao nhiêu cách để chú nhảy tới vị trí ~n~.

Dễ thấy trạng thái của bài toán này có thể đặt là:

• ~f(i)~ là số cách để nhảy xuất phát từ vị trí ~0~ tới vị trí ~i~.
• ~f(0)~ = 1 là trạng thái gốc.
• Công thức có thể tính dựa vào các trạng thái con: ~f(i) = f(i-1) + f(i-2) + f(i-3)~.

Hay, một ví dụ khó hơn là bài toán Knapsack:

Một đêm nọ, một tên trộm nọ quyết định đột nhập vào một siêu thị nọ. Siêu thị có ~N~ đồ vật, vật thứ ~i~ có trọng lượng ~A_i~, giá trị ~B_i~. Tên trộm mang theo một cái túi chứa được trọng lượng tối đa ~W~. Hỏi tổng giá trị tối đa tên trộm có thể lấy được là bao nhiêu?

Ta có thể đặt trạng thái như sau:

• ~f(i,j)~ là xét tới đồ dùng thứ ~i~, ta đang mang số đồ vật có tổng trọng lượng là ~j~ thì sẽ có tổng giá trị tối đa là bao nhiêu.
• Đặt ~f(0,0) = 0~, các trường hợp còn lại là âm vô cùng.
• Ta có công thức truy hồi: ~f(i,j) = max(f(i-1,j),f(i - 1,j-a[i]) + b[i])~, dựa vào hai trường hợp lấy hoặc không lấy đồ dùng ~i~.

Như vậy, trạng thái trong quy hoạch động chính xác là cách ta định nghĩa về bài toán cần giải và lập một hàm để tính toán đáp án dựa trên công thức định sẵn. Việc xác định được trạng thái của bài toán chính là chìa khóa để giải được các bài toán quy hoạch động.

Ở trên là một số cách đặt trạng thái phổ biến, nhưng trong bài này, ta sẽ học về một kiểu trạng thái khác, mang tính trừu tượng hơn.

II. Trạng thái bitmask

1. Bài toán ví dụ

Có ~n~ người tham gia xếp hàng. Nếu người thứ ~i~ đứng ở vị trí ~j~ sẽ có độ thẩm mĩ là ~A_{i,j}~. Tìm cách xếp hàng để có tổng độ thẩm mỹ cao nhất.

Ví dụ ~n=3~ và ta có bảng ~A(i,j)~ như sau:

4 2 3
5 2 4
6 7 2

Kết quả tối ưu sẽ là ~15~, bởi ta xếp theo thứ tự ~1,3,2~.

2. Phân tích bài toán

a) Tiếp cận với khái niệm tập

Ở đây, rõ ràng ta không thể đặt trạng thái là ~f(i)~ là xét tới người thứ ~i~ thì tổng độ thẩm mĩ lớn nhất là bao nhiêu được. Bởi để xếp người ~i~ vào hàng, ta cần biết người đó đứng thứ mấy trong hàng, đồng thời việc thứ tự xếp hàng của ~n~ người không quan trọng cũng khiến việc đặt trạng thái theo kiểu "truyền thống" như trên không thực hiện được.

Để tiếp cận bài toán này, ta cần xác định được những thông tin bắt buộc phải có trong trạng thái quy hoạch động:

• Đầu tiên là do thứ tự ta xếp không quan trọng, nên ta cần biết được những người nào đã được xếp vào hàng rồi để không bị xếp thừa.
• Thứ hai là số lượng những người đang đứng trong hàng, để nếu ta xếp thêm người sẽ biết người đó đứng ở vị trí bao nhiêu để cộng vào giá trị ~A_{i,j}~ tương ứng.

Để thỏa mãn đủ số thông tin trên, ta có thể đặt một trạng thái là ~f(S)~, tức là xét tập người ~S~, thì tổng độ thẩm mỹ là bao nhiêu. Ở đây ~S~ là một tập hợp, có thể tượng tượng như một Vector, giả sử tập gồm người ~1,4,5~ thì ~S = \{1,4,5\}~. Như vậy ta có thể biết thêm cả thông tin số lượng người đang đứng trong hàng, tương đương độ lớn của ~S~, hay ~|S|~.

Đầu tiên ta có ~f(S') = 0~, với ~S' = \varnothing~. Để tiện lợi hơn trong việc suy nghĩ, ta sẽ xây dựng công thức dựa trên phương pháp DP Bottom Up, tức là từ một trạng thái ta sẽ đẩy nó cho lên các trạng thái mới.

Với một tập người ~S~, ta có hàm ~f(S)~ để tối ưu tính thẩm mỹ nếu chỉ xếp tập người này vào hàng. Để cập nhật lên các trạng thái lớn hơn, ta thử thêm người ~i~ vào hàng (lưu ý cần đảm bảo người ~i~ không có trong tập ~S~), như vậy người này sẽ đứng ở vị trí ~|S| + 1~, và trạng thái mới sẽ là ~S \cup i~. Vậy ta có:

• ~f(S \cup i) = max(f(S \cup i), f(S) + A_{i,|S|+1})~.
• Ở đây ~\cup~ là kí hiệu tập giao.

Vậy kết quả của bài toán sẽ là ~f(S'')~ với ~S'' = \{1,2,3,...,n\}~.

b) Chuyển về dạng bitmask

Đối với cách làm trên, ta thấy vấn đề lớn nhất gặp phải là khái niệm tập ~S~, khi nó giống một Vector, và như ta đã biết thì để lưu được mảng trạng thái quy hoạch động, các trạng thái cần được lưu dưới dạng các số nguyên không âm.

Vậy công việc bây giờ ta cần làm là đưa một tập về biểu diễn dưới dạng số.

Xét một tập ~S~ bất kì, ta có nhận xét rằng ngoài tập rỗng, thì nó sẽ bao gồm các số trong tập ~\{1,2,3,...,n\}~, mỗi số chỉ xuất hiện một lần. Vậy tương đương với việc, ta có thể chuyển tập ~S~ về một dãy ~a~ gồm ~n~ phần tử được đánh số từ ~0~ tới ~n-1~, với ~a_{i-1} = 0/1~, tương đương với người thứ ~i~ có xuất hiện trong tập hay không.

Giả sử với ~n = 5~, tập ~S = \{3,5\}~ sẽ được biểu diễn bằng mảng ~a = [0,0,1,0,1]~. Nếu ta đưa được mảng ~a~ này về số thì tương đương với việc đưa được mảng ~S~ về dạng số. Và bởi, dãy ~a~ chỉ gồm các phần tử mang hai giá trị ~0~ hoặc ~1~, nên ta dễ dàng liên tưởng tới việc dãy ~a~ tương đương một dãy nhị phân.

Và như chúng ta đã biết, có thể dễ dàng chuyển một dãy nhị phân về một số dưới dạng thập phân như sau:

• ~a = [0,0,1,0,1]~ tương đương giá trị nhị phân ~a_2 = 10100~, hay giá trị thập phân ~a_{10} = 20~.

Với ~n \le 20~, dễ thấy giá trị tối đa dùng để biểu diễn một tập là ~2^{20} - 1 = 1048575~, tức là chỉ lớn hơn ~10^6~ một chút, do vậy ta hoàn toàn có thể lưu trữ bằng mảng.

Đây được gọi là ~bitmask~, hay đưa một tập về dạng một số nguyên hệ thập phân, nhưng máy tính của ta luôn nhìn các số dưới dạng nhị phân nên rất tiện lợi.

Bây giờ ta cần định nghĩa một số thao tác có thể làm trên tập ~bitmask~ này:

• Bước đầu tiên ta cần biết các toán tử bitwise do từ giờ ta sẽ cần làm việc trên tập nhị phân. Các bạn hãy tham khảo một số phép toán chính như ~and~, ~or~, ~xor~ tại đây.
• Để kiểm tra xem người thứ ~i~ có nằm trong tập ~S~ hay không (~S~ từ giờ ta xét sẽ là một số nguyên không âm biểu diễn cho tập ~S~ gốc), ta có thể dùng toán tử ~and~. Bởi người thứ ~i~ được biểu diễn bằng ~bit~ thứ ~i-1~, vậy nên ta chỉ cần kiểm tra xem ~\text{bit}~ đó có xuất hiện trong ~S~ hay không.
• Để lấy số người trong tập, hay ~|S|~, ta cần đếm số ~bit~ bật trong ~S~. Trong C++, ta có một hàm tiện ích khá hữu dụng để làm việc này trong độ phức tạp ~O(1)~, là cntOnBit = __builtin_popcount(S).

Như vậy, ta có thể biểu diễn tập ~S~ cũng như các phép toán của nó dưới dạng số một số thập phân thông qua các phép toán trên hệ nhị phân của nó.

Đây được gọi là phương pháp DP Bitmask.

Dưới đây là đoạn code mẫu với độ phức tạp ~O(2^n \times n)~:

// giá trị trạng thái tối đa
int Max = (1 << n);
// khởi tạo các trạng thái là âm vô cùng và đặt f(0) = 0 làm trạng thái gốc
for (int mask=0; mask<Max; mask++) f[mask] = -inf;
f[0] = 0;
// duyệt qua từng mask để thực hiện quy hoạch động
for (int mask=0; mask<Max; mask++) {
    // tính số bit bật của mask
    int cntOnBit = __builtin_popcount(mask);
    for (int i=0; i<n; i++) { // xét từng người để thêm vào tập
        // kiểm tra để đảm bảo người i không nằm trong tập mask
        if ((mask >> i & 1) == 0) { 
            // cập nhật giá trị của tập mới
            int newMask = mask | (1 << i); // (1 << i) tương đương (2^i)
            f[newMask] = max(f[newMask],f[mask] + f[i][cntOnBit+1]);
        }
    }
}
// kết quả khi ta đã xếp đủ n người là f(Max-1), khi mọi bit từ 0 tới n-1 đều bật
cout << f[Max-1];

3) Một số lưu ý nhỏ

Đầu tiên là dấu hiệu nhận biết khi nào nên nghĩ tới Quy Hoạch Động Bitmask, đó là lúc ta cần lập hàm quy hoạch động, nhưng các trạng thái thông thường không thể lưu đủ thông tin, hay ta cần làm việc với các tập. Một dấu hiệu rõ ràng hơn đó là giá trị của ~n~, thường đường giới hạn bởi ~n \le 20~.

Khi xác định được việc phải dùng ~bitmask~, ta nên đánh ~index~ của các phần tử trong tập theo zero-index, hay từ ~0~ tới ~n-1~ để tiện lợi hơn. Khi đó phần tử ~i~ sẽ ứng luôn với ~bit~ thứ ~i~.

III. Một số bài tập khác

1) Đếm hành trình

Có ~n~ ~(1 \le n \le 20)~ thành phố được đánh số từ ~1~ tới ~n~. Có ~m~ ~(m \le n^2)~ chuyến bay giữa các thành phố. Nhiệm vụ của bạn là đếm số hành trình khác nhau để bay xuất phát từ thành phố ~1~ và kết thúc ở thành phố ~n~, sao cho có thể đi hết tất cả ~n~ thành phố, với mỗi thành phố chỉ được tới đúng một lần.

Đầu tiên ta định nghĩa ~p(u,v) = 0/1~ để xác định từ thành phố ~u~ có chuyến bay tới thành phố ~v~ hay không.

Ta cần phân tích một chút để đặt được trạng thái của bài toán:

• Đầu tiên ta thấy ngoài việc cần xuất phát từ thành phố ~1~ và kết thúc ở thành phố ~n~, thì thứ tự bay của các thành phố khác đều không quan trọng. Và, do mỗi thành phố cần được thăm đúng ~1~ lần, vậy nên ta có thể nghĩ tới việc lưu các thành phố đã thăm dưới dạng ~bitmask~.
• Vấn đề thứ ~2~ là việc chuyển trạng thái. Nếu ta chỉ lưu ~f(mask)~ là số chuyến bay để đi hết và thăm đúng một lần các thành phố trong tập ~mask~, rõ ràng ta không thể chuyển được trạng thái, bởi ta không biết mình đang dừng ở đâu để đi tiếp.
• Bởi vậy, ta cần thêm chiều "đang dừng ở thành phố nào": ~f(mask,i)~ là đã thăm hết đúng ~1~ lần các thành phố trong tập ~mask~ và hiện tại đang dừng ở thành phố ~i~.
• Và bởi ta đã xác định được trạng thái cần dùng ~bitmask~, để tiện lợi ta sẽ đánh luôn ~index~ của các thành phố từ ~0~ tới ~n-1~.

Lúc này, việc chuyển trạng thái khá đơn giản:

• Từ trạng thái ~f(mask,i)~, ta có thể di chuyển tiếp sang thành phố thứ ~j~, nếu ~p(i,j) = 1~ và ~j~ không tồn tại trong ~mask~: cpp newMask = mask | (1 << j) f(newMask,j) += f(mask,i)) Độ phức tạp của thuật toán này nếu tính toán qua sẽ là ~O(2^n \times n^2)~, thoạt nghe rất lớn bởi ~n = 20~, nhưng nên nhớ rằng có rất nhiều trạng thái "thừa", ví dụ ~f(mask,i)~ nhưng ~i \notin mask~.

int Max = (1 << n);
// khởi tạo mọi trạng thái bằng 0
memset(f,0,sizeof(f));
// trạng thái gốc xuất phát ở đỉnh 1 và mới chỉ thăm được đúng đỉnh 1 (lưu ý là ta đang dùng zero-index nên thành phố 1 sẽ ứng với index 0)
f[1][0] = 1;
for (int mask=0; mask<Max; mask++) {
    for (int i=0; i<n; i++) {
        // nếu i không nằm trong tập mask hoặc giá trị f[mask][i] = 0 thì ta không cần duyệt thêm
        if ((mask >> i & 1) == 0 || f[mask][i] == 0) continue;
        // duyệt thành phố j sắp tới
        for (int j=0; j<n; j++) {
            // nếu từ i tới j không có chuyến bay hoặc j đã nằm sẵn trong tập i thì bỏ qua
            if (p[i][j] == 0 || (mask >> j & 1) == 1) continue;
            // cập nhật giá trị cho trạng thái mới
            int newMask = mask | (1 << j);
            f[newMask][j] += f[mask][i];
        }
    }
}
// kết quả là trạng thái mà ta thăm tất cả các thành phố và dừng lại ở thành phố n-1, hay là thành phố n trong bài toán gốc.
cout << f[Max-1][n-1];

2) Ghép cặp

Có ~n~ người đàn ông và ~n~ ~(1 \le n \le 20)~ người phụ nữ đều được đánh số từ ~1~ tới ~n~. Độ hợp nhau của người đàn ông thứ ~i~ và người phụ nữ thứ ~j~ là ~a_{i,j}~, nếu giá trị ~a_{i,j} = 0~ thì hai người này không hợp nhau, còn ngược lại giá trị này bằng ~1~. Hãy tìm cách chia ~n~ người đàn ông và ~n~ người phụ nữ này thành ~n~ cặp sao cho mỗi cặp gồm một người đàn ông và một người phụ nữ hợp nhau.

Dễ thấy rằng, ta chỉ cần ghép cặp dần cho từng người đàn ông từ ~1~ tới ~n~, nhưng cần phải kiểm soát thêm cả việc có bao nhiêu người phụ nữ đã được ghép cặp để tránh bị trùng. Để kiểm soát được cả hai thông tin này, ta chỉ cần dùng một tập ~S~ duy nhất, gọi ~f(S)~ là số cách để ghép cặp cho ~|S|~ người đàn ông đầu tiên với các người phụ nữ trong tập ~S~.

Chuyển trạng thái như sau:

• Từ trạng thái ~f(S)~, ta có thể đẩy trạng thái bằng cách ghép cặp cho người đàn ông thứ ~|S|+1~ cho người phụ nữ nào đó không nằm trong tập ~S~ và hợp nhau với người đàn ông đó.

Độ phức tạp: ~O(2^n \times n)~.

Phần code xin nhường lại như một bài tập cho bạn đ