状压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 | int n; |
由于状压dp的特性,我们只能求解n比较小的情况,否则内存就会超限。
思考上述代码后,我们可以发现,每一个比较小的节点集合都是由比较大的节点集合计算出来的。即对于两个集合S( i ) ∈ S( j ) ,有 i <= j 。我们在求S( i )时,需要先求出来S( j )的值。因此,我们也可以用循环的方法求解:
1 | int n; |
这就是最基础的状压dp问题。
(内容持续更新……)