【45. 状态压缩DP（最短Hamilton路径）】

状态压缩思想：

• 用一个整数来表示一个状态，整数把它当做二进制的数，二进制数中的每一位是0还是1，表示俩种不同的情况
• 状态压缩的特点：要把所有不同的状态压缩到一个整数里面，所以不同的状态个数不会多，一般n = 20就极限了，2²⁰ = 10e6

1. 例子：

• 首先想下暴力算法比如数据有 5 个点，分别是 0,1,2,3,4那么在爆搜的时候，会枚举一下六种路径情况（只算对答案有贡献的情况的话）：

case 1: 0→1→2→3→4
case 2: 0→1→3→2→4
case 3: 0→2→1→3→4
case 4: 0→2→3→1→4
case 5: 0→3→1→2→4
case 6: 0→3→2→1→4
1
2
3
4
5
6

• 观察一下 case 1 和 case 3，可以发现，我们在计算从点 0 到点 3 的路径时，其实并不关心这两中路径经过的点的顺序，而是只需要这两种路径中的较小值，因为只有较小值可能对答案有贡献。
• 所以，我们在枚举路径的时候，只需要记录两个属性：当前经过的点集，当前到了哪个点。
  而当前经过的点集不是一个数。观察到数据中点数不会超过 20，我们可以用一个二进制数表示当前经过的点集。其中第i位为 1/0 表示是/否经过了点 i。

状态表示

• f[state][j]。其中 state 是一个二进制数，表示点集的方法如上述所示。

  • 集合：经过的点集为 state，且当前到了点 j 上的所有路径。
  • 属性：路径总长度的最小值

状态计算

• 假设当前要从点 k 转移到 j。那么根据 Hamilton路径的定义，走到点k 的路径就不能经过点 j，所以就可以推出状态转移方程
  • f[state][j] = min{f[state ^ (1 << j)][k] + w[k][j]}
  • w[k][j]表示从点 k 到点 j 的距离
  • state ^ (1 << j)是将 state 的第 j 位改变后的值，即
    • 如果 state的第 j 位是 1 那么将其改为 0
    • 否则将 state 的第 j 位改为 1

由于到达点 j 的路径一定经过点 j，也就是说当 state 的第 j 位为 1 的时候，f[state][j]才可以被转移，所以 state ^ (1 << j) 其实就是将 state的第 j 位改为 0，这样也就符合了 走到点 k 的路径就不能经过点 j 这个条件。

问题1：

1. 哪些点被用过
2. 目前停在那个点上

f[state][j] = f[state_k][k] + weight[k][j] 假设是从k这个点转移过来的,加上从k到j的距离
stata_k = state出掉j之后的集合,state_k要包含k

问题2：state怎么表示一个集合

• 用二进制的整数表示state,用20位整数来表示，当为1，则走过，为0没走过

• (如果题目给了5个点，那么需要5位的二进制表示)当走完所有点后，5位全会变成1

• 而5个1的状态，必然是由4个1，1个0的状态转变过来的(只需要关心，这4个1的点，从哪一个点走到0这个点的路径最短)

• 只需要关心0的状态转移 4个0 -> 3个0 -> 2个0 -> 1个0 ->全1 ,维护他们之间状态转移的最小值

dp[i][j]表示从第i个状态，也就是那个点被用过（01011），停在了第j号点（j不是最终完成任务的点，题目是从0号点标记的）——>(i状态下的第j位)

dp[i][j] -> 当变成1个0时，从2个0状态变过来的最短路径(可能从1号点过来最短，可能2号，可能3号)
01011 1 
01011 2 
01011 3 
1
2
3
4

答案

• 所有状态转移完后，根据 f[state][j]的定义，要输出 f[111⋯11(n个1)][n−1]。
  • 那么怎么构造 n 个 1 呢，可以直接通过 1 << n 求出 100⋯0(n个0)，然后减一即可。

时间复杂度

• 2^20 * 20 = 2 * 10^ 7
• 状态数量 * 状态转移 = (2 * 10 ^ 7 ) * 20 = 4亿,7秒算7亿次，

为什么把数组定义到全局变量里？

• 一个代码有一个虚拟空间，假设内存4g，那么代码对应的虚拟空间是2^32,整个内存空间分为上下俩个部分，上面是栈空间，底下是堆空间，所有开在函数内部的变量或数组开到栈里面，所有开在静态变量或者全局变量的会开在堆里，c++默认的栈空间是4兆，此时如果把很大数组放在主函数，那么栈可能爆掉
• 而且开在全局，默认初始化值为0

2. 题目

3. 代码

#include 
#include 
using namespace std;

const int N = 20, M = 1 << N;
int dp[M][N];               //有n个点，点之间的距离为10e7
int w[N][N];                //存储点到点的距离

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            cin >> w[i][j];
            
            
    //因为存储的是最小值，所以dp应该首先初始化最大值
    memset(dp, 0x3f, sizeof dp);
    
     //起点在0号点，对应的状态是1（二进制状态下是1,00000000001，第0号点最右边的点，十进制表示1）
    dp[1][0] = 0;
    
    for (int i = 1; i < 1 << n; i ++)       //枚举位数，使得每一位都变成0
        // if (i & 1)                       //当最后一位出现0是不合法的，起点就是走过的点，需要将这个点排除出去
            for (int j = 0; j < n; j ++)   //枚举终点，他不是最后的一个点，只是停留点，需要往这个点靠拢
                  if (i >> j & 1)          //停在j这个点上，代表已经走过了，检验这个状态也要合法，下面开始转移
                        for (int k = 0; k < n; k++)
                            if (i - (1 << j) >> k & 1)  //检测第k这个点是否合法     
                            {
                                //上面已经验证i状态下的第j位是1，而我们是从k跳到j的，所以不包含j，要减去j  
                                dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + w[k][j]) ; 
                            }
                     
     cout << dp[(1 << n)- 1][n - 1];                 
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37