BITMASKS

Mình chắc chắn ai từng lập trình đều đã dùng kĩ thuật này, nhưng mọi người có thể gọi bằng những tên gọi khác nhau hoặc chẳng thèm gọi tên là gì. Ta bắt đầu làm rõ kĩ thuật này.

Chẳng hạn ta có 3 bóng đèn. Mỗi bóng đèn có 2 trạng thái là bật hay tắt. Để biểu diễn trạng thái của 3 bóng đèn, ta có thể dùng một dãy có 3 phần tử để biểu diễn, ví dụ bool a[3]. Nếu số bóng đèn ít, ta có thể dùng một cách khác để biểu diễn: ta dùng duy nhất một số nguyên để biểu diễn chúng. Giả sử hai bóng đầu bật và bóng cuối tắt, ta có thể biểu diễn 110(cơ số 2) = 6(cơ số 10). Như vậy với một số 6 ta có thể biết được trạng thái hiện tại của ba bóng đèn, tương tự 7 = 1112 biểu diễn cả 3 bóng đều bật.

Bitmask: Để biểu diễn trạng thái cho nhiều đối tượng, ta phải dùng nhiều biến để lưu lại trạng thái của chúng. Thay vào đó ta dùng duy nhất một biến để biểu trạng thái cho tất cả. Chắc chắn là bạn đã dùng kĩ thuật này rồi? Khi làm web, người ta cũng hay dùng cách này để biểu diễn role của user.

Ta sẽ đi qua từng ví dụ để rõ hơn về nó. 

1.   Dùng bitmask để duyệt “trâu bò“

Bắt đầu bằng một ví dụ:

Một đầu bếp đang chuẩn bị một bữa ăn với N nguyên liệu (N < 20). Vị đầu bếp muốn bữa ăn phải có đầy đủ K chất (K < 20) C1, C2, …, Ck. Để vấn đề dễ hiểu, ta chưa quan tâm đến lượng của các chất trong bữa ăn. Với mỗi nguyên liệu ta biết được nó có chứa chất nào trong thành phần của nó. Đầu bếp muốn biết tất cả các tập nguyên liệu mà tập đó chứa đầy đủ K chất.

Dữ liệu:

Dòng 1: N và K

N dòng tiếp theo: mỗi dòng chứa K số thể hiện thành phần của mỗi nguyên liệu, số thứ i thể hiện nó có chứa chất Ci hay ko, là 1 nếu nó chứa chất Ci,  0 ngược lại.

Chẳng hạn:

6 7

1 0 0 1 0 1 0

0 1 0 0 1 0 0

1 0 0 0 0 0 1

0 0 1 1 0 0 0

1 1 0 0 0 0 0

0 0 0 0 0 1 0

Đầu bếp có 6 nguyên liệu, và ông ta quan tâm bữa ăn phải chứa đủ 7 chất. Nguyên liệu thứ nhất chỉ chứa chất C1, C4, C6

Giải quyết:

Với mỗi nguyên liệu, nó sẽ có trạng thái là được chọn hoặc không được chọn. Mỗi nguyên liệu có 2 trạng thái, vậy sẽ có tất cả 2^N trạng thái cho N nguyên liệu. Với những trường hợp N nhỏ  thì duyệt qua tất cả các trạng thái là chuyện dễ dàng (2^20 ~ 10^6). Cách duyệt qua tất cả các phương án để tìm lời giải gọi là duyệt trâu bò. Vấn đề là thể hiện cách duyệt qua tất cả trạng thái bằng ngôn ngữ lập trình. Bạn có thể dùng đệ qui để giải quyết, nó vẫn ok. Tuy nhiên, mình muốn trình bày bằng bitmask, code ngắn, dễ sử dụng lại.

Do có 2^N trạng thái, tất cả trạng thái là 0000002=0, 0000012=1, 0000102=2, …, 1111112=2^N-1. Tất cả trạng thái là các số nguên chạy từ 0 đến 2^N-1. Nên chỉ với một vòng lặp for(state=0; state < 2^N; state++) đã biểu diễn được việc “duyệt qua tất cả trạng thái“

Với mỗi giá trị của state, ta muốn biết nguyên liệu thứ i có được chọn hay ko, ta chỉ cần xét biểu thức (state and 2^i), i tính từ 0 đến K-1. Nếu biểu thức này lớn hơn 0 nghĩa là nguyên liệu thứ i được chọn trong trạng thái state, ngược lại thì 0. and ở đây là phép and bit.(Bạn tự kiểm chứng biểu thức này).

Một điểm chú ý nữa, Với mỗi nguyên liệu thứ i ta cũng chuyển thành một số b[i] để diễn tả thành phần của nó. Ví dụ với nguyên liệu thứ nhất, ta sẽ biểu diễn b[0] = 10010102=74.

Như vậy nếu các nguyên liệu được chọn có các giá trị b[i] or với nhau hợp thành 11111112=(2^K-1) thì tập đó thỏa mãn. or ở đây là phép or bit

Code:

For(state=0; state < 2^N; state++){

            Sumarize = 0;

            For(i=0; i < N; i++) if((state and 2^i) > 0){

                     Sumarize = Sumarize or b[i];

            }

            If(Sumarize == (2^K-1)){

                    //Print the result

            }

}

Độ phức tạp của đoạn code trên là O(2^N*K), với N=K=20 thì chạy trong 1s là ok.

Nhìn code rất dễ hiểu phải không? Bạn có thể xem code bằng C++ tại https://www.dropbox.com/s/u387lban20nk3l7/cheif.cpp

2.     Bitmask để biểu diễn trạng thái.

Từ đầu bài viết tới giờ, chúng ta chỉ biểu diễn không hoặc có. Thực tế kĩ thuật này được hiểu xa hơn một tí, ta xét ví dụ khá quen thuộc sau:

Ta có ba chai nước có thể tích là V1, V2, V3 (Vi < 10)  (đơn vị thể tích). Ban đầu ta có chai nước thứ nhất đầy nước và hai chai còn lại không chứa gì cả. Bạn cần tìm cách rót sao cho bình V3 chứa K (K<=V3) thể tích nước và số lần rót là ít nhất. Bạn được thực hiện một trong các cách sau:

1. Rót hết nước từ chai này sang chai khác (được phép tràn)
2. Rót nước từ chai này sang chai khác cho đến lúc chai khác được nhận đầy nước.
3. Rót bỏ hết nước từ một chai.

Với mỗi trạng thái (x1, x2, x3) thì ta cũng có thể dùng dãy 3 phần tử để diễn tả chúng. Tuy nhiên ta cũng có thể diễn tả trạng thái của ba chai bằng một số nguyên X= (x1*(V2+1)+x2)*(V3+1)+x3. Bạn có thắc mắc tại sao nhân với V2+1 và V3+1. Thật ra nhân với số lớn hơn 2 số này vẫn thỏa, hai số này là hai số nhỏ nhất có thể nhân vào, dựa vào tính chất của phép mod. Với cách diễn đạt này, thì đảm bảo với mỗi bộ số (x1, x2, x3) khác nhau thì X cũng khác nhau (bạn tự kiểm tra bằng phản chứng). Với mỗi số nguyên X biểu diễn cho một thái, ta có thể biết được lượng nước trong mỗi chai

-       x1 = X / ((V2+1)(V3+1))

-       x2 = (X/(V3+1)) mod (V2 +1)

-       x3 = X mod (V3+1)

Tổng cộng ta có (V1+1)*(V2+1)*(V3+1) trạng thái, ta cũng biết được quy tắc chuyển từ trạng thái này sang trạng thái khác thông qua các cách rót nước. Ta xây dựng một đồ thị có (V1+1)*(V2+1)*(V3+1) đỉnh, xây dựng các cạnh nối bằng các quy tắc của đề bài. Trạng thái bắt đầu là (V1, 0 ,0), số nguyên biểu diễn là V1*(V2+1)*(V3+1). Trạng thái kết thúc là (0, 0, K), số nguyên biểu diễn là K.

Có đồ thị, việc tìm đường đi ngắn nhất từ đỉnh này đến đỉnh khác là dễ dàng thông qua các giải thuật có sẵn. Với bài này ta có thể dùng breadth first search hoặc dijkstra. Ở đây ta không chú tâm đến việc giải bài này, ta chỉ tìm hiểu cách tiếp cận biểu diễn trạng thái bằng một số nguyên. Bạn có thể xem lời giải bằng C++ tại https://www.dropbox.com/s/3sl45k6hskgtypm/ThreeBottles.cpp.

3.     Bitmask và quy hoạch động (copy từ Giang Vi)

Bài toán tìm đường đi Hamilton là một bài toán khá quen thuộc: cho N đỉnh, tìm đường đi sao cho mỗi đỉnh được thăm duy nhất một lần, và chi phí thăm N đỉnh là thấp nhất.

Với bài toán này, thông thường nếu N nhỏ (N <=10), ta có thể giải quyết bài toán bằng phương pháp nhánh cận. Tuỳ vào cách đặt cận mà tốc độ chương trình có thể được nâng lên, tuy nhiên thời gian chạy chương trình vẫn có thể không đảm bảo với một số test khó.

Không những vậy, nếu giới hạn N tăng lên đến 20, thì việc sử dụng phương pháp nhánh cận để giải quyết sẽ không còn khả thi nữa. Trong trường hợp này, ta có cách tiếp cận khác để giải quyết bài toán một cách hiệu quả hơn, với độ phức tạp O(N^2*2^N). Đó chính là sử dụng quy hoạch động và bitmask (cách thường gọi là quy hoạch động trạng thái).

Ý tưởng

Để giải quyết bài toán này theo phương pháp quy hoạch động, các buớc thiết lập lời giải phải được lưu trữ để có thể tính toán từ các bài toán con. Rõ ràng ở đây, chúng ta phải lưu các đỉnh đã đi qua và đỉnh cuối cùng của một hành trình bất kỳ. Để làm việc này, ta dùng một mảng nhị phân N phần tử với ý nghĩa bit 1 tượng trưng cho các đỉnh đã được thăm và ngược lại. Từ đó, ta định nghĩa Fx [i,j] là chi phí tối ưu trong trạng thái i, j là đỉnh kết thúc hành trình (0 <= i <= 2^N -1; 1 <= j <= N).

Ví dụ:

Dãy [010011]2 tương đương trạng thái có 3 đỉnh được đi, và đỉnh kết thúc hành trình là đỉnh 5 (tính từ phải qua, bạn có thể lưu từ phải qua, vấn đề này không ảnh hưởng gì), với biểu diễn trong hệ thập phân tương ứng của dãy này là 19. Vậy hàm quy hoạch động của trạng thái này là Fx[19,5]

Chi tiết thuật toán

Với mỗi trạng thái I có j là đỉnh đến cuối cùng trong trạng thái này, xét mọi đỉnh k khác j mà k chưa được thăm trong trạng thái I. Gọi trạng thái mà hành trình của nó có chứa đỉnh k là X.

Ví dụ:

I = [010011] có các đỉnh 1,2,5 đã thăm. Giả sử k = 3 (thoả vì chưa đến được thành phố 3 trong trạng thái I), ta được trạng thái X = [010111].

Tóm lại, ở bước này: trạng thái X và trạng thái I chỉ khác nhau duy nhất ở đỉnh k. Dễ nhận thấy số thành phố đi được thấy đi được ở trạng thái X = số thành phố đi được ở trạng thái I + 1, suy ra việc tính toán Fx[X,k] sẽ dựa vào kết quả bài toán có kích thước nhỏ hơn nó là Fx[I,j]

Tiếp theo, ta sẽ tối ưu Fx[X,k] theo công thức : Fx[X,k] = Min (Fx[X,k], Fx[I,j] + C[j,k]);

Công thức trên sẽ lấy chi phí nhỏ hơn giữa trạng thái hiện tại (hành trình kết thúc tại k) và trạng thái hành trình kết thúc tại j cộng với chi phí di chuyển từ j -> k.

Bước tìm đường đi có chi phí ngắn nhất chính là giá trị nhỏ nhất trong tất cả đường đi qua N đỉnh mà đường đi đó kết thúc tại thành phố i. Từ đó ta có kết quả bài toán là Min (Fx [2^N - 1, i]) với i =1..N.

Số 2^N-1 thể hiện trạng thái mà N đỉnh đã được thăm. Ví dụ: 2^6 - 1 = 6310 = 1111112

Như đã đề cập ở trên, độ phức tạp cở khoảng 2^N*(N^2), dù sao cũng nhỏ hơn N!

Bạn có thể xem code viết bằng C++ tại https://www.dropbox.com/s/f1u4af4dpxghu72/Hamilton.cpp

Người viết: Dương Thành Phong