有關狀壓DP

【以下內容僅為本人在學習中的所感所想，本人水平有限目前尚處學習階段，如有錯誤及不妥之處還請各位大佬指正，請諒解，謝謝！】

引言

動態規劃雖然已經是對暴力演算法的優化，但在某些比較特別的情況下，可以通過一些小技巧進一步對其優化，通產我們會在時間與空間中做權衡，在時間可以接受度範圍內，適當的以時間為代價換取更小空間的佔用；在不爆空間的情況下，適當的以空間換時間。在此，本人將以目前總結的經驗詳細介紹狀態壓縮與狀壓DP。

狀態壓縮

（一）狀態

狀態指某個事物表現出來的形態（百度百科）。聯繫前面的文章（有關動態規劃 – PaperHammer – 部落格園 (cnblogs.com)），我們在分析解決動態規劃的問題時，其重點是在「分情況定變數」這一步，即有多少種選擇，如何選擇。不妨把這每一個選擇視為一個事物，則它表現出來的形態就是所做出的選擇，更進一步就是選擇的結果。所以，動態規劃中的狀態實際上就是每一種情況。

（二）壓縮

壓縮是一種通過特定的演算法來減小電腦文件大小的機制，其目的是減少所佔空間的同時提高運算速度（百度百科）。壓縮的本質是減小，但不可否認雖然減小了文件體積提高了傳輸速度，但會存在文件品質的下降。

（三）狀態壓縮

一般地，我們規定利用電腦的二進位性質來描述所做出的選擇，即將所有情況統一分為：行或不行、放或不放等兩種情況（將很多情況歸於兩類情況）。由此可以發現，對於狀態壓縮，我們是針對有多少種選擇進行了壓縮，即對空間進行優化，那麼根據互斥性原則（自己編的名字），對空間上的優化勢必會帶來時間上的複雜。所以，狀態壓縮在時間上其實是一種很暴力的思想，它需要遍歷每一種情況，每種情況有兩種選擇（0或1），最高會達到2n的時間複雜度，但針對一些題目，可以依靠某些限定條件，大幅降低時間複雜度，從而變相達到既優化了空間也優化了時間的目的。

【註：相關位運算內容在此不作說明】

舉例

（一）吃乳酪

鏈接：P1433 吃乳酪 – 洛谷 | 電腦科學教育新生態 (luogu.com.cn)

題意：房間里放著n塊乳酪。一隻小老鼠要把它們都吃掉，問至少要跑多少距離？老鼠一開始在(0,0)點處。

分析：據題意可將其抽象為，從原點出發，返回走過所有點的最小距離。最值問題容易想到搜索。搜索時跳過重複路徑，最後進行比較即可。

 1 using System;
 2 using System.Collections.Generic;
 3 using System.Linq;
 4 using System.Text;
 5 
 6 namespace ConsoleApp1
 7 {
 8     internal class Program
 9     {
10         static int n;
11         static double res = double.MaxValue;
12         static NodeToNode[][] ntn;
13         static int[] vis;
14         static void Main(string[] args)
15         {
16             Program p = new Program();
17             n = int.Parse(Console.ReadLine());
18             n += 1;
19             double[] x = new double[n], y = new double[n];
20             x[0] = 0;
21             y[0] = 0;
22             for (int i = 1; i < n; i++)
23             {
24                 string[] inp = Console.ReadLine().Split(' ');
25                 x[i] = double.Parse(inp[0]);
26                 y[i] = double.Parse(inp[1]);
27             }//錄入所有點，包括（0，0）
28             ntn = new NodeToNode[n][];
29             for (int i = 0; i < n; i++) ntn[i] = new NodeToNode[n];
30             for (int i = 0; i < n; i++)
31             {
32                 for (int j = 0; j < n; j++)
33                 {
34                     ntn[i][j].dis = Dis(x[i], y[i], x[j], y[j]);//計算每兩個點間的距離並編號
35                     ntn[i][j].next = j;
36                 }
37                 ntn[i] = ntn[i].OrderBy(k => k.dis).ThenBy(k => k.next).ToArray();//一定要注意這個排序方式！！！！！
38             }           
39 
40             //for (int i = 0; i < n; i++)
41             //    for (int j = 0; j < n; j++)
42             //        Console.WriteLine(ntn[i][j].dis + " " + ntn[i][j].next);
43 
44             vis = new int[n];
45             vis[0] = 1;
46             p.Dfs(0, 0.0, 1);
47             Console.WriteLine(res.ToString("0.00"));
48             //Console.ReadLine();
49         }
50         public void Dfs(int cur, double sum, int cnt)
51         {
52             if(cnt == n)
53             {
54                 res = res <= sum ? res : sum;
55                 return;
56             }
57             if (sum >= res) return;
58             for(int i = 0; i < n; i++)
59             {
60                 if(vis[ntn[cur][i].next] == 0 && cur != ntn[cur][i].next)
61                 {
62                     vis[ntn[cur][i].next] = 1;
63                     Dfs(ntn[cur][i].next, sum + ntn[cur][i].dis, cnt + 1);
64                     vis[ntn[cur][i].next] = 0;
65                 }
66             }
67         }
68         public struct NodeToNode
69         {
70             public double dis;
71             public int next;
72         }
73         private static double Dis(double x1, double y1, double x2, double y2)
74         {
75             return Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
76         }
77     }
78 }

View Code

這種思路本質上是對除原點以外的所有點，進行全排列，比較每一種排列結果，其時間複雜度為O(N*N!)，（應該是），在比賽中一般僅能承受N<=10的數據範圍。

 

 

再分析：因為在深度搜索中會出現大量重複訪問的數據，所以優化搜索演算法，最先想到的一般是記憶化處理，記住到達某一個點的最小距離。但這種方法不能保證最壞的情況，有一部分情況和之前無異。本題除了距離因素，就只剩乳酪因素，既然記住距離還不夠，那就只能在「乳酪」上下手了。

對於每個乳酪，只有兩種情況：吃過/沒吃過；抽象出來即，對於每個點：走過/沒走過。發現對於每個事物（乳酪/點），僅有兩種狀態（訪問過/沒訪問過），滿足基本狀態壓縮的前提，所以我們考慮使用二進位來表示每個狀態。

　　a.  大化小：最終問題是讓總距離最小，最終距離是基於每一次選擇得來的，那麼就把從一個點到一個新的點，這一選擇視為一個子問題。並且每次選擇總以最小最小距離為基礎進行操作，每次選擇處理方式相同。

　　b.  分情況定變數：對於每個點，只有兩種情況（走或不走）；我們需要知道當前這個點是否走過，所以要記錄當前所在點；還需要知道已經走過了幾個乳酪，所以要記錄對點（乳酪）的訪問情況，共兩個變數。用f[i][j]表示老鼠當前走到第i個點（乳酪）處，且走過的點的二進位狀態為j時，最短的距離。

如：可以使用二進位10100110來表示已經走過第2、3、6、8個乳酪（定義此處索引從1開始），此時j的值為166。需要注意的是，第i個狀態是從低位向高位的第i位，即從低位向高位進行轉移。

　　c.  推方程：如果要走這個點（保證該點可訪問）那麼f[i][j] = f[j][k – (1 << (i − 1)] + dis(i, j)其中f[i][j]表示以i為起點走成狀態j的最小距離，dis表示兩點間距離。

 

【解釋 k – (1 << i − 1) 】

（1）  符號『<<』：表示某十進位數對應的二進位數向右移，等價於對十進位數*2。

如：1 << 3表示將1對應的二進位編碼向右移動4位　　(1)10 = (0001)2 右移5位變為（1000）2 = （8）10 = 1 * 23

（2）式子：最終目標的狀態 – 當前位置的狀態 = 中間狀態

      如：（5）10 =（0101）2 = (0111)10 – (0010)2 = (7)10 – （2）10

                    上一個中間狀態 = 目標狀態 – 當前位置狀態

 

【難點】為什麼可以用 k & (1 << (i – 1)判斷合法位置

我們設一個狀態 k = 01101，表示第一、三、四列（從低位開始）中的某個點已經訪問過；

由於我們是一行一行訪問的，所以在k狀態我們應該訪問第三行的點了，那第三行我們應該訪問哪個點，或者說狀態k由哪些狀態轉移而來呢？

狀態k(01101)由三種狀態（必然是前兩行的狀態）來的：

　　前兩行在三、四列已訪問，第三行只好訪問第一列；(01100)

　　前兩行在一、四列已訪問，第三行只好訪問第三列；(01001)

　　前兩行在一、三列已訪問，第三行只好訪問第四列；(00101)

無非就是這三種情況，現在我們來考慮怎麼來表示狀態s由這三種狀態來的，k & (1 << (i – 1))就是用來實現這個功能的，即判斷當前情況是否為其上一個情況轉移而來。

for (int i = 1; i <= 4; i++)

　　01101 & (1<<0) = 01101 & 1 = 00001

　　01101 & (1<<1) = 01101 & 10 = 00000

　　01101 & (1<<2) = 01101 & 100 = 00100

　　01101 & (1<<3) = 01101 & 1000 = 01000

　　01101 & (1<<4) = 01101 & 10000 = 00000

由此得出，只有和k=01101有1重合結果才大於0，根據這個特性判斷此列是否可以訪問。

　　d.  定邊界：本題在搜索過程中不存在索引非法而導致的無法訪問點，但需要對初值進行設定，因為其默認值為0，我們需要存儲最小距離，所以應對初值設定為一個較大的值。

【註：文末程式碼中已附有更加詳細的注釋】

 

（二）01背包

【註：題目解析請轉至該文章有關動態規劃 – PaperHammer – 部落格園 (cnblogs.com)】

在該問題中，對於每種物品只有兩種選擇，放與不放，故也可以使用狀態壓縮進行優化。

如：有5件物品，

　　如果這5件物品都不放的話，那就是00000;

　　如果這5件物品都放的話，那就是11111;

觀察可知，在上面的例子中00000 ~ 11111可以代表所有的情況，轉化為十進位就是0到(1 << (5 – 1));

其中，所以f[10000]只能從f[00000] + W[1] 轉移過來；f[11000]可以從f[01000] + W[1]或者f[10000] + W[2]轉移過來,以此類推

總結

　　1.  注意位運算的運算等級順序，括弧很重要

　　2.  狀壓dp的特點一般是規模比較小，一般小於15，最多不超過20；而且一般只有兩種決策

狀態壓縮比較難理解，本篇文章也花了快兩周時間，雖然寫成了筆記，但本人理解程度依舊不深，在此希望與各位大佬相互交流一起學習

【感謝您可以抽出時間閱讀到這裡；受限於水平，內容可能會有許多不妥之處，許多地方可能存在錯誤，還請各位大佬留言指正，請見諒，謝謝！】

 

#附文中所提到的第一題的程式碼 及 狀壓模板

（1）吃乳酪

 1 using System;
 2 using System.Collections.Generic;
 3 using System.Linq;
 4 using System.Text;
 5 
 6 namespace ConsoleApp1
 7 {
 8     internal class Program
 9     {
10         static int n;
11         static double res = double.MaxValue;
12         static double[][] f;
13         static double[] x, y;
14         static void Main(string[] arg)
15         {
16             n = int.Parse(Console.ReadLine());
17             x = new double[20];
18             y = new double[20];
19             
20             for (int i = 1; i <= n; i++)
21             {
22                 string[] inp = Console.ReadLine().Split(' ');
23                 x[i] = double.Parse(inp[0]);
24                 y[i] = double.Parse(inp[1]);
25             }
26 
27             //初始化，因為之後的比較是取較小的一個，所以將所有值預設為最大
28             f = new double[20][];
29             for(int i = 1; i <= n; i++)
30             {
31                 f[i] = new double[35000];
32                 Array.Fill(f[i], double.MaxValue);
33             }
34 
35             DP(f, n);
36             Console.WriteLine(res.ToString("0.00"));
37             //Console.ReadLine();
38         }
39         static public double DP(double[][] f, int n)
40         {
41             for (int k = 1; k <= (1 << n) - 1; k++)
42                 for (int i = 1; i <= n; i++)
43                 {
44                     if ((k & (1 << (i - 1))) == 0) continue;//已經訪問過
45                     if (k == (1 << (i - 1)))
46                     {
47                         f[i][k] = 0;//標記為不可訪問
48                         continue;//當前位置與目標位置相同
49                     }
50                     for(int j = 1; j <= n; j++)
51                     {
52                         if ((k & (1 << (j - 1))) == 0 || i == j) continue;//如果不可訪問 或 兩個位置相同 則跳過
53                         f[i][k] = Math.Min(f[i][k], f[j][k - (1 << (i - 1))] + Dis(i, j));
54                     }
55                 }
56             for (int i = 1; i <= n; i++)
57             {
58                 double cur = f[i][(1 << n) - 1] + Dis(i, 0);
59                 res = Math.Min(res, cur);
60             }
61                 
62             return res;
63         }
64         private static double Dis(int a,int b)
65         {
66             return Math.Sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));
67         }
68     }
69 }

 

（2）一般狀壓模板

 1 int n;
 2 int maxn = 1 << n;//總狀態數。
 3     //枚舉已有的集合數。按照狀態轉移的順序，一般從小編號到大編號。
 4     for(int i = 1; i <= m; ++ i){
 5         //枚舉當前集合中的狀態。
 6         for(int j = 0; j < maxn; ++ j){
 7             //判斷當前集合是否處於合法狀態，通常我們需用一個數組提前處理好。如g數組;
 8             if(當前狀態是否合格){
 9                 for(int k = 0; k < maxn; ++ k){
10                     //枚舉上一個集合的狀態。
11                     if(上一個集合的狀態是否合格 + 上一個集合的狀態和當前狀態的集合是否產生了衝突){
12                         列寫狀態轉移方程。
13                     }
14                 }
15             }
16         }
17     }
18 }

Tags:

VirMach 便宜 VPS

QNews

QNews