【算法与数据结构】——状态压缩DP

约定不等于承诺〃 2022-09-12 06:46 203阅读 0赞

# 状态压缩DP简介 #

在动态规划状态设计中，若状态是一个集合，例如S=\{1,0,1,1,0\},则表示第1,2,4个节点被选中（从右向左对应0-4号节点）。若集合的大小不超过N，则集合中的每个元素都是小于K的正整数，可以把这个集合看作一个N位K进制数，以一个\[0, K N K^N KN\-1\]的十进制整数作为DP状态。可以将S=\{1,0,1，1,0\}看作一个5位二进制数10110，其对应的十进制数为21。  
这种将集合作为整数记录状态的一类算法叫做状态压缩DP。

# 经典旅行商问题 #

旅行商问题(TSP)指一个旅行商从一个城市出发，经过每个城市一次且只有一次回到原来的地方，要求经过的距离最短。TSP问题是一个NP难题，目前没有多项式时间的高效算法。可以尝试用动态规划解决。  
假设已访问的节点集合为S（将源点0作为未被访问的节点，因为从0出发，所以要回到0），当前所在的节点为u。  
**状态表示**：dp\[S\]\[u\]表示已经访问的节点集合为S，从u出发走完所有剩余节点回到源点的最短距离。  
**状态转移方程**：若当前u的邻接点v未访问，则dp\[S\]\[u\]由两部分组成，第1部分是u到v的边值，第2部分是从v出发走完所有剩余节点再回到源点的最短距离。访问完v之后，已访问的节点集合变为 S ∪ v S\\cup\{v\} S∪v，若u有多个未访问的邻接点v，则取最小值。dp\[S\]\[u\]=min\{dp\[ S ∪ v S\\cup\{v\} S∪v\]\[v\]+d\[u\]\[v\]  v ∉ S v\\notin S v∈/S\}，如下图所示。  
临界条件：dp\[(1<<n)-1\]\[0\]=0，表示若所有节点都已被访问，则此时已经没有剩余节点，从0节点出发走完所有剩余节点回到源点的最短距离为0。  
旅行商问题可以采用递推和记忆化递归两种方法求解。

1.  递推  
    以递推的方法求解旅行商问题指从临界条件开始枚举每一种状态S，若u=0或者u已被访问，而v未被访问，则判断是否可以借助v更新dp\[S\]\[u\],直到求解出答案dp\[0\]\[0\]。时间复杂度为 O ( n 2 2 n ) O(n^2 2^n) O(n22n)。  
    算法代码：

void traveling(){ //计算dp[S][u]
    dp[(1<<n)-1][0];//1<<n要加括号
    for(int S=(1<<n)-2;S>=0;S--)//(1<<n)-2表示源点0未被访问，其他节点都已访问
    for(int u = 0;u < n;u++)
    for(int v = 0;v < n;v++)
    { 
    if((u!=0&&!(S>>u&1))||g[u][v]==INF)continue;//u节点不是源点同时u未被访问或者uv不是邻接点，跳过节点v
    if(!(S>>v&1)&&dp[S][u]>dp[S|1<<v][v]+g[u][v])//若v节点未被访问
    { 
    	dp[S][u]=dp[S|1<<v][v]+g[u][v];
    	path[S][u]=v;//记录后继节点
    }
    }
    }

1.  记忆化递归  
    采用记忆化递归的方法求解旅行商问题时，首先确定递归结束的条件和递归式，然后记忆化递归即可。  
    a.递归结束的条件为上面递推方法的初始条件：当S=(1<<n)-1且u=0时，返回dp\[S\]\[0\]=0。  
    b.递归式：traveling(S,u)=min(ans,traveling(S|1<<v,v)+g\[u\]\[v\])。  
    c.记忆化递归：将dp\[\]\[\]数组初始化为-1，若已赋值，则直接返回。  
    算法代码：

int traveling(int S, int u)//计算dp[S][u]
    { 
    if(dp[S][u])
    return dp[S][u];
    if(S==(1<<n)-1&&u==0)//递归结束条件
    return dp[S][u]==0;
    int ans = INF;
    for(int v = 0;v<n;v++)
    { 
    if(!(S>>v&1)&&g[u][v]!=INF)
    ans+=min(ans,traveling(S|1<<v,v)+g[u][v]);
    }
    return dp[S][u]=ans; 
    }