1、基于连通性状态压缩的动态规划问题长沙市雅礼中学 陈丹琦【摘要】基于状态压缩的动态规划问题是一类以集合信息为状态且状态总数为指数级的特殊的动态规划问题在状态压缩的基础上，有一类问题的状态中必须要记录若干个元素的连通情况，我们称这样的问题为基于连通性状态压缩的动态规划问题，本文着重对这类问题的解法及优化进行探讨和研究 本文主要从动态规划的几个步骤划分阶段，确立状态，状态转移以及程序实现来介绍这类问题的一般解法，会特别针对到目前为止信息学竞赛中涌现出来的几类题型的解法作一个探讨结合例题，本文还会介绍作者在减少状态总数和降低转移开销两个方面对这类问题优化的一些心得【关键词】 状态压缩 连通性 括号表示
2、法 轮廓线 插头 棋盘模型IOI2008 中国国家集训队论文 长沙市雅礼中学 陈丹琦第 2 页【目录】【序言】 .3【正文】 .5一. 问题的一般解法 .5【例 1】Formula 1 .5问题描述 .5算法分析 .5小结 .11二. 一类简单路径问题 .12【例 2】Formula 2 .15问题描述 .15算法分析 .15小结 .17三. 一类棋盘染色问题 .17【例 3】Black & White .17问题描述 .17算法分析 .18小结 .19四. 一类基于非棋盘模型的问题 .20【例 4】生成树计数 .20问题描述 .20算法分析 .20小结 .21五. 一类最优性问题的剪枝技巧
3、.22【例 5】Rocket Mania .22问题描述 .22算法分析 .22小结 .25六.总结 .25【参考文献】 .26【感谢】 .26【附录】 .26IOI2008 中国国家集训队论文 长沙市雅礼中学 陈丹琦第 3 页【序言】先看一个非常经典的问题旅行商问题(即 TSP 问题，Traveling Salesman Problem)：一个 n(15)个点的带权完全图，求权和最小的经过每个点恰好一次的封闭回路这个问题已经被证明是 NP 完全问题，那么对于这样一类无多项式算法的问题，搜索算法是不是解决问题的唯一途径呢? 答案是否定的不难发现任何时候我们只需要知道哪些点已经被遍历过而遍历点的
4、具体顺序对以后的决策是没有影响的，因此不妨以当前所在的位置 i，遍历过的点的集合 S 为状态作动态规划：，其中 ji，i ，j in S(,)min(,)(,)fiSfjSidstji动态规划的时间复杂度为 ，虽然为指数级算法，但是对于 n = 152*nO的数据规模来说已经比朴素的 的搜索算法高效很多了我们通常把这样一!类以一个集合内的元素信息作为状态且状态总数为指数级别的动态规划称为基于状态压缩的动态规划或集合动态规划基于状态压缩的动态规划问题通常具有以下两个特点：1数据规模的某一维或几维非常小；2它需要具备动态规划问题的两个基本性质：最优性原理和无后效性一般的状态压缩问题，压缩的是一个小
5、范围内每个元素的决策，状态中元素的信息相对独立而有些问题，仅仅记录每个元素的决策是不够的，不妨再看一个例子：给你一个 m * n (m, n9) 的矩阵，每个格子有一个价值 ，要求,ijV找一个连通块使得该连通块内所有格子的价值之和最大按从上到下的顺序依次考虑每个格子选还是不选，下图为一个极端情况，其中黑色的格子为所选的连通块只考虑前 5 行的时候，所有的黑色格子形成了三个连通块，而最后所有的黑色格子形成一个连通块如果状态中只单纯地记录前一行或前几行的格子选还是不选，是无法准确描述这个状态的，因此压缩的状态中我们需要增加一维，记录若干个格子之间的连通情况我们把这一类必须要在状态中记录若干个元素
6、之间的连通信息的问题称为基于连通性状态压缩的动态规划问题本文着重对这类问题进行研究连通是图论中一个非常重要的概念，在一个无向图中，如果两个顶点之间存在一条路径，则称这两个点连通而基于连通性状态压缩的动态规划问题与图论模型有着密切的关联，比如后文涉及到的哈密尔顿回路、生成树等等通常这类问题的本身与连通性有关或者隐藏着连通信息IOI2008 中国国家集训队论文 长沙市雅礼中学 陈丹琦第 4 页全文共有六个章节第一章，问题的一般解法，介绍解决基于连通性状态压缩的动态规划问题的一般思路和解题技巧；第二章，一类简单路径问题，介绍一类基于棋盘模型的简单路径问题的状态表示的改进括号表示法以及提出广义的括号表
7、示法；第三章，一类棋盘染色问题，介绍解决一类棋盘染色问题的一般思路； 第四章，一类基于非棋盘模型的问题，介绍解决一类非棋盘模型的连通性状态压缩问题的一般思路；第五章，一类最优性问题的剪枝技巧，本章的重点是优化，探讨如何通过剪枝来减少扩展的状态的总数从而提高算法的效率；第六章，总结，回顾前文，总结解题方法IOI2008 中国国家集训队论文 长沙市雅礼中学 陈丹琦第 5 页【正文】一. 问题的一般解法基于连通性状态压缩的动态规划问题通常具有一个比较固定的模式，几乎所有的题目都是在这个模式的基础上变形和扩展的本章选取了一个有代表性的例题来介绍这一类问题的一般解法【例 1】Formula 1 1问题描
8、述给你一个 m * n 的棋盘，有的格子是障碍，问共有多少条回路使得经过每个非障碍格子恰好一次m, n 12如图，m = n = 4，(1, 1), (1, 2)是障碍，共有 2 条满足要求的回路算法分析【划分阶段】 这是一个典型的基于 棋盘模型棋盘模型的问题，棋盘模型的特殊结构，使得它成为连通性状态压缩动态规划问题最常见的“舞台” 通常来说，棋盘模型有三种划分阶段的方法：逐行，逐列，逐格顾名思义，逐行即从上到下或从下到上依次考虑每一行的状态，并转移到下一行；逐列即从左到右或从右到左依次考虑每一列的状态，并转移到下一列；逐格即按一定的顺序(如从上到下，从左到右)依次考虑每一格的状态，并转移到下
9、一个格子对于本题来说，逐行递推和逐列递推基本类似 2，接下来我们会对逐行递推和逐格递推的状态确立，状态转移以及程序实现一一介绍1 Ural1519, Timus Top Coders : Third Challenge2 有的题目, 逐行递推和逐列递推的状态表示有较大的区别, 比如本文后面会讲到的 Rocket Mania 一题IOI2008 中国国家集训队论文 长沙市雅礼中学 陈丹琦第 6 页【确立状态】 先提出一个非常重要的概念“插头” 对于一个 4 连通的问题来说，它通常有上下左右 4 个插头，一个方向的插头存在表示这个格子在这个方向可以与外面相连本题要求回路的个数，观察可以发现所有的非
10、障碍格子一定是从一个格子进来，另一个格子出去，即 4 个插头恰好有 2 个插头存在，共 6 种情况逐行递推 不妨按照从上到下的顺序依次考虑每一行分析第 i 行的哪些信息对第 i + 1 行有影响：我们需要记录第 i 行的每个格子是否有下插头，这决定了第 i+1 行的每个格子是否有上插头仅仅记录插头是否存在是不够的，可能导致出现多个回路 (如右图)，而本题要求一个回路，也就隐含着最后所有的非障碍格子通过插头连接成了一个连通块，因此还需要记录第 i 行的 n 个格子的 连通情况连通情况 插头：0011 插头：1111 插头：1001 3连通性：(3,4) 连通性：(1,2) (3,4) 连通性：(
11、1,2,3,4) 4我们称图中的蓝线为轮廓线，任何时候只有轮廓线上方与其直接相连的格子和插头才会对轮廓线以下的格子产生直接的影响通过上面的分析，可以写出动态规划的状态： 表示前 i 行，第 i 行的 n 个格子是否具有下插头01(,)fiS的一个 n 位的二进制数为 ，第 i 行的 n 个格子之间的连通性为 的方案总1S数如何表示 n 个格子的连通性呢? 通常给每一个格子标记一个正数，属于同一个的连通块的格子标记相同的数比如1,1,2,2 和2,2,1,1 都表示第 1,2 个格子属于一个连通块，第 3,4 个格子属于一个连通块为了避免出现同一个连通信息有不同的表示，一般会使用最小表示法一种最
12、小表示法为：所有的障碍格子标记为 0，第一个非障碍格子以及与它连通的所有格子标记为 1，然后再找第一个未标记的非障碍格子以及与它连通的格子标记为 2，重复这个过程，直到所有的格子都标记完毕比如连通信息(1,2,5),(3,6),(4) 表示为1,1,2,3,1,2还有一种最小表示法，即一个连3 从左到右, 0 表示无插头, 1 表示有插头4 括号内的数表示的是格子的列编号, 一个括号内的格子属于一个连通块IOI2008 中国国家集训队论文 长沙市雅礼中学 陈丹琦第 7 页通块内所有的格子都标记成该连通块最左边格子的列编号，比如上面这个例子，我们表示为1,1,3,4,1,3 两种表示方法在转移的
13、时候略有不同，本文后面将会提到 5如上图三个状态我们可以依次表示为 ，2(1,0),1,)f， 2(,1),)f 2(3,10),)f状态表示的优化 通过观察可以发现如果轮廓线上方的 n 个格子中某个格子没有下插头，那么它就不会再与轮廓线以下的格子直接相连，它的连通性对轮廓线以下的格子不会再有影响，也就成为了“冗余”信息不妨将记录格子的连通性改成记录插头的连通性，如果这个插头存在，那么就标记这个插头对应的格子的连通标号，如果这个插头不存在，那么标记为 0这样状态就从精简为 ，上图三个状态表示为 ， ，01(,)fiS(,)fiS(1,)f(2,1)f3,优化后不仅状态表示更加简单，而且状态总数
14、将会大大减少逐格递推 按照从上到下，从左到右的顺序依次考虑每一格分析转移完(i , j)这个格子后哪些信息对后面的决策有影响：同样我们可以刻画出轮廓线，即轮廓线上方是已决策格子，下方是未决策格子由图可知与轮廓线直接相连的格子有n 个，直接相连的插头有 n+1 个，包括 n个格子的下插头以及(i, j)的右插头为了保持轮廓线的“连贯性” ，不妨从左到右依次给 n 个格子标号，n+1 个插头标号类似地，我们需要记录与轮廓线直接相连的 n+1 个插头是否存在以及 n 个格子的连通情况 通过上面的分析，很容易写出动态规划的状态： 表示当前转移01(,)fijS完(i , j)这个格子，n+1 个插头是
15、否存在表示成一个 n+1 位的二进制数 S0，以及n 个格子的连通性为 S1 的方案总数2(3,10),1)f 2(3,10),)f 2(3,10),1)f逐行递推的时候我们提到了状态的优化，同样地，我们也可以把格子的连5因为第一种表示法更加直观, 本文如果不作特殊说明, 默认使用第一种最小表示法IOI2008 中国国家集训队论文 长沙市雅礼中学 陈丹琦第 8 页通性记录在插头上，新的状态为 ，上图 3 个状态依次为(,)fijS， ， (3,10,2)f (3,102f ,10,)f【转移状态】状态的转移开销主要包含两个方面：每个状态转移的状态数，计算新的状态的时间逐行递推 假设从第 i 行
16、转移到第 i+1 行，我们需要枚举第 i+1 行的每个格子的状态( 共 6 种情况) ，对于任何一个非障碍格子，它是否有上插头和左插头已知，因此最多只有 2 种情况，状态的转移数2 n枚举完第 i+1 行每个格子的状态后，需要计算第 i+1 行 n 个格子之间的连通性的最小表示，通常可以使用并查集的 Father 数组对其重新标号或者重新执行一次 BFS/DFS，时间复杂度为 O(n)，最后将格子的连通性转移到插头的连通性上特别需要注意的是在转移的过程中，为了避免出现多个连通块，除了最后一行，任何时候一个连通分量内至少有一个格子有下插头逐格递推 仔细观察下面这个图，当 转移到 时，轮廓(,1)
17、fijS(,)fijS线上 n 个格子只有(i-1, j)被改成( i, j)，n+1 个插头只有 2 个插头被改动，即( i, j-1)的右插头修改成(i, j)的下插头和 (i-1，j)的下插头修改成(i, j)的右插头转移的时候枚举(i, j)的状态分情况讨论一般棋盘模型的逐格递推转移有 3 类情况：新建一个连通分量，合并两个连通分量，以及保持原来的连通分量下面针对本题进行分析：Condition I Condition IIICondition IIIOI2008 中国国家集训队论文 长沙市雅礼中学 陈丹琦第 9 页情况 1 新建一个连通分量，这种情况出现在(i, j)有右插头和下插头
18、新建的两个插头连通且不与其它插头连通，这种情况下需要将这两个插头连通分量标号标记成一个未标记过的正数，重新 O(n)扫描保证新的状态满足最小表示情况 2 合并两个连通分量，这种情况出现在(i, j)有上插头和左插头如果两个插头不连通，那么将两个插头所处的连通分量合并，标记相同的连通块标号，O( n)扫描保证最小表示；如果已经连通，相当于出现了一个回路，这种情况只能出现在最后一个非障碍格子 情况 3 保持原来的连通分量，这种情况出现在(i, j)的上插头和左插头恰好有一个，下插头和右插头也恰好有一个下插头或右插头相当于是左插头或上插头的延续，连通块标号相同，并且不会影响到其他的插头的连通块标号，
19、计算新的状态的时间为 O(1)注意当从一行的最后一个格子转移到下一行的第一个格子的时候，轮廓线需要特殊处理值得一提的是，上面三种情况计算新的状态的时间分别为 O(n), O(n), O(1)，如果使用前面提到的第二种最小表示方法，情况 1 只需要 O(1)，但是情况 3 可能需要 O(n)重新扫描比较一下逐行递推和逐格递推的状态的转移，逐行递推的每一个转移的状态总数为指数级，而逐格递推为 O(1)，每次计算新的状态的时间两者最坏情况都为 O(n)，但是逐行递推的常数要比逐格递推大，从转移开销这个角度来看，逐格递推的优势是毋庸置疑的【程序实现】逐行递推和逐格递推的程序实现基本一致，下面以逐格递推
20、为例来说明首先必须解决的一个问题是，对于像 这样的一个状态我(3,210,)f们该如何存储，可以开一个长度为 n+1 的数组来存取 n+1 个插头的连通性，但是数组判重并不方便，而且空间较大不妨将 n+1 个元素进行编码，用一个或几个整数来存储，当我们需要取一个状态出来对它进行修改的时候再进行解码编码最简单的方法就是表示成一个 n+1 位的 p 进制数，p 可以取能够达到的最大的连通块标号加 16，对本题来说，最多出现 个连通块，不妨取/26np = 7在不会超过数据类型的范围的前提下，建议将 p 改成 2 的幂，因为位运算比普通的运算要快很多，本题最好采用 8 进制来存储如需大范围修改连通块
21、标号，最好将状态 O(n) 解码到一个数组中，修改后再 O(n)计算出新的 p 进制数，而对于只需要局部修改几个标号的情况下，可6 因为还要把 0 留出来存没有插头的情况IOI2008 中国国家集训队论文 长沙市雅礼中学 陈丹琦第 10 页以直接用(x div pi-1) mod p 来获取第 i 位的状态，用 直接对第 i 位进行修1*ikp改最后我们探讨一下实现的方法，一般有两种方法：1对所有可能出现的状态进行编码，枚举编码方式：预处理将所有可能的连通性状态搜索出来，依次编号 1, 2, 3, ,Tot，那么状态为 表示转移完(,)fijk(i, j)后轮廓线状态编号为 k 的方案总数将所
22、有状态存入 Hash 表中，使得每个状态与编号一一对应，程序框架如下：2记忆化宽度优先搜索：将初始状态放入队列中，每次取队首元素进行扩展，并用 Hash 对扩展出来的新的状态判重程序框架如下： 比较上述两种实现方法，直接编码的方法实现简单，结构清晰，但是有一个很大的缺点：无效状态可能很多，导致了很多次空循环，而大大影响了程序的效率下面是一组实验的比较数据：表 1直接编码与宽度优先搜索扩展状态总数比较For i 1 to mFor j 1 to nFor k 1 to TotFor x ( i, j, Statek) 的所有转移后的状态 状态 x 的编号， 为 的后继格子 )(,)(,)ffijfijk(,ij,)ijEnd ForQueue.Push(所有初始状态 ) While not Empty(Queue)p Queue.Pop()For x p 的所有转移后的状态If x 之前扩展过 Then Sum x Sumx + SumpElse Queue.Push(x)Sumx Sum p End IfEnd ForEnd While
