Bitmask DP

Nasıl düşünülür

Bitmask DP, durumun geçerli kümede hangi öğelerin olduğunu hatırlaması gereken problemler içindir. n bitlik bir mask üyeliği kodlar: i biti setse i öğesi kullanımda. DP geçişleri bir biti çevirerek bir öğe ekler/çıkarır. Ana kısıt: n ≤ ~20 olmalı çünkü durum uzayı 2^n’dir, n=20’de bir milyon durum, uygulanabilir; n=25’te 33 milyon, sınırda.

Kanonik problem TSP (gezgin satıcı): dp[mask][last], mask içindeki düğümleri ziyaret edip last’ta biten minimum maliyettir. Geçiş: ziyaret edilmemiş her j için dp[mask | (1<<j)][j] = min(dp[mask][last] + dist[last][j]). Temel: dp[1<<start][start] = 0. Cevap: kapalı tur için min(dp[(1<<n)-1][last] + dist[last][start]), açık için min(dp[full][last]).

Şablon şekilleri

Şekil	Temel hamle	Örnek
TSP	dp[mask][last]; ziyaret edilmemiş j ekle	LC 943
Atama / partisyon	dp[mask]; bir gruba öğe dene	LC 1655, LC 1799
Maliyetli alt küme seçimi	dp[mask]; kalanlar alt kümesinde geçiş	LC 1994
Renklendirme / kısıt	dp[mask][renk]; geçerli uzantılar	LC 1931

Karmaşıklık temeli

O(2^n * n) zaman, O(2^n * n) alan (veya last katlanırsa O(2^n)). n=20’de ~4 * 10^7 işlem, süreye sığar. n > 22’de problemin daha hızlı bir yapı kabul edip etmediğini düşün.

Şablondan probleme

1. n’nin ≤ ~20 olduğunu doğrula; daha büyükse farklı teknik ara (greedy, flow, meet-in-the-middle).
2. Maskı tanımla: hangi öğeler “kullanıldı” veya “ziyaret edildi”.
3. DP hücresini tanımla: dp[mask] veya dp[mask][ekstra] (son düğüm, sayı, grup).
4. Maskları küçükten büyüğe iterasyona et; her birinde kullanılabilir her öğeyi dene.
5. Cevabı tam masktan veya son boyut üzerinden min’den çıkar.

/** Bitmask DP template: TSP (open path) over a distance matrix. */

export function tspOpen(dist: number[][]): number {
  const n = dist.length;
  const full = (1 << n) - 1;
  const dp: number[][] = Array.from({ length: 1 << n }, () =>
    new Array<number>(n).fill(Infinity),
  );
  for (let i = 0; i < n; i++) dp[1 << i]![i] = 0;
  for (let mask = 1; mask <= full; mask++) {
    for (let last = 0; last < n; last++) {
      if (!(mask & (1 << last))) continue;
      const cur = dp[mask]![last]!;
      if (cur === Infinity) continue;
      for (let j = 0; j < n; j++) {
        if (mask & (1 << j)) continue;
        const next = mask | (1 << j);
        dp[next]![j] = Math.min(dp[next]![j]!, cur + dist[last]![j]!);
      }
    }
  }
  let ans = Infinity;
  for (let last = 0; last < n; last++) ans = Math.min(ans, dp[full]![last]!);
  return ans;
}

/** Bitmask DP template: TSP (open path) over a distance matrix. */

export function tspOpen(dist: number[][]): number {
  const n = dist.length;
  const full = (1 << n) - 1;
  const dp: number[][] = Array.from({ length: 1 << n }, () =>
    new Array<number>(n).fill(Infinity),
  );
  for (let i = 0; i < n; i++) dp[1 << i]![i] = 0;
  for (let mask = 1; mask <= full; mask++) {
    for (let last = 0; last < n; last++) {
      if (!(mask & (1 << last))) continue;
      const cur = dp[mask]![last]!;
      if (cur === Infinity) continue;
      for (let j = 0; j < n; j++) {
        if (mask & (1 << j)) continue;
        const next = mask | (1 << j);
        dp[next]![j] = Math.min(dp[next]![j]!, cur + dist[last]![j]!);
      }
    }
  }
  let ans = Infinity;
  for (let last = 0; last < n; last++) ans = Math.min(ans, dp[full]![last]!);
  return ans;
}