Cấu trúc dữ liệu và Giải thuật Bài 104: Quy hoạch động trạng thái (Bitmask DP) - Giải quyết bài toán tập hợp và tối ưu hóa tổ hợp.

Trong hành trình giải quyết các bài toán tối ưu hóa, một trong những thách thức khó nhằn nhất là Bài toán tập hợp (Subset Selection Problems).

Ví dụ kinh điển: Bạn cần giao $N$ công việc cho $N$ người sao cho tổng chi phí là nhỏ nhất, hoặc bài toán Người giao hàng (Traveling Salesperson Problem - TSP) tìm đường đi ngắn nhất ghé thăm qua tất cả các thành phố đúng một lần.

Nếu số lượng phần tử $N$ lớn (ví dụ $N = 100$), việc thử tất cả các hoán vị (brute-force) sẽ có độ phức tạp $O(N!)$, vượt quá giới hạn tính toán của vũ trụ. Tuy nhiên, nếu $N$ nhỏ (thường trong khoảng $15 \le N \le 20$), ta có thể sử dụng một kỹ thuật cực kỳ tinh tế gọi là Quy hoạch động trạng thái (Bitmask DP) để ép độ phức tạp xuống còn $O(N^2 2^N)$ hoặc $O(N 2^N)$, biến một bài toán không thể giải thành khả thi trong chớp mắt.

1. Bản chất của Bitmask (Mặt nạ bit)

Thay vì dùng một mảng boolean phức tạp hoặc cấu trúc dữ liệu nặng nề để đánh dấu các phần tử đã được chọn hay chưa trong một tập hợp, Bitmask sử dụng một số nguyên duy nhất (int hoặc long long), trong đó mỗi bit đại diện cho trạng thái của một phần tử:

• Bit thứ $i$ có giá trị 1: Phần tử thứ $i$ đã được chọn / đã ghé thăm.

• Bit thứ $i$ có giá trị 0: Phần tử thứ $i$ chưa được chọn / chưa ghé thăm.

Ví dụ với tập hợp 4 phần tử ($N = 4$), số nguyên 5 trong hệ nhị phân là 0101. Điều này biểu thị rằng phần tử số 0 và số 2 đã được chọn, còn phần tử số 1 và số 3 chưa được chọn.

Các phép toán bitwise cốt lõi trong Bitmask DP:

1. Kiểm tra xem phần tử $i$ đã được bật hay chưa:

   if (mask & (1 << i)) != 0

2. Bật phần tử $i$ lên (Đánh dấu là đã chọn):

   newMask = mask | (1 << i)

3. Tắt phần tử $i$ đi (Bỏ chọn):

   newMask = mask & ~(1 << i)

2. Xây dựng trạng thái và chuyển đổi trong Bitmask DP

Hàm quy hoạch động thường có dạng:

$$\text{dp}[\text{mask}][\text{u}]$$

Trong đó:

• $\text{mask}$: Trạng thái tập hợp các phần tử đã đi qua.

• $u$: Phần tử hiện tại (hoặc đỉnh đồ thị hiện tại) mà ta đang đứng.

Quá trình chuyển trạng thái (Transition) thực hiện bằng cách duyệt qua các phần tử chưa được chọn trong $\text{mask}$, sau đó "bật" bit tương ứng lên và cộng dồn chi phí.

4. Hiện thực hóa bài toán Người giao hàng (TSP) bằng Golang

Dưới đây là đoạn code Golang giải quyết bài toán Traveling Salesperson Problem (TSP) kinh điển bằng phương pháp Bitmask DP:

Go

package main

import (
	"fmt"
	"math"
)

// Ma trận trọng số khoảng cách giữa các thành phố
var dist = [][]int{
	{0, 10, 15, 20},
	{10, 0, 35, 25},
	{15, 35, 0, 30},
	{20, 25, 30, 0},
}

const INF = 1e9

// dp[mask][u]: Chi phí nhỏ nhất khi đã đi qua tập các thành phố biểu diễn bởi mask, và đang đứng ở thành phố u
var memo [][]int
var n int

func tsp(mask int, u int) int {
	// Nếu đã đi qua tất cả các thành phố (mask đầy các bit 1: (1 << n) - 1)
	// Trở về thành phố xuất phát (0)
	if mask == (1<<n)-1 {
		return dist[u][0]
	}

	// Nếu đã tính toán trước đó, trả về kết quả lưu trong memo
	if memo[mask][u] != -1 {
		return memo[mask][u]
	}

	ans := INF

	// Thử di chuyển đến mọi thành phố v chưa được ghé thăm
	for v := 0; v < n; v++ {
		if (mask & (1 << v)) == 0 { // Nếu thành phố v chưa đi
			newCost := dist[u][v] + tsp(mask|(1<<v), v)
			if newCost < ans {
				ans = newCost
			}
		}
	}

	memo[mask][u] = ans
	return ans
}

func main() {
	n = len(dist)
	
	// Khởi tạo bảng Memoization với kích thước (2^n) x n, giá trị -1
	totalMasks := 1 << n
	memo = make([][]int, totalMasks)
	for i := range memo {
		memo[i] = make([]int, n)
		for j := range memo[i] {
			memo[i][j] = -1
		}
	}

	// Bắt đầu từ thành phố 0, với mask ban đầu chỉ có bit 0 bật (0001 = 1)
	minCost := tsp(1, 0)

	fmt.Printf("Chi phí hành trình ngắn nhất qua tất cả các thành phố: %d\n", minCost)
}

5. Ứng dụng thực tế của Bitmask DP

• Tối ưu hóa phân bổ tài nguyên (Resource Assignment): Giao $N$ tác vụ cho $N$ máy chủ sao cho tối ưu hóa hiệu năng dựa trên ma trận năng lực tương ứng.

• Hệ thống thương mại điện tử & Khuyến mại: Tính toán tổ hợp các mã giảm giá (Voucher stacking) tối ưu nhất cho giỏ hàng mà không vi phạm các điều kiện xung đột.

• Đồ họa máy tính & Xử lý hình ảnh: Các bài toán liên quan đến việc phủ các đỉnh hoặc ô lưới (Grid tiling).

Bitmask DP mở ra một góc nhìn hoàn toàn mới: biến tập hợp trừu tượng thành các con số nhị phân gọn gàng để tính toán trong không gian trạng thái tuyến tính.