四大dp系列--状压dp

状压dp

状态压缩dp,是一种将复杂的状态压缩成二进制数字的算法。

旅行商问题

我们来看一个经典的旅行商问题:

给定一个n个顶点组成的带权有向图的距离矩阵d(i,j)(INF表示没有边)。要求从顶点0出发,经过每个顶点恰好一次后再回到顶点0。问所经过的边的总权重的最小值是多少?(来源于《挑战程序设计竞赛》)。

限制条件:

2<=n<=15

0<=d(i,j)<=1000

所有可能的路线会有 (n-1)! 种结果,因此我们不能够使用暴力的方法求解,那么我们需要用高效的方法来求解。

假如我们对每个顶点编号。我们可以用一个数的二进制来表示走过的集合 S

当n=5时,00000表示所有顶点均未走过,00001表示经过编号为0的顶点,10001表示经过第0和第4个顶点。11111表示经过所有的顶点。

这样,我们就能使用2^n次方个数来表示出所有的状态。

定义dp[S][v]:从v出发,访问剩余未访问过的节点所需要的最小花费。特别的,当S=2^n-1,v=0时,dp[S][v]=0。

从dp[S][v]的定义,我们也可以看出如下递推式:
$$
dp[S][v]=min(dp[S∪{u}][u]+d[v][u] | u∉S)
$$
其中u表示从v出发到达的下一个顶点。 S ∪ { u } 表示现在经过的所有顶点,由于是从 v 到 u ,所以当前的出发点也为u。d[v][u]表示从顶点 v 到顶点 u 的花费。

找出了递推式,我们就可以使用记忆化搜索的方式找出最小花费:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int n;
int d[maxn][maxn];//储存地图信息,初始化为 INF
int dp[1<<maxn][maxn];//记忆化搜索使用的数组
int rec(int S,int v){//当前走过的节点集合 S,出发顶点v
if(dp[S][v]>=0){
return dp[S][v];//由于我们使用的是递归的方法,所以如果有解,储存的一定是最优的解
}
if(S==(1<<n)-1 && v==0){//访问过所有定点,并且回到最初起点0,那么在这个状态之后的花费一定是0,即不需要再有其他的花费
return dp[S][v]=0;
}
int res=INF;
for(int u=0;u<n;u++){
if(!(S>>u&1)){//第u个节点未被访问
res=min(res,rec(S|1<<u,u)+d[v][u]);//递归 S|1<<u表示走过u之后的节点集合,因为是走到u,所以新的出发点也是u
}
}
return dp[S][v]=res;
}
int solve(){
memset(dp,-1,sizeof(dp));//-1表示未被访问过
printf("%d\n",rec(0,0));
}

由于状压dp的特性,我们只能求解n比较小的情况,否则内存就会超限。

思考上述代码后,我们可以发现,每一个比较小的节点集合都是由比较大的节点集合计算出来的。即对于两个集合S( i ) ∈ S( j ) ,有 i <= j 。我们在求S( i )时,需要先求出来S( j )的值。因此,我们也可以用循环的方法求解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int n;
int d[maxn][maxn];
int dp[1<<maxn][maxn];
void solve(){
for(int S=0;S<1<<n;S++){
fill(dp[S],dp[S]+n,INF);
}
dp[(1<<n)-1][0]=0;
for(int S=(1<<n)-2;S>=0;S--){
for(int v=0;v<n;v++){
for(int u=0;u<n;u++){
if(!(S>>u&1)){
dp[S][v]=min(dp[S][v],dp[S|1<<u][u]+d[v][u]);
}
}
}
}
printf("%d\n",dp[0][0]);
}

这就是最基础的状压dp问题。

(内容持续更新……)

感谢您的支持
-------------本文结束感谢您的阅读-------------