Bitmask – Quy hoạch động với bitmask

Tư tưởng:

Các trạng thái trong QHĐ bitmask được làm rõ và thể hiện qua các bit 0/1, thể hiện được sự phụ định/khẳng định của 1 đặc tính của bài toán.

Ví dụ:

Như ví dụ về 1 trạng thái ở trên thì mỗi bit biểu thị cho 1 sự phụ định/khẳng định cho 6 cái chủ thể có đặc tính ở trên. Ví dụ chủ thể con người và đặc tính là có khả năng bay. Thì người thứ 0, 4 và 5 có thể bay còn những người còn lại thì không.

Làm quen với bitmask:

Các trạng thái sẽ ở dưới dạng các số thập phân, nhưng các thao tác để nhận biết trên trạng thái là các thao tác với bit.
- Ví dụ: có trạng thái là 5 thì tự hiểu nó là dạng nhị phân là 101.
- Muốn biết bit thứ 0 có là 1 hay không thì chúng ta sẽ sử dụng các thao tác với bit để kiểm tra ⇒ thao tác sẽ nhanh gọn hơn

Vì thao tác tất cả đều dưới dạng bit nhưng trạng thái lại ở dạng thập phân nên các bài toán có số chủ thể = n ≤ 20 thì mới phù hợp với thuật toán này. Vì khi đó số trạng thái lớn nhất của bài toán là 2^20, nghĩa là số nhị phân có 20 bit 1 = 11….11

Quy hoạch động bitmask:

Như chúng ta đã biết, quy hoạch động là quá trình tổng hợp kết hợp kết quả lần lượt, kết quả sau dựa trên kết quả trước.
Quy hoạch động bitmask cũng dựa trên nguyên lý của quy hoạch động thông thường, chỉ khác sự dịch chuyển các trạng thái là sự dịch chuyển các bitmask.

Một số thao tác Bit cần dùng trong bài toán quy hoạch động bitmask:

I. Đếm số bit 1 của trạng thái hiện tại:

Mình sẽ sử dụng hàm __builtin_popcount(x);

Ý nghĩa: Với bitmask hiện tại miêu tả số người biết bay thì hàm này cho ta biết hiện tại có bao nhiêu người biết bay, thì bây giờ, mình muốn dạy thêm 1 người biết bay thì mình sẽ biết được người này là người biết bay thứ mấy.

II. Kiểm tra bit thứ i là bit gì?

III. Duyệt các bit 1 có trên bitmask hiện tại:

Sử dụng 2 hàm:

__builtin_ctz: tính số số 0 ở cuối
__builtin_ffs: tính số thứ tự của bit 1 đầu tiên

Cách sử dụng 2 hàm này có ý nghĩa tương đương nhau

Dưới đây là là một bài toán sử dụng phương pháp quy hoạch động bitmask để xử lý.

Đề bài:

Một thị trấn có n xã khác nhau và giữa mỗi xã đều có một con đường dẫn tới nhau, để đi lại thì mất a_ij chi phí. Ông chủ tịch thị trấn mới nhậm chức, muốn đến từng xã để chào hỏi bà con. Khổ nỗi ông muốn tiết kiệm chi phí nhất có thể để còn dành tiền đi nhậu nên ông có bảo thư ký mình lập ra lịch trình để đi hết các xã để có thể tiết kiệm chi phí nhất. Hãy giúp anh thư ký có một cái Tết ấm nha.
Đầu vào:
– Dòng đầu tiên là một số nguyên n (n <= 20) là số xã trong huyện đó.
– n dòng tiếp theo, mỗi dòng chứa n số: số thứ j của dòng thứ i sẽ là chi phí để đi một chiều từ xã i đến xã j. Chi phí này sẽ bằng 0 nếu i = j.
Đầu ra: một số nguyên duy nhất là chi phí nhỏ nhất mà thư ký tính toán được.

Solution:

dp[mask][i]: chi phí ít nhất để chủ tịch thị trấn đi hết các xã ở trong trạng thái mask mà xã cuối cùng trong mask là i.
mask sẽ nằm trong khoảng từ 1 đến 2ⁿ – 1 (big_mask), mỗi bit 1 trong mask tương ứng với trạng thái đã đi qua của 1 xã trong đó theo thứ tự.
Cách cập nhật giá trị của mảng dp: lật lần lượt các bit 0 ở trong mask để update kết quả.

Implementation:

Khởi tạo:
- big_mask là trạng thái lớn nhất có thể xảy ra (trạng thái “full 1”)
- mảng dp mang giá trị max vì cần cập nhật mảng dp theo min
- dp[1<<i][i] = 0 với mỗi i => biểu thị trạng thái xuất phát tại i
Cập nhật:
- Với mỗi trạng thái mask bao gồm các bit 1 biểu thị các thị xã đã đi qua, các bit 0 biểu thị các thị xã cần đến tiếp theo.
- dp[mask][i] là chi phí ít nhất để đi hết các thị xã được biểu thị qua số bit 1 trong mask và đang dừng lại ở thị xã thứ i
- cách cập nhật thì mình sẽ chọn thị xã j trong số các thị xã chưa được đến qua tập các bit 0 trong mask:
  - cost = chi phí từ thị xã i đến thị xã j
  - nmask (trạng thái sau khi thêm thị xã j vào hành trình) = mask || 1 << j
  - dp[nmask][j] = max(dp[nmask][j], dp[mask][i] + cost)
Kết quả cuối cùng là giá trị lớn nhất của các dp[big_mask][i] (chi phí thấp nhất khi hoàn thành hành trình đi hết n thị xã và kết thúc tại thị xã i)