Bitmask DP

Bitmask DP adalah teknik dynamic programming di mana state menyertakan bitmask (integer yang merepresentasikan himpunan) untuk melacak subset elemen yang sudah diproses. Teknik ini cocok bila jumlah elemen kecil (biasanya n ≤ 20), sehingga 2^n state masih layak. Aplikasi paling klasik adalah Traveling Salesman Problem (TSP), assignment problem, dan counting Hamiltonian paths. Pada Chapter ini kita akan membedah struktur state, transisi berbasis bitmask, dan implementasi TSP.

Aturan: Bitmask sebagai Himpunan #

Bitmask adalah integer di mana bit ke-i merepresentasikan apakah elemen i sudah diproses (1) atau belum (0). Operasi bitwise memungkinkan manipulasi himpunan secara efisien:

(mask | (1 << i)) — tambahkan elemen i ke himpunan.
(mask & ~(1 << i)) — hapus elemen i.
(mask >> i) & 1 — cek apakah elemen i ada di himpunan.
__builtin_popcount(mask) — jumlah elemen (GCC/Clang built-in).

Mekanisme: State = (mask, last) #

State TSP: dp[mask][last] = biaya minimum untuk mengunjungi semua kota dalam mask, berakhir di kota last.

Recurrence:

text

dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][last] + dist[last][j])
                            untuk setiap j yang belum dikunjungi (bit ke-j di mask = 0)

Base case: dp[1 << start][start] = 0 — dimulai dari kota start, hanya kota start yang dikunjungi.

Jawaban: min(dp[(1 << n) - 1][last] + dist[last][start]) untuk setiap last — kembali ke kota awal.

flowchart TD A["State: mask, last"] --> B[Untuk setiap j yang belum dikunjungi] B --> C["Update dp[mask | 1<<j][j]"] C --> B

Kode: Traveling Salesman Problem #

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

long long tsp(const std::vector<std::vector<int>>& dist) {
    int n = static_cast<int>(dist.size());
    int full = (1 << n) - 1;
    std::vector<std::vector<long long>> dp(1 << n,
        std::vector<long long>(n, LLONG_MAX / 4));
    // Mulai dari kota 0
    dp[1 << 0][0] = 0;
    for (int mask = 0; mask <= full; ++mask) {
        for (int last = 0; last < n; ++last) {
            if (!(mask & (1 << last))) continue;  // last harus di mask
            if (dp[mask][last] == LLONG_MAX / 4) continue;
            for (int j = 0; j < n; ++j) {
                if (mask & (1 << j)) continue;     // j belum dikunjungi
                int new_mask = mask | (1 << j);
                long long cost = dp[mask][last] + dist[last][j];
                dp[new_mask][j] = std::min(dp[new_mask][j], cost);
            }
        }
    }
    // Kembali ke kota 0
    long long best = LLONG_MAX;
    for (int last = 0; last < n; ++last) {
        if (dp[full][last] == LLONG_MAX / 4) continue;
        best = std::min(best, dp[full][last] + dist[last][0]);
    }
    return best;
}

int main() {
    std::vector<std::vector<int>> dist = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    std::cout << "TSP minimum cost = " << tsp(dist) << '\n';
    return 0;
}

Output yang Dihasilkan:

text

TSP minimum cost = 80

Baris int full = (1 << n) - 1;: bitmask dengan semua n bit disetel ke 1 — merepresentasikan semua kota telah dikunjungi.
Baris std::vector<std::vector<long long>> dp(1 << n, std::vector<long long>(n, LLONG_MAX / 4));: tabel dp[mask][last]. LLONG_MAX / 4 digunakan sebagai sentinel “tak tercapai” agar penambahan tidak overflow.
Baris dp[1 << 0][0] = 0;: base case — mulai dari kota 0, biaya 0.
Baris if (!(mask & (1 << last))) continue;: last harus sudah ada di mask agar state valid.
Baris if (mask & (1 << j)) continue;: skip j yang sudah dikunjungi.
Baris int new_mask = mask | (1 << j);: tambahkan j ke himpunan kunjungan.
Baris dp[new_mask][j] = std::min(dp[new_mask][j], cost);: update minimum cost untuk state (new_mask, j).
Hasil 80: rute 0 → 1 → 3 → 2 → 0 = 10 + 25 + 30 + 15 = 80. Optimal.

Kompleksitas dan Batas Praktis #

Dimensi	Nilai	Catatan
Jumlah state	`2^n × n`	Untuk TSP
Transisi per state	`n`	Coba setiap kota berikutnya
Waktu total	`O(2^n × n²)`	Untuk TSP
Ruang	`O(2^n × n)`	Bisa dioptimasi dengan rolling

Batas praktis (1 detik):

n = 15: 2^15 × 15² ≈ 7,4 juta operasi — cepat.
n = 18: 2^18 × 18² ≈ 85 juta — masih OK dalam 1-2 detik.
n = 20: 2^20 × 20² ≈ 420 juta — batas atas praktis.
n = 22: ~2 miliar operasi — tidak praktis tanpa optimasi lanjutan.

Optimasi Memori dengan Rolling Array #

Karena transisi selalu menambah bit ke mask (dari mask ke mask | (1 << j)), kita bisa mengisi tabel berdasarkan jumlah bit (popcount):

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

long long tsp_rolling(const std::vector<std::vector<int>>& dist) {
    int n = static_cast<int>(dist.size());
    int full = (1 << n) - 1;
    std::vector<long long> dp(1 << n, LLONG_MAX / 4);
    dp[1 << 0] = 0;
    for (int mask = 0; mask <= full; ++mask) {
        if (dp[mask] == LLONG_MAX / 4) continue;
        for (int j = 0; j < n; ++j) {
            if (mask & (1 << j)) continue;
            int new_mask = mask | (1 << j);
            // Cari last = elemen mana yang terakhir dikunjungi
            // (perlu loop untuk mencari)
            for (int last = 0; last < n; ++last) {
                if (!(mask & (1 << last))) continue;
                long long prev = dp[mask];  // perlu dp[mask][last] - lihat catatan
                // Catatan: implementasi penuh perlu dp[mask] = min(dp[mask][last])...
            }
        }
    }
    return dp[full];
}

Variasi: Hamiltonian Path Count #

Masalah: hitung jumlah Hamiltonian path (jalur yang mengunjungi setiap node tepat sekali) pada graph.

State: dp[mask][last] = jumlah jalur yang mengunjungi himpunan mask, berakhir di last.

Recurrence (counting, bukan min):

text

dp[mask | (1 << j)][j] += dp[mask][last]   untuk setiap j yang belum dikunjungi
                                        dan edge (last, j) ada

Base case: dp[1 << i][i] = 1 untuk setiap i — mulai dari mana saja.

Variasi: Assignment Problem #

Masalah: diberikan n pekerja dan n tugas dengan biaya cost[i][j], tugaskan setiap pekerja ke tepat satu tugas, meminimumkan total biaya.

State: dp[mask] = biaya minimum bila tugas-tugas dalam mask sudah ditugaskan ke |mask| pekerja pertama.

Recurrence: untuk mask dengan k = popcount(mask) bit, coba tambah tugas j yang belum ditugaskan:

text

dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + cost[k][j])

Kompleksitas O(2^n × n) — lebih cepat dari TSP karena tidak perlu dimensi last.

Kode: Assignment Problem (Hungarian Alternatif) #

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

long long assignment(const std::vector<std::vector<int>>& cost) {
    int n = static_cast<int>(cost.size());
    std::vector<long long> dp(1 << n, LLONG_MAX / 4);
    dp[0] = 0;
    for (int mask = 0; mask < (1 << n); ++mask) {
        if (dp[mask] == LLONG_MAX / 4) continue;
        int k = __builtin_popcount(mask);  // pekerja ke-k
        for (int j = 0; j < n; ++j) {
            if (mask & (1 << j)) continue;  // tugas j belum ditugaskan
            int new_mask = mask | (1 << j);
            dp[new_mask] = std::min(dp[new_mask], dp[mask] + cost[k][j]);
        }
    }
    return dp[(1 << n) - 1];
}

int main() {
    std::vector<std::vector<int>> cost = {
        {9, 2, 7, 8},
        {6, 4, 3, 7},
        {5, 8, 1, 8},
        {7, 6, 9, 4}
    };
    std::cout << "Biaya minimum assignment = " << assignment(cost) << '\n';
    return 0;
}

Output yang Dihasilkan:

text

Biaya minimum assignment = 13

Baris int k = __builtin_popcount(mask);: pekerja yang sedang ditugaskan = jumlah bit set di mask. Tidak perlu dimensi last seperti TSP.
Baris dp[new_mask] = std::min(dp[new_mask], dp[mask] + cost[k][j]);: tugaskan pekerja k ke tugas j, tambahkan biaya.
Hasil 13: penugasan optimal pekerja 0→1 (2), 1→0 (6), 2→2 (1), 3→3 (4). Total 2+6+1+4 = 13.

Pola Umum Bitmask DP #

Masalah	Dimensi State	Waktu
TSP	`2^n × n`	`O(2^n × n²)`
Hamiltonian path count	`2^n × n`	`O(2^n × n²)`
Assignment problem	`2^n`	`O(2^n × n)`
Steiner tree	`2^k × n`	`O(3^k × n + 2^k × n²)`
Subset sum (boolean)	`2^n`	`O(2^n)`

Tips Implementasi #

Selalu pakai long long untuk dp — 2^20 × n² bisa overflow int.
Sentinel “tak tercapai”: LLONG_MAX / 4 agar penambahan tidak overflow.
Iterasi mask dari 0 hingga (1 << n) - 1 dalam urutan naik.
Untuk debugging, cetak mask dalam biner dengan std::bitset.

Ringkasan #

Bitmask DP: state menyertakan bitmask untuk himpunan kecil (n ≤ 20).
Operasi bitwise: | (tambah), & ~(1<<i) (hapus), >> i & 1 (cek), __builtin_popcount (hitung).
TSP klasik: dp[mask][last], transisi coba setiap kota belum dikunjungi. O(2^n × n²).
Assignment problem: dp[mask] saja (lebih cepat, O(2^n × n)).
Batas praktis: n ≤ 20 dalam 1-2 detik.