基于连通性状态压缩的动态规划问题.docx

基于连通性状态压缩的动态规划问题.docx

《基于连通性状态压缩的动态规划问题.docx》由会员分享，可在线阅读，更多相关《基于连通性状态压缩的动态规划问题.docx（33页珍藏版）》请在冰点文库上搜索。

基于连通性状态压缩的动态规划问题

基于连通性状态压缩的动态规划问题

长沙市雅礼中学陈丹琦

【摘要】

基于状态压缩的动态规划问题是一类以集合信息为状态且状态总数为指数级的特殊的动态规划问题.在状态压缩的基础上，有一类问题的状态中必须要记录若干个元素的连通情况，我们称这样的问题为基于连通性状态压缩的动态规划问题，本文着重对这类问题的解法及优化进行探讨和研究•

本文主要从动态规划的几个步骤一一划分阶段，确立状态，状态转移以及程序实现来介绍这类问题的一般解法，会特别针对到目前为止信息学竞赛中涌现出来的几类题型的解法作一个探讨.结合例题，本文还会介绍作者在减少状态总数和降低转移开销两个方面对这类问题优化的一些心得.

【关键词】

状态压缩连通性括号表示法轮廓线插头棋盘模型

【目录】

【序言】3

【正文】5

1.问题的一般解法5

【例1】Formula15

问题描述5

算法分析5

小结11

2.一类简单路径问题12

【例2】Formula215

问题描述15

算法分析15

小结16

3.一类棋盘染色问题17

【例3】Black&White17

问题描述17

算法分析17

小结19

4.一类基于非棋盘模型的问题20

【例4】生成树计数20

问题描述20

算法分析20

小结21

5.一类最优性问题的剪枝技巧22

【例5】RocketMania22

问题描述22

算法分析23

小结25

6.总结25

【参考文献】26

【感谢】26

【附录】26

【序言】

先看一个非常经典的问题旅行商问题（即TSP问题，TravelingSalesman

Problem）：

—个n（W5）个点的带权完全图，求权和最小的经过每个点恰好一次的封闭回路.这个问题已经被证明是NP完全问题，那么对于这样一类无多项式算法的问题，搜索算法是不是解决问题的唯一途径呢？

答案是否定的•不难发

现任何时候我们只需要知道哪些点已经被遍历过而遍历点的具体顺序对以后的决策是没有影响的，因此不妨以当前所在的位置i，遍历过的点的集合S为状态

作动态规划：

f（i,S>minfj（寻i{}）dist,（j其中jv>i，i,jinS.

动态规划的时间复杂度为0（2n*n2），虽然为指数级算法，但是对于n=15的数据规模来说已经比朴素的0（n!

）的搜索算法高效很多了•我们通常把这样一

类以一个集合内的元素信息作为状态且状态总数为指数级别的动态规划称为基于状态压缩的动态规划或集合动态规划•基于状态压缩的动态规划问题通常具

有以下两个特点：

1•数据规模的某一维或几维非常小；2•它需要具备动态规

划问题的两个基本性质：

最优性原理和无后效性.

一般的状态压缩问题，压缩的是一个小范围内每个元素的决策，状态中元素的信息相对独立.而有些问题，仅仅记录每个元素的决策是不够的，不妨再看一个例子：

给你一个m*n（m,nWJ）的矩阵，每个格子有一个价值，要求找一个连通块使得该连通块内所有格子的价值之和最大•按从上到下的顺序依次考虑每个格子选还是不选，下图为一个极端情况，其中黑色的格子为所选的连通块•只考虑前5行的时候，所有的黑色格子形成了三个连通块，而最后所

有的黑色格子形成一个连通块•如果状态中只单纯地记录前一行或前几行的格子选还是不选，是无法准确描述这个状态的，因此压缩的状态中我们需要增加一维，记录若干个格子之间的连通情况•我们把这一类必须要在状态中记录若干个元素之间的连通信息的问题称为基于连通性状态压缩的动态规划问题.本文着重对这类问题进行研究.

连通是图论中一个非常重要的概念，在一个无向图中，如果两个顶点之间存在一条路径，则称这两个点连通.而基于连通性状态压缩的动态规划问题与图论模型有着密切的关联，比如后文涉及到的哈密尔顿回路、生成树等等.通常这类问题的本身与连通性有关或者隐藏着连通信息.

全文共有六个章节.

第一章，问题的一般解法，介绍解决基于连通性状态压缩的动态规划问题的一般思路和解题技巧；

第二章，一类简单路径问题，介绍一类基于棋盘模型的简单路径问题的状态表示的改进括号表示法以及提出广义的括号表示法；

第三章，一类棋盘染色问题，介绍解决一类棋盘染色问题的一般思路；第四章，一类基于非棋盘模型的问题，介绍解决一类非棋盘模型的连通性状态压缩问题的一般思路；

第五章，一类最优性问题的剪枝技巧，本章的重点是优化，探讨如何通过剪枝来减少扩展的状态的总数从而提高算法的效率；

第六章，总结，回顾前文，总结解题方法.

【正文】一•问题的一般解法

基于连通性状态压缩的动态规划问题通常具有一个比较固定的模式，几乎所有的题目都是在这个模式的基础上变形和扩展的.本章选取了一个有代表性的例题来介绍这一类问题的一般解法.

【例1】Formula1

问题描述

给你一个m*n的棋盘，有的格子是障碍，问共有多少条回路使得经过每个非障碍格子恰好一次.m,n<12.

算法分析

【戈U分阶段】这是一个典型的基于棋盘模型的问题，棋盘模型的特殊结

构，使得它成为连通性状态压缩动态规划问题最常见的“舞台”.通常来说，棋

盘模型有三种划分阶段的方法：

逐行，逐列，逐格.顾名思义，逐行即从上到下或从下到上依次考虑每一行的状态，并转移到下一行；逐列即从左到右或从右到左依次考虑每一列的状态，并转移到下一列；逐格即按一定的顺序（如从上

到下，从左到右）依次考虑每一格的状态，并转移到下一个格子.

对于本题来说，逐行递推和逐列递推基本类似,接下来我们会对逐行递推和逐格递推的状态确立，状态转移以及程序实现一一介绍.

【确立状态】先提出一个非常重要的概念一一“插头”对于一个4连通的问题来说，它通常有上下左右4个插头，一个方向的插头存在表示这个格子在这个方向可以与外面相连•本题要求回路的个数，观察可以发现所有的非障碍格子一定是从一个格子进来，另一个格子出去，即4个插头恰好有2个插

头存在，共6种情况.

逐行递推不妨按照从上到下的顺序依次考虑每一行.分析第i行的哪些信息对第i+1行有影响：

我们需要记录第i行的每个格子是否有下插头，这决定了第i+1行的每个格子是否有上插头.仅仅记录插头是否存在是不够的，可能导致出现多个回路（如右图），而本题要求一个回路，也就隐含着最后所有的非障碍格子通过插头连接成了一个连通块，因此还需要记录第i行的n个格子的连通情况.

连通性：

（3,4）连通性：

（1,2）（3,4）连通性：

（1,2,3,4）

我们称图中的蓝线为轮廓线，任何时候只有轮廓线上方与其直接相连的格

子和插头才会对轮廓线以下的格子产生直接的影响.通过上面的分析，可以写出动态规划的状态：

f（i,So,SJ表示前i行，第i行的n个格子是否具有下插头的一个n位的二进制数为So，第i行的n个格子之间的连通性为S的方案总数.

如何表示n个格子的连通性呢？

通常给每一个格子标记一个正数，属于同一个的连通块的格子标记相同的数.比如｛1,1,2,2｝和｛2,2,1,1｝都表示第1,2个格子

属于一个连通块，第3,4个格子属于一个连通块.为了避免出现同一个连通信息有不同的表示，一般会使用最小表示法.

一种最小表示法为：

所有的障碍格子标记为0，第一个非障碍格子以及与它

连通的所有格子标记为1,然后再找第一个未标记的非障碍格子以及与它连通的格子标记为2，……，重复这个过程，直到所有的格子都标记完毕.比如连通信息（（1,2,5）,（3,6）,（4））表示为｛1,1,2,3,1,2｝.还有一种最小表示法，即一个连通块内所有的格子都标记成该连通块最左边格子的列编号，比如上面这个例子，我们表

示为{1,1,3,4,1,3}.两种表示方法在转移的时候略有不同，本文后面将会提到5.如

上图三个状态我们可以依次表示为f（1,（0011）2,{0,0,1,1}）,

f（2,（1111）2,{1,1,2,2}）,f（3,（1001）2,{1,1,1,1）.

状态表示的优化通过观察可以发现如果轮廓线上方的n个格子中某个格子

没有下插头，那么它就不会再与轮廓线以下的格子直接相连，它的连通性对轮廓线以下的格子不会再有影响，也就成为了“冗余”信息.不妨将记录格子的连通性改成记录插头的连通性，如果这个插头存在，那么就标记这个插头对应的格子的连通标号，如果这个插头不存在，那么标记为0.这样状态就从

f（i,S0,3）精简为f（i,S），上图三个状态表示为f（1,{0,0,1,1}），f（2,{1,1,2,2}），

f（3,{1,0,0,1}）.

优化后不仅状态表示更加简单，而且状态总数将会大大减少.

逐格递推按照从上到下，从左到右的顺序依次考虑每一格.分析转移完（i,j）

这个格子后哪些信息对后面的决策有影响：

同样我们可以刻画出轮廓线，即轮廓线上方是已决策格子，下方是未决策格子.由图可知与轮廓线直接相连的格子有n个，直接相连的插头有n+1个，包括n个格子的下插头以及（i,j）的右插头.为了保持轮廓线的“连贯性”，不妨从左到右依次给n个格子标号，n+1个插头标号.类似地，我们需要记录与轮廓线直接相连的n+1个插头是否存在以及n个格子的连通情况.

通过上面的分析，很容易写出动态规划的状态：

f（i,j,S°,S）表示当前转移

完（i,j）这个格子，n+1个插头是否存在表示成一个n+1位的二进制数So，以及n个格子的连通性为S1的方案总数.

f（3,1,（10111）2,{1,1,2,2}）f（3,2,（10111）2,{1,1,2,2}）f（3,3,（10001）2,{1,1,1,1）

逐行递推的时候我们提到了状态的优化，同样地，我们也可以把格子的连通性记录在插头上，新的状态为f（i,j,S），上图3个状态依次为

f（3,1,{1,0,1,2,2}），f（3,2,{1,0,1,2,2}），f（3,3,{1,0,0,0,1}）.

【转移状态】

状态的转移开销主要包含两个方面：

每个状态转移的状态数，计算新的状态的时间.

逐行递推假设从第i行转移到第i+1行，我们需要枚举第i+1行的每个格子的状态（共6种情况），对于任何一个非障碍格子，它是否有上插头和左插头已知，因此最多只有2种情况，状态的转移数Pn.

枚举完第i+1行每个格子的状态后，需要计算第i+1行n个格子之间的连通性的最小表示，通常可以使用并查集的Father数组对其重新标号或者重新执行

一次BFS/DFS，时间复杂度为O（n），最后将格子的连通性转移到插头的连通性上.

特别需要注意的是在转移的过程中，为了避免出现多个连通块，除了最后一行，任何时候一个连通分量内至少有一个格子有下插头.

逐格递推仔细观察下面这个图，当f（i,j-1,S）转移到f（i,j,S'）时，轮廓

线上n个格子只有（i-1,j）被改成（i,j）,n+1个插头只有2个插头被改动，即（i,j-1）的右插头修改成（i,j）的下插头和（i-1,j）的下插头修改成（i,j）的右插头.转移的时候枚举（i,j）的状态分情况讨论.一般棋盘模型的逐格递推转移有3类情况：

新建

一个连通分量，合并两个连通分量，以及保持原来的连通分量.下面针对本题进行分析：

的两个插头连通且不与其它插头连通，这种情况下需要将这两个插头连通分量标号标记成一个未标记过的正数，重新O（n）扫描保证新的状态满足最小表示.

情况2合并两个连通分量，这种情况出现在（i,j）有上插头和左插头•如果两个插头不连通，那么将两个插头所处的连通分量合并，标记相同的连通块标号，O（n）扫描保证最小表示；如果已经连通，相当于出现了一个回路，这种情况只能出现在最后一个非障碍格子.

情况3保持原来的连通分量，这种情况出现在（i,j）的上插头和左插头恰好有一个，下插头和右插头也恰好有一个•下插头或右插头相当于是左插头或上插头的延续，连通块标号相同，并且不会影响到其他的插头的连通块标号，计算新的状态的时间为0

（1）.

注意当从一行的最后一个格子转移到下一行的第一个格子的时候，轮廓线需要特殊处理•值得一提的是，上面三种情况计算新的状态的时间分别为O（n）,

O（n）,0

（1），如果使用前面提到的第二种最小表示方法，情况1只需要0

（1），但

是情况3可能需要O（n）重新扫描.

比较一下逐行递推和逐格递推的状态的转移，逐行递推的每一个转移的状态总数为指数级，而逐格递推为0

（1），每次计算新的状态的时间两者最坏情况都为0（n），但是逐行递推的常数要比逐格递推大，从转移开销这个角度来看，逐格递推的优势是毋庸置疑的.

【程序实现】

逐行递推和逐格递推的程序实现基本一致，下面以逐格递推为例来说明.首先必须解决的一个问题是，对于像f（3,2,{1,0,1,2,2}）这样的一个状态我们该如何存储，可以开一个长度为n+1的数组来存取n+1个插头的连通性，但是数组判重并不方便，而且空间较大•不妨将n+1个元素进行编码，用一个或几个整数

来存储，当我们需要取一个状态出来对它进行修改的时候再进行解码.

编码最简单的方法就是表示成一个n+1位的p进制数，p可以取能够达到的最大的连通块标号加1,对本题来说，最多出现_n/2<6个连通块，不妨取p=7•在不会超过数据类型的范围的前提下，建议将p改成2的幕，因为位运算比

普通的运算要快很多，本题最好采用8进制来存储.

如需大范围修改连通块标号，最好将状态0（n）解码到一个数组中，修改后再0（n）计算出新的p进制数，而对于只需要局部修改几个标号的情况下，可以直接用（xdivpi-1）modp来获取第i位的状态，用-k*直接对第i位进行修改.

最后我们探讨一下实现的方法，一般有两种方法：

1•对所有可能出现的状态进行编码，枚举编码方式：

预处理将所有可能的连通性状态搜索出来，依次编号1,2,3,…,Tot,那么状态为f（i,j,k）表示转移完（i,j）后轮廓线状态编号为k的方案总数•将所有状态存入Hash表中，使得每个状态与编号一一对应，程序框架如下：

Forij1tom

Forjj1ton

Forkj1toTot

Forxj（i,j,State[k]）的所有转移后的状态

k'j状态x的编号

f（ij,k）「f（i,j,k）f（i,j,k），（i,j）为（i,j）的后继格子.

EndFor

2•记忆化宽度优先搜索：

将初始状态放入队列中，每次取队首元素进行扩展，并用Hash对扩展出来的新的状态判重.程序框架如下：

Queue.Push（所有初始状态）

WhilenotEmpty（Queue）

pjQueue.Pop（）

Forxjp的所有转移后的状态

Ifx之前扩展过Then

Sum[x]jSum[x]+Sum[p]

Else

Queue.Push（x）

Sum[x]jSum[p]

EndIf

EndFor

EndWhile

比较上述两种实现方法，直接编码的方法实现简单，结构清晰，但是有一个很大的缺点：

无效状态可能很多，导致了很多次空循环，而大大影响了程序的效率.下面是一组实验的比较数据：

表1.直接编码与宽度优先搜索扩展状态总数比较

测试数据

宽度优先搜索扩展状态总数

直接编码

Tot

Tot*m*n

无效状态比率

m=9,n=9（1,1）为障碍

30930

2188

177228

82.5%

m=10,n=

10

无障碍

134011

5798

579800

76.8%

m=11,n=11

（1,1）为障碍

333264

15511

1876831

82.2%

m=12,n=

12

无障碍

1333113

41835

6024240

77.9%

可以看出直接编码扩展的无效状态的比率非常高，对于障碍较多的棋盘其对比更加明显，因此通常来说宽度优先搜索扩展比直接编码实现效率要高.

Hash判重的优化：

使用一个HashSize较小的Hash表，每转移一个（i,j）清空一次，每次判断状态x是否扩展过的程序效率比用一个HashSize较大的Hash表每次判断状态（i,j,x）高很多•类似地，在不需要记录路径的情况下，也可以使用滚动的扩展队列来代替一个大的扩展队列.

最后我们比较一下，不同的实现方法对程序效率的影响：

Program1:

8-Based枚举编码方式.

Program2:

8-Based队列扩展，HashSize=3999997

Program3:

8-Based队列扩展，HashSize=4001,Hash表每次清空.

Program4:

7-Based队列扩展，HashSize=4001,Hash表每次清空.

表2.不同的实现方法的程序效率的比较

测试数据

Program1

Program2

Program3

Program4

m=10,n=10

无障碍棋盘

46ms

31ms

15ms

31ms

m=11,n=11

（1,1）为障碍

140ms

499ms

109ms

187ms

m=12,n=12

无障碍

624ms

1840ms

499ms

873ms

小结

本章从划分阶段，确立状态，状态转移以及程序实现四个方面介绍了基于连通性状态压缩动态规划问题的一般解法，并在每个方面归纳了一些不同的方法，最后对不同的算法的效率进行比较.在平时的解题过程中我们要学会针对题目的特点和数据规模“对症下药”，选择最合适的方法而达到最好的效果.

由于逐格递推的转移开销比逐行递推小很多，下文如果不作特殊说明，我们都采用逐格的阶段划分.

2.一类简单路径问题

这一章我们会针对一类基于棋盘模型的简单回路和简单路径问题的解法作一个探讨•简单路径，即除了起点和终点可能相同外，其余顶点均不相同的路径，而简单回路为起点和终点相同的简单路径.Formula1是一个典型的棋盘模

型的简单回路问题，这一章我们继续以这个题为例来说明.

首先我们分析一下简单回路问题有什么特点:

仔细观察上面的图，可以发现轮廓线上方是由若干条互不相交的路径构成的，而每条路径的两个端口恰好对应了轮廓线上的两个插头！

一条路径上的所有

格子对应的是一个连通块，而每条路径的两个端口对应的两个插头是连通的而且不与其他任何一个插头连通.

在上一章我们提到了逐格递推转移的时候的三种情况：

新建一个连通分量，合并两个连通分量，保持原来的连通分量，它们分别等价于两个插头成为了一条新的路径的两端，两条路径的两个端口连接起来形成一条更长的路径或一条路径的两个端口连接起来形成一个回路以及延长原来的路径.

通过上面的分析我们知道了简单回路问题一定满足任何时候轮廓线上每一

个连通分量恰好有2个插头，那么这些插头之间有什么性质呢？

【性质】轮廓线上从左到右4个插头a,b,c,d,如果a,c连通，并且与b不连通，那么b,d一定不连通.

证明：

反证法，如果a,c连通，b,d连通，那么轮廓线上方一定至少存在一条a到c的路径和一条b到d

t-%宅

的路径•如图，两条路径一定会有交点，不妨设两条路•

径相交于格子P，那么P既与a,c连通，又与b,d连通，cd可以推出a,c与b,d连通，矛盾，得证.

这个性质对所有的棋盘模型的问题都适用.

“两两匹配”，“不会交叉”这样的性质，我们很容易联想到括号匹配•将轮廓线上每一个连通分量中左边那个插头标记为左括号，右边那个插头标记为右括号，由于插头之间不会交叉，那么左括号一定可以与右括号一一对应•这样我们就可以使用3进制一一0表示无插头，1表示左括号插头，2表示右括号插头记录下所有的轮廓线信息•不妨用#表示无插头，那么上面的三幅图分别对应的是（（））#（），（（）#）（），（（）###），即（1122012）3,（1120212）3,（1120002）3，我们称这种状态的表示方法为括号表示法.

依然分三类情况来讨论状态的转移：

为了叙述方便，不妨称（i,j-1）的右插头为p，（i-1,j）的下插头为q，（i,j）的下插头为p，右插头为q•，那么每次转移相当于轮廓线上插头p的信息修改成p的信息，插头q的信息修改成q•的信息，设W（x）=0,1,2表示插头x的状态.

情况1新建一个连通分量，这种情况下W（p）=0，W（q）=0，p，q•两个插头构建了一条新的路径，相当于p为左括号，q为右括号，即W（p）-1,

W（q）—2,计算新的状态的时间为0

（1）.

情况2合并两个连通分量，这种情况下W（p）>0，W（q）>0，W（p）-0，W（q）-0,根据p,q为左括号还是右括号分四类情况讨论：

情况2.1W（p）=1，W（q）=1•那么需要将q这个左括号与之对应的右括号v修改成左括号，即W（v）—1.

情况2.2W（p）=2，W（q）=2•那么需要将p这个右括号与之对应的左括号v修改成右括号，即W（v）-2.

仃q

情况2.1图情况2.2图

情况2.3W（p）=1，W（q）=2，那么p和q是相对应的左括号和右括号，连接p,q相当于将一条路径的两端连接起来形成一个回路，这种情况下只能出现在最后一个非障碍格子.

情况2.4W（p）=2，W（q）=1，那么p和q连接起来后，p对应的左括号和q对应的右括号恰好匹配，不需要修改其他的插头的状态.

情况2.1,2.2需要计算某个左括号或右括号与之匹配的括号，这个时候需要对三进制状态解码，利用类似模拟栈的方法•因此情况2.1,2.2计算新的状态的

时间复杂度为O（n），2.3,2.4时间复杂度为0

（1）.

情况3保持原来的连通分量，W（p）,W（q）中恰好一个为0,W（p）,W（q）中也恰好一个为0•那么无论p，q•中哪个插头存在，都相当于是p,q中那个存在的插头的延续，括号性质一样，因此W（p）-W（p）+W（q），W（q）J0或者W（q）JW（p）+W（q），W（p）-0•计算新的状态的时间复杂度为0

（1）.

通过上面的分析可以看出，括号表示法利用了简单回路问题的“一个连通分量内只有2个插头”的特殊性质巧妙地用3进制状态存储下完整的连通信息，插头的连通性标号相对独立，不再需要通过O（n）扫描大范围修改连通性标号.实现的时候，我们可以用4进制代替3进制而提高程序运算效率，下面对最小表示法与括号表示法的程序效率进行比较：

表3.不同的状态表示的程序效率的比较

测试数据

最小表示法

7Based

最小表示法

8Based

括号表示法

3Based

括号表示法

4Based

m=10,n=10

无障碍棋盘

31ms

15ms