動態(tài)規(guī)劃——狀壓DP 學(xué)習(xí)筆記

引入

前置知識：位運(yùn)算

動態(tài)規(guī)劃的過程是隨著階段的增長，在每個狀態(tài)維度上不斷擴(kuò)展的。

在任意時刻，已經(jīng)求出最優(yōu)解的狀態(tài)與尚未求出最優(yōu)解的狀態(tài)在各維度上的分界點(diǎn)組成了 DP 擴(kuò)展的“輪廓”。對于某些問題，我們需要在動態(tài)規(guī)劃的“狀態(tài)”中記錄一個集合，保存這個“輪廓”的詳細(xì)信息，以便進(jìn)行狀態(tài)轉(zhuǎn)移。

若集合大小不超過 \(N\)，集合中每個元素都是小于 \(K\) 的自然數(shù)，則我們可以把這個集合看作一個 \(N\) 位 \(K\) 進(jìn)制數(shù)，以一個 \([0, K^{N - 1}]\) 之間的十進(jìn)制整數(shù)的形式作為 DP 狀態(tài)的一維。這種把集合轉(zhuǎn)化為整數(shù)記錄在 DO 狀態(tài)中的一類算法，就被稱為狀態(tài)壓縮的動態(tài)規(guī)劃算法。

定義

意義

狀態(tài)壓縮，即在數(shù)據(jù)范圍較小的情況下，將每個物品或者東西選與不選的狀態(tài)壓縮為一個整數(shù)的方法。

狀態(tài)壓縮，即以最小代價來表示某種狀態(tài)的方式，通常是用一串二進(jìn)制數(shù)（\(01\) 串）來表示各個元素的狀態(tài)，通常我們稱這些情況叫做子集、設(shè)為 \(S\)。

然而還有其他的狀壓方法，例如三進(jìn)制狀壓法等等，但不大常用。

本質(zhì)

所以狀壓 DP，本質(zhì)上是與 DP 無異的，它沒有改變 DP 本質(zhì)的優(yōu)化方法，階段還是要照分，狀態(tài)還是老樣子，決策依舊要做，轉(zhuǎn)移方程還是得列，最優(yōu)還是最優(yōu)，無后性還是無后性，所以它還是比較好理解的。所以最明顯的標(biāo)志就是數(shù)據(jù)不能太大，大約是 \(n \le 20\)。

遍歷所有狀態(tài)的正確姿勢就是用二進(jìn)制的位運(yùn)算來遍歷。這大概就是狀壓 DP 的精髓了吧！

應(yīng)用

什么時候用？

• 數(shù)據(jù)范圍：范圍在 \(20\) 左右時正常的狀壓；很多時候會有一些 NP 問題會用狀壓求解。
• 是否可以壓縮：一般的狀態(tài)壓縮都是選擇或者不選擇，放或者不放，遇見這種東西一般時狀壓。
• 常見題目模型：比如 TSP，覆蓋問題之類的。經(jīng)常會有這種模型的題出現(xiàn)就可以使用狀壓。

狀態(tài)設(shè)計(jì)

在使用狀壓 DP 的題目當(dāng)中，往往能一眼看到一些小數(shù)據(jù)范圍的量，切人點(diǎn)明確。而有些題，這樣的量并不明顯，需要更深人地分析題目性質(zhì)才能找到。

1. 狀態(tài)跟某一個信息集合內(nèi)的每一條都有關(guān)。
2. 若干條精簡而相互獨(dú)立的信息壓在一起處理。（如每個數(shù)字是否出現(xiàn)）

例題：旅行商（TSP）問題

狀態(tài)壓縮最經(jīng)典的問題應(yīng)該就是旅行商問題了。

問題描述

旅行商問題（Travelling Salesman Problem，TSP），給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次并回到起始城市的最短回路。

如何運(yùn)用狀態(tài)壓縮

比如一共有 \(5\) 個點(diǎn)：\(\{1\:2\:3\:4\:5\}\)。現(xiàn)在要表示已經(jīng)走過的地方和沒走過的地方，我們可以用 \(\{0, 1\}\) 來表示。其中 \(0\) 表示沒到過，\(1\) 表示到達(dá)過。那么對應(yīng)的狀態(tài)有：

1 2 3 4 5
0 0 0 0 0（剛要開始走，還沒有到達(dá)的地方）
0 0 0 0 1（已經(jīng)到過第五個點(diǎn)）
0 0 0 1 0（已經(jīng)到過第四個點(diǎn)）
0 0 0 1 1（已經(jīng)到過第四，五個點(diǎn)）
......

我們發(fā)現(xiàn)以上的狀態(tài)可以用二進(jìn)制數(shù)表示，二進(jìn)制數(shù)就是由 \(\{0, 1\}\) 組成的。并且 \(2^5\) 可以涵蓋所有的情況，從 \(0\:0\:0\:0\:0\) 到 \(1\:1\:1\:1\:1\)；

\(dp[i][S]\) 表示走到 \(i\) 這個點(diǎn)，已經(jīng)經(jīng)過的地方為 \(S\)，此時所走過的最短路。

狀態(tài)轉(zhuǎn)移

舉個栗子，當(dāng) \(S = (11011)_{\mathrm B}\) 的時候，\(S\) 可以是由 \(11001\) 來，也可以是從 \(11010\) 來：

for (int j = 1; j <= n; ++j) {
    if (i == j || (s & (1 << (j - 1))) == 0) continue;
    dp[i][s] = min(dp[i][s], dp[j][s - (1 << (i - 1))] + dis(i, j));
}

練習(xí)題

見：https://www.luogu.com.cn/training/384914

Reference

[1] https://www.luogu.com.cn/blog/new2zy/zhuang-ya-zhuang-ya-post
[2] https://www.luogu.com.cn/blog/yijan/zhuang-ya-dp
[3] https://www.luogu.com.cn/blog/DestinHistoire/zhuang-tai-ya-su-dp
[4] https://www.cnblogs.com/maoyiting/p/13368682.html
[5] https://blog.csdn.net/qq_44579321/article/details/129489274
[6] https://blog.csdn.net/weixin_44254608/article/details/105761281文章來源地址http://www.zghlxwxcb.cn/news/detail-710481.html

到了這里，關(guān)于動態(tài)規(guī)劃——狀壓DP 學(xué)習(xí)筆記的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！