状态压缩DP入门 POJ2686 Traveling by Stagecoach

这是我第一次写状态压缩的题目. 前不久在回家的说车上看完了这一章dp, 一直懒得敲代码, 昨晚就调试了一题. 虽然之前看了一遍书, 但是按照昨天的状态来看, 还是忘了不少.

使用状态压缩的动态规划问题, 其本质依然是一个动态规划问题, 所以要判断问题的状态是什么, 状态如何转移, 是否符合最有子结构, 是否不具有后效性, 最后还要考虑复杂的边界, 是一种需要先考虑很周全然后才能敲代码的问题. 在某些问题中, 一个状态可能需要用一个集合来表示(例如还剩下的车票的集合), 但是在dp的代码中, 状态作为一个数组的下标(例如dp[status]), 所以这个状态必须用一个Integer来表示. 因此我们就需要用Integer来表示一个集合的邪恶之力.

一个元素, 要么包含在集合中(1), 要么不包含在集合中(0); 一个集合可以用每一个元素是否包含在这个集合里面来表示, 因此可以用二进制来表示集合(例如1011表示0, 1, 3号物品在集合里面, 2号物品不在集合里面). 这样一个Integer就可以表示一个集合啦! 这样就是状压DP了! 真是很容易理解.

POJ2686这个问题也不复杂, 对我来说好玩的地方在于, 他本来是一个城市为点, 马路为边的一个无向图, 但是在求解问题的过程中, 把问题转化为了状态为点, 状态转移的费用为边的一个有向无环图, 最短路就是最优解. DAG正好可以用dp来求最短路. 下面代码的这个多层循环最让我赏(zi)心(yu)悦(zi)目(le):

  for (int S = (1 << n) - 1; S >= 0; S--) {
    res = min(res, dp[S][b]);
    for (int v = 1; v <= m; v++) {
      for (int i = 0; i < n; i++) {
        if (S >> i & 1) {
          for (int u = 1; u <= m; u++) {
            if (d[u][v] >= 0) {
              dp[S & ~(1 << i)][u] = min(dp[S & ~(1 << i)][u],
                                          dp[S][v] + d[u][v] / (double)t[i]);
            }
          }
        }
      }
    }
  }

其中,

S是剩余车票的集合;
v和u是城市标号;
i是第i号车票.

这每一层的循环嵌套顺序不能乱, 首先最外面是S的循环, 状态从11111111(n个1)开始, 代表所有车票都没有用出去, 费用为0, 这是状态的起点, 是已知条件. 循环到00000000结束, 这是车票全都花光的情况(不一定是目标状态, 只能代表所有状态遍历了一遍).

第二层循环是对城市的循环. 在第一层循环的基础上, 也就是在知道手里面还有多少张票的情况下, 再分析路线图里面的每个起点的情况.

对于每一个起点, 再遍历每一张车票, 就是第三层循环.

对于每一个起点配上某张车票的组合, 再选择一个重点城市, 就是第四层循环.

这样问题的答案就逐步逐步被计算出来, 从手里很多票的状态开始, 慢慢到手里面的票少了的情况. 每一种票的组合, 都试图给出可行解. 随着票被用出去, 可行解逐渐被松弛, 然后逐渐接近最优解. 从图论的角度来说, 这和Floyd是很像的; 从状态压缩来说, 因为

S--

能够满足题目要求的求解顺序, 所以不需要用到记忆化搜索的技术, 可以循环求解.