码农的自我修养——插头DP

码农的自我修养——插头DP

想不到促使我学习插头DP的动机竟然是一道算法课的Lab题,还被网上的假教程演了半天……姑且把学到的东西写一写,纪念一下我对着一屏幕的表画了大半天图的自闭时光。

起这个标题的原因实在一篇博客里看到“转移过程十分码农”,敲完代码深以为然,就借用过来了。

以下内容仅为插头DP的一种应用情形。若要应用于其他题目,需要对过程略作修改。

前置知识:状态压缩DP、BFS、哈希

问题背景

给定一张\(n \times n\)有障碍物方格纸(\(n \leq 8\)),问从\((1, 1)\)\((1, n)\)一共有多少条Hamilton路径?(为方便后文叙述,此处做了转置处理)

image-20200315231540841

前置概念

插头和括号匹配

把上面的图一切两半,在断口处会有“被切断的路”,这就是这个问题模型里的插头

为什么会和括号匹配有关系呢?在这张方格纸上画回路(或者Hamilton路,额外加一条边就能构成回路)本质上是在构建一张平面图。从断口的一侧看,如果同一条路径与断口的两个交界处看成一组括号,那么在断口上可以得到一组合法的括号匹配序列。这个性质可以由反证法得出,此处略去。

image-20200316000043385

如图,在“断口”的每一侧都能得到一组合法括号匹配序列。因此,我们可以把插头分为两类——“左括号”插头“右括号”插头

保证括号匹配合法性是解决题目的关键。

轮廓线

整个搜索过程本质上是一行一行往下扫描的,因此在已遍历部分和未遍历部分中间有一条分界的轮廓线。整个DP的过程其实也就是轮廓线的转移过程。假设当前遍历到的格子坐标为\((i, j)\),那么对应的轮廓线如图:

image-20200315233958018

不难观察到,若方格纸宽度为\(n\),则轮廓线的长度为\(n+1\)。特殊地,当\(j = 0\)时,轮廓线形状如图:

image-20200315234209189

这个特点在后面状态转移的时候会提及。

状态转移

为方便后续描述,记\(0, 1, 2\)分别为无插头、“左括号”插头(简称左插头)、“右括号”插头(简称右插头);\(\neq 0\)泛指有插头。

如果轮廓线上的插头状态能用数字\(S\)来表示,那么我们就可以用\((i, j, S)\)来刻画格子\((i, j)\)对应的状态了。对于每一个“单元轮廓线”,其状态有三种:没有插头\(0\))、有左插头\(1\))和有右插头\(2\))。为了方便起见,我们可以使用四进制表示,用位运算的方法加快转移。

对于位置\((i, j)\)上的方格,其状态转移过程如图(以\(n = 5\)为例):

image-20200316001325572

特殊地,当\(j = n\)时,我们发现有一条轮廓线竖直贴到了最右边。这并不是我们期望的状态,所以需要做一下修正:

image-20200316002332701

注意对应下标的变化,对应到\(S\)上需要做移位操作(四进制)。整个过程其实就是一行一行扫描的过程。

由于上一行的\(a'_n\)会被舍去,所以\(a'_n \neq 0\)的状态是非法的。转移的时候要注意。

如果沿用上面的标记,那么初始状态就应该是\(a_1 = 1, a_n = 2\),其余地方均为\(0\)。我们给这个状态初始化为\(1\),表示这样的状态有一种可能性。该状态如图所示:

image-20200316104905653

在上方人为添加一条线,实际上就成了Hamilton回路问题


接下来的部分,就是非常码农的状态转移了。

啰嗦一句,这里的状态转移就是把当前状态\(S\)的情况数累加到下一个状态\(S'\)上,前提是通过对当前格子的操作可以使\(S\)变成\(S’\)

由于每次转移只有两个插头发生了变化(忽略换行的情形),我们可以把这些情形全部枚举出来一一讨论(红色代表\(S\),橙色代表\(S’\)):

image-20200316003249977

  1. \((\neq 0, 0)\)的情形

    只有一个插头的情形,只需要把这个插头(对应的路)拓展一格就好了。我们可以向下做拓展:

    image-20200316113928163

    注意拓展后的插头类型和拓展前一致。如果当前\(j \neq n\),还可以向右做拓展:

    image-20200316114228937

    写成数学符号的形式就是: \[ (\neq 0, 0) \rightarrow \begin{cases} (\neq 0, 0) \\ (0, \neq 0) \text{ if } j \neq n \end{cases} \]

  2. \((0, \neq 0)\)的情形

    和上面的情形一样,可以向下或者向右(若\(j \neq n\))拓展:

    image-20200316115027562

    用符号表达就是: \[ (0, \neq 0) \rightarrow \begin{cases} (\neq 0, 0) \\ (0, \neq 0) \text{ if } j \neq n \end{cases} \]

  3. \((0, 0)\)的情形

    如果两边都没有插头,那就只能自力更生新建插头了。为了适应后面的转移,定义新插头状态为\((1, 2)\)

    image-20200316115947885

    符号表达: \[ (0, 0) \rightarrow (1, 2) \text{ if } j \neq n \]

  4. \((\neq 0, \neq 0)\)的情形

    两个插头的情形,只要把这两个插头接起来就大功告成了?

    image-20200316120553557

    符号表达: \[ (\neq 0, \neq 0) \rightarrow (0, 0) \] 错!

    对于当前题目,我们需要的是一条Hamilton路,也就是说中间不能出现其它回路。因此我们需要格外注意括号配对的问题。

    下面对四种情况进行分类讨论:

    • \((2, 1)\)的情形

      右插头和左插头连接(注意顺序),其实是把两段独立的线接在了一起。没有问题,直接转移。

    • \((1, 1)\)的情形

      左插头和左插头连接,意味着从起点出发的线和一条独立的线接在了一起,作为一条新的起点出发的线。于是我们需要对这条线进行一下修正:

      image-20200316122142085

      如图所示,右边的这个\(1\)有一个对应的\(2\),我们需要将其修改为\(1\)。我们可以由括号匹配法则向右搜索找到这个\(2\)。这样一来,整个轮廓线上的括号匹配合法性也得到了保证。

    • \((2, 2)\)的情形

      同理,我们需要对左边的\(2\)对应的线进行修正。由括号匹配法则向左找到匹配的\(1\)并修改成\(2\)

      image-20200316134439530

    • \((1, 2)\)的情形

      左插头和右插头连接,意味着一个回路的闭合。在这道题目里,我们只能在最后一个遍历到的方格完成这个操作,其余的情况都不能做转移,需要剪枝。

  5. 障碍物的情形

    障碍物意味着线路需要绕过当前方格,因此也需要状态转移。唯一合法的转移只有\((0, 0) \rightarrow (0, 0)\)

    image-20200316135243207

最终只需要检查\((n + 1, 1, 0)\)这个状态的值就完成了。(应该也可以检查\((n, n, ?)\)的状态吧?依实现情况而定)

空间优化

DP一般的做法是使用数组(dp[i][j][S])来进行转移;然而在这道题里,暴力开数组是会MLE的!

然而经过观察,在整个状态空间里面实际用到的状态数并不多,因此我们可以考虑使用哈希表和队列来维护需要转移的状态(有BFS那味了)。鉴于这里不是ACM,调标准库的unordered_map/HashMapqueue/Queue不香吗?

由题意,\(n \leq 8\),因此刻画\(S\)最多需要18个二进制位,而\(i\)\(j\)最多分别需要4个二进制位。int范围刚好存的下,这样就可以把这个三元组转换成整数来做哈希了。

需要注意的一点是,状态转移过程中有可能出现多个状态指向一个状态的情形,也就是说一个状态有可能多次入队、进行重复转移!这就需要考虑到DP的核心——记忆化搜索了。同样地,由于无法开数组来标记入队信息,可以使用unordered_set/HashSet来记录已入队的状态,从而规避重复入队的情况。

接下来只需要像一只码农一样快乐coding就好啦!祝各位dalao早日AC!(逃)