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

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。

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

长沙市雅礼中学 陈丹琦

【摘要】
基于状态压缩的动态规划问题是一类以集合信息为状态且状态总数为指数级的特殊的动态规划问题．在状态压缩的基础上, 有一类问题的状态中必须要记录若干个元素的连通情况, 我们称这样的问题为基于连通性状态压缩的动态规划问题, 本文着重对这类问题的解法及优化进行探讨和研究．
本文主要从动态规划的几个步骤——划分阶段, 确立状态, 状态转移以及程序实现来介绍这类问题的一般解法, 会特别针对到当前为止信息学竞赛中涌现出来的几类题型的解法作一个探讨．结合例题, 本文还会介绍作者在减少状态总数和降低转移开销两个方面对这类问题优化的一些心得．

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

【目录】
【序言】 3
【正文】 5
一. 问题的一般解法 5
【例1】Formula 1 5
问题描述 5
算法分析 5
小结 11
二. 一类简单路径问题 12
【例2】Formula 2 15
问题描述 15
算法分析 15
小结 16
三. 一类棋盘染色问题 17
【例3】Black & White 17
问题描述 17
算法分析 17
小结 19
四. 一类基于非棋盘模型的问题 20
【例4】生成树计数 20
问题描述 20
算法分析 20
小结 21
五. 一类最优性问题的剪枝技巧 22
【例5】Rocket Mania 22
问题描述 22
算法分析 22
小结 25
六.总结 26
【参考文献】 27
【感谢】 27
【附录】 27

【序言】
先看一个非常经典的问题——旅行商问题(即TSP问题, Traveling Salesman Problem): 一个n(≤15)个点的带权完全图, 求权和最小的经过每个点恰好一次的封闭回路．这个问题已经被证明是NP完全问题, 那么对于这样一类无多项式算法的问题, 搜索算法是不是解决问题的唯一途径呢? 答案是否定的．不难发现任何时候我们只需要知道哪些点已经被遍历过而遍历点的具体顺序对以后的决策是没有影响的, 因此不妨以当前所在的位置i, 遍历过的点的集合S为状态作动态规划:
, 其中j<>i, i, j in S．
动态规划的时间复杂度为, 虽然为指数级算法, 可是对于n = 15的数据规模来说已经比朴素的的搜索算法高效很多了．我们一般把这样一类以一个集合内的元素信息作为状态且状态总数为指数级别的动态规划称为基于状态压缩的动态规划或集合动态规划．基于状态压缩的动态规划问题一般具有以下两个特点: 1．数据规模的某一维或几维非常小; 2．它需要具备动态规划问题的两个基本性质: 最优性原理和无后效性．
一般的状态压缩问题, 压缩的是一个小范围内每个元素的决策, 状态中元素的信息相对独立．而有些问题, 仅仅记录每个元素的决策是不够的, 不妨再看一个例子: 给你一个m * n (m, n≤9) 的矩阵, 每个格子有一个价值, 要求找一个连通块使得该连通块内所有格子的价值之和最大．按从上到下的顺序依次考虑每个格子选还是不选, 下图为一个极端情况, 其中黑色的格子为所选的连通块．只考虑前5行的时候, 所有的黑色格子形成了三个连通块, 而最后所有的黑色格子形成一个连通块．如果状态中只单纯地记录前一行或前几行的格子选还是不选, 是无法准确描述这个状态的, 因此压缩的状态中我们需要增加一维, 记录若干个格子之间的连通情况．我们把这一类必须要在状态中记录若干个元素之间的连通信息的问题称为基于连通性状态压缩的动态规划问题．本文着重对这类问题进行研究．
连通是图论中一个非常重要的概念, 在一个无向图中, 如果两个顶点之间存在一条路径, 则称这两个点连通．而基于连通性状态压缩的动态规划问题与图论模型有着密切的关联, 比如后文涉及到的哈密尔顿回路、 生成树等等．一般这类问题的本身与连通性有关或者隐藏着连通信息．
全文共有六个章节．
第一章, 问题的一般解法, 介绍解决基于连通性状态压缩的动态规划问题的一般思路和解题技巧;
第二章, 一类简单路径问题, 介绍一类基于棋盘模型的简单路径问题的状态表示的改进——括号表示法以及提出广义的括号表示法;
第三章, 一类棋盘染色问题, 介绍解决一类棋盘染色问题的一般思路;
第四章, 一类基于非棋盘模型的问题, 介绍解决一类非棋盘模型的连通性状态压缩问题的一般思路;
第五章, 一类最优性问题的剪枝技巧, 本章的重点是优化, 探讨如何经过剪枝来减少扩展的状态的总数从而提高算法的效率;
第六章, 总结, 回顾前文, 总结解题方法．

【正文】
一. 问题的一般解法
基于连通性状态压缩的动态规划问题一般具有一个比较固定的模式, 几乎所有的题目都是在这个模式的基础上变形和扩展的．本章选取了一个有代表性的例题来介绍这一类问题的一般解法．
【例1】Formula 1 Ural1519, Timus Top Coders : Third Challenge

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

如图, m = n = 4, (1, 1), (1, 2)是障碍, 共有2条满足要求的回路．
算法分析
【划分阶段】 这是一个典型的基于棋盘模型的问题, 棋盘模型的特殊结构, 使得它成为连通性状态压缩动态规划问题最常见的”舞台”．一般来说, 棋盘模型有三种划分阶段的方法: 逐行, 逐列, 逐格．顾名思义, 逐行即从上到下或从下到上依次考虑每一行的状态, 并转移到下一行; 逐列即从左到右或从右到左依次考虑每一列的状态, 并转移到下一列; 逐格即按一定的顺序(如从上到下, 从左到右)依次考虑每一格的状态, 并转移到下一个格子．
对于本题来说, 逐行递推和逐列递推基本类似 有的题目, 逐行递推和逐列递推的状态表示有较大的区别, 比如本文后面会讲到的Rocket Mania一题
, 接下来我们会对逐行递推和逐格递推的状态确立, 状态转移以及程序实现一一介绍．
【确立状态】 先提出一个非常重要的概念——”插头”．对于一个4连通的问题来说, 它一般有上下左右4个插头, 一个方向的插头存在表示这个格子在这个方向能够与外面相连．本题要求回路的个数, 观察能够发现所有的非障碍格子一定是从一个格子进来, 另一个格子出去, 即4个插头恰好有2个插头存在, 共6种情况．
逐行递推 不妨按照从上到下的顺序依次考虑每
一行．分析第i 行的哪些信息对第i + 1行有影响:
我们需要记录第i行的每个格子是否有下插头, 这决
定了第i+1行的每个格子是否有上插头．仅仅记录插
头是否存在是不够的, 可能导致出现多个回路 (如右
图), 而本题要求一个回路, 也就隐含着最后所有的非障碍格子经过插头连接成了一个连通块, 因此还需要记录第i行的n个格子的连通情况．

插头: 0011 插头: 1111 插头: 1001 从左到右, 0表示无插头, 1表示有插头

连通性: (3,4) 连通性: (1,2) (3,4) 连通性: (1,2,3,4) 括号内的数表示的是格子的列编号, 一个括号内的格子属于一个连通块

我们称图中的蓝线为轮廓线, 任何时候只有轮廓线上方与其直接相连的格子和插头才会对轮廓线以下的格子产生直接的影响．经过上面的分析, 能够写出动态规划的状态: 表示前i行, 第i行的n个格子是否具有下插头的一个n位的二进制数为, 第i行的n个格子之间的连通性为的方案总数．
如何表示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}．两种表示方法在转移的时候略有不同, 本文后面将会提到因为第一种表示法更加直观, 本文如果不作特殊说明, 默认使用第一种最小表示法
．如上图三个状态我们能够依次表示为, , ．
状态表示的优化 经过观察能够发现如果轮廓线上方的n个格子中某个格子没有下插头, 那么它就不会再与轮廓线以下的格子直接相连, 它的连通性对轮廓线以下的格子不会再有影响, 也就成为了”冗余”信息．不妨将记录格子的连通性改成记录插头的连通性, 如果这个插头存在, 那么就标记这个插头对应的格子的连通标号, 如果这个插头不存在, 那么标记为0．这样状态就从精简为, 上图三个状态表示为, , ．
优化后不但状态表示更加简单, 而且状态总数将会大大减少．
逐格递推 按照从上到下, 从左到右的顺序依次考虑每一格．分析转移完(i, j)这个格子后哪些信息对后面的决策有影响: 同样我们能够刻画出轮廓线, 即轮廓线上方是已决策格子, 下方是未决策格子．由图可知与轮廓线直接相连的格子有n个, 直接相连的插头有n+1个, 包括n个格子的下插头以及(i, j)的右插头．为了保持轮廓线的”连贯性”, 不妨从左到右依次给n个格子标号, n+1个插头标号．类似地, 我们需要记录与轮廓线直接相连的n+1个插头是否存在以及n个格子的连通情况．　　　　　　　　　　
经过上面的分析, 很容易写出动态规划的状态: 表示当前转移完(i, j)这个格子, n+1个插头是否存在表示成一个n+1位的二进制数S0, 以及n个格子的连通性为S1的方案总数．

逐行递推的时候我们提到了状态的优化, 同样地, 我们也能够把格子的连通性记录在插头上, 新的状态为, 上图3个状态依次为, , ．

【转移状态】
状态的转移开销主要包含两个方面: 每个状态转移的状态数, 计算新的状态的时间．
逐行递推　假设从第i行转移到第i+1行, 我们需要枚举第i+1行的每个格子的状态(共6种情况), 对于任何一个非障碍格子, 它是否有上插头和左插头已知, 因此最多只有2种情况, 状态的转移数≤2n．
枚举完第i+1行每个格子的状态后, 需要计算第i+1行n个格子之间的连通性的最小表示, 一般能够使用并查集的Father数组对其重新标号或者重新执行一次BFS/DFS, 时间复杂度为O(n), 最后将格子的连通性转移到插头的连通性上．
特别需要注意的是在转移的过程中, 为了避免出现多个连通块, 除了最后一行, 任何时候一个连通分量内至少有一个格子有下插头．
逐格递推　仔细观察下面这个图, 当转移到时, 轮廓

线上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 III
Condition II

情况1 新建一个连通分量, 这种情况出现在(i, j)有右插头和下插头．新建的两个插头连通且不与其它插头连通, 这种情况下需要将这两个插头连通分量标号标记成一个未标记过的正数, 重新O(n)扫描保证新的状态满足最小表示．
情况2 合并两个连通分量, 这种情况出现在(i, j)有上插头和左插头．如果两个插头不连通, 那么将两个插头所处的连通分量合并, 标记相同的连通块标号, O(n)扫描保证最小表示; 如果已经连通, 相当于出现了一个回路, 这种情况只能出现在最后一个非障碍格子．
情况3 保持原来的连通分量, 这种情况出现在(i, j)的上插头和左插头恰好有一个, 下插头和右插头也恰好有一个．下插头或右插头相当于是左插头或上插头的延续, 连通块标号相同, 而且不会影响到其它的插头的连通块标号, 计算新的状态的时间为O(1)．
注意当从一行的最后一个格子转移到下一行的第一个格子的时候, 轮廓线需要特殊处理．值得一提的是, 上面三种情况计算新的状态的时间分别为O(n), O(n), O(1), 如果使用前面提到的第二种最小表示方法, 情况1只需要O(1), 可是情况3可能需要O(n)重新扫描．
比较一下逐行递推和逐格递推的状态的转移, 逐行递推的每一个转移的状态总数为指数级, 而逐格递推为O(1), 每次计算新的状态的时间两者最坏情况都为O(n), 可是逐行递推的常数要比逐格递推大, 从转移开销这个角度来看, 逐格递推的优势是毋庸置疑的．
【程序实现】
逐行递推和逐格递推的程序实现基本一致, 下面以逐格递推为例来说明．首先必须解决的一个问题是, 对于像这样的一个状态我们该如何存储, 能够开一个长度为n+1的数组来存取n+1个插头的连通性, 可是数组判重并不方便, 而且空间较大．不妨将n+1个元素进行编码, 用一个或几个整数来存储, 当我们需要取一个状态出来对它进行修改的时候再进行解码．
编码最简单的方法就是表示成一个n+1位的p进制数, p能够取能够达到的最大的连通块标号加1 因为还要把0留出来存没有插头的情况
, 对本题来说, 最多出现个连通块, 不妨取p = 7．在不会超过数据类型的范围的前提下, 建议将p改成2的幂, 因为位运算比普通的运算要快很多, 本题最好采用8进制来存储．
如需大范围修改连通块标号, 最好将状态O(n) 解码到一个数组中, 修改后再O(n)计算出新的p进制数, 而对于只需要局部修改几个标号的情况下, 能够直接用(x div pi-1) mod p来获取第i位的状态, 用直接对第i位进行修改．
最后我们探讨一下实现的方法, 一般有两种方法:
1．对所有可能出现的状态进行编码, 枚举编码方式: 预处理将所有可能的
连通性状态搜索出来, 依次编号1, 2, 3, …,Tot, 那么状态为表示转移完(i, j)后轮廓线状态编号为k的方案总数．将所有状态存入Hash表中, 使得每个状态与编号一一对应, 程序框架如下:
For i ← 1 to m
For j ←1 to n
For k ← 1 to Tot
For x ← (i, j, State[k]) 的所有转移后的状态
← 状态x的编号
, 为的后继格子．
End For
2．记忆化宽度优先搜索: 将初始状态放入队列中, 每次取队首元素进行扩展, 并用Hash对扩展出来的新的状态判重．程序框架如下:
Queue.Push(所有初始状态)
While not Empty(Queue)
p ← Queue.Pop()
For x ← p的所有转移后的状态
If x之前扩展过 Then
Sum [x] ← Sum[x] + Sum[p]
Else
Queue.Push(x)
Sum[x] ← Sum[p]
End If
End For
End While

比较上述两种实现方法, 直接编码的方法实现简单, 结构清晰, 可是有一个很大的缺点: 无效状态可能很多, 导致了很多次空循环, 而大大影响了程序的效率．下面是一组实验的比较数据:
表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)高很多．类似地, 在不需要记录路径的情况下, 也能够使用滚动的扩展队列来代替一个大的扩展队列．
最后我们比较一下, 不同的实现方法对程序效率的影响 测试环境: Intel Core2 Duo T7100, 1.8GHz, 1G内存
:
Program 1 : 8-Based, 枚举编码方式．
Program 2 : 8-Based, 队列扩展, HashSize = 3999997．
Program 3 : 8-Based, 队列扩展, HashSize = 4001, Hash表每次清空．
Program 4 : 7-Based, 队列扩展, HashSize = 4001, Hash表每次清空．
表2．不同的实现方法的程序效率的比较
测试数据
Program 1
Program 2
Program 3
Program 4
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
小结
本章从划分阶段, 确立状态, 状态转移以及程序实现四个方面介绍了基于连通性状态压缩动态规划问题的一般解法, 并在每个方面归纳了一些不同的方法, 最后对不同的算法的效率进行比较．在平时的解题过程中我们要学会针对题目的特点和数据规模”对症下药”, 选择最合适的方法而达到最好的效果．
由于逐格递推的转移开销比逐行递推小很多, 下文如果不作特殊说明, 我们都采用逐格的阶段划分．

二. 一类简单路径问题
这一章我们会针对一类基于棋盘模型的简单回路和简单路径问题的解法作一个探讨．简单路径, 即除了起点和终点可能相同外, 其余顶点均不相同的路径, 而简单回路为起点和终点相同的简单路径．Formula 1是一个典型的棋盘模型的简单回路问题, 这一章我们继续以这个题为例来说明．
首先我们分析一下简单回路问题有什么特点:

仔细观察上面的图, 能够发现轮廓线上方是由若干条互不相交的路径构成的, 而每条路径的两个端口恰好对应了轮廓线上的两个插头! 一条路径上的所有格子对应的是一个连通块, 而每条路径的两个端口对应的两个插头是连通的而且不与其它任何一个插头连通．
在上一章我们提到了逐格递推转移的时候的三种情况: 新建一个连通分量, 合并两个连通分量, 保持原来的连通分量, 它们分别等价于两个插头成为了一条新的路径的两端, 两条路径的两个端口连接起来形成一条更长的路径或一条路径的两个端口连接起来形成一个回路以及延长原来的路径．
经过上面的分析我们知道了简单回路问题一定满足任何时候轮廓线上每一个连通分量恰好有2个插头, 那么这些插头之间有什么性质呢?　
【性质】轮廓线上从左到右4个插头a, b, c, d, 如果a, c连通, 而且与b不连通, 那么b, d一定不连通．
d
c
a
b
证明: 反证法, 如果a, c连通, b, d连通, 那么轮廓线上方一定至少存在一条a到c的路径和一条b到d的路径．如图, 两条路径一定会有交点, 不妨设两条路径相交于格子P, 那么P既与a, c连通, 又与b, d连通, 能够推出a, c与b, d连通, 矛盾, 得证．
这个性质对所有的棋盘模型的问题都适用．
”两两匹配”, ”不会交叉”这样的性质, 我们很容易联想到括号匹配．将轮廓线上每一个连通分量中左边那个插头标记为左括号, 右边那个插头标记为右括号, 由于插头之间不会交叉, 那么左括号一定能够与右括号一一对应．这样我们就能够使用3进制——0表示无插头, 1表示左括号插头, 2表示右括号插头记录下所有的轮廓线信息．不妨用#表示无插头, 那么上面的三幅图分别对应的是(())#(), (()#)(), (()###), 即, 我们称这种状态的表示方法为括号表示法．
依然分三类情况来讨论状态的转移:
为了叙述方便, 不妨称(i,j-1)的右插头为p, (i-1, j)的下插头为q, (i, j)的下插头为, 右插头为, 那么每次转移相当于轮廓线上插头p的信息修改成的信息, 插头q的信息修改成的信息, 设W(x) = 0, 1, 2表示插头x的状态．
情况1 新建一个连通分量, 这种情况下W(p) = 0, W(q) = 0, , 两个插头构建了一条新的路径, 相当于为左括号, 为右括号, 即← 1, ← 2, 计算新的状态的时间为O(1)．
情况2 合并两个连通分量, 这种情况下W(p) > 0, W(q) > 0, ← 0, ← 0, 根据p, q为左括号还是右括号分四类情况讨论:
情况2.1 W(p) = 1, W(q) = 1．那么需要将q这个左括号与之对应的右括号v修改成左括号, 即W(v) ← 1．
情况2.2 W(p) = 2, W(q) = 2．那么需要将p这个右括号与之对应的左括号v修改成右括号, 即W(v)← 2．
q
p
v
(

)

情况2.1图
q
p
(

v
)

情况2.2图

情况2.3 W(p) = 1, W(q) = 2, 那么p和q是相对应的左括号和右括号, 连接p, q相当于将一条路径的两端连接起来形成一个回路, 这种情况下只能出现在最后一个非障碍格子．
　情况2.4 W(p) = 2, W(q) = 1, 那么p和q连接起来后, p对应的左括号和q对应的右括号恰好匹配, 不需要修改其它的插头的状态．

p
q
情况2.3图
p
q
(
)
情况2.4图

情况2.1, 2.2需要计算某个左括号或右括号与之匹配的括号, 这个时候需要对三进制状态解码, 利用类似模拟栈的方法．因此情况2.1, 2.2计算新的状态的时间复杂度为O(n), 2.3, 2.4时间复杂度为O(1)．
情况3 保持原来的连通分量, W(p), W(q)中恰好一个为0, , 中也恰好一个为0．那么无论, 中哪个插头存在, 都相当于是p, q中那个存在的插头的延续, 括号性质一样, 因此← W(p) + W(q), ← 0或者← W(p) + W(q), ← 0．计算新的状态的时间复杂度为O(1)．
经过上面的分析能够看出, 括号表示法利用了简单回路问题的”一个连通分量内只有2个插头”的特殊性质巧妙地用3进制状态存储下完整的连通信息, 插头的连通性标号相对独立, 不再需要经过O(n)扫描大范围修改连通性标号．实现的时候, 我们能够用4进制代替3进制而提高程序运算效率, 下面对最小表示法与括号表示法的程序效率进行比较:
表3．不同的状态表示的程序效率的比较
测试数据
最小表示法
7Based
最小表示法 8Based
括号表示法 3Based
括号表示法 4Based
m = 10, n = 10
无障碍棋盘
31ms
15ms
0ms
0ms
m = 11, n = 11
(1,1)为障碍
187ms
109ms
46ms
31ms
m = 12, n = 12
无障碍
873ms
499ms
265ms
140ms
能够看出, 括号表示法的优势非常明显, 加上它的思路清晰自然, 实现也更加简单, 因此对于解决这样一类简单回路问题是非常有价值的．
类似的问题还有: NWERC Pipes, Hnoi Postman, Hnoi Park, 还有一类非回路问题也能够经过棋盘改造后用简单回路问题的方法解决, 比如 POJ 1739 Tony’s Tour: 给一个m * n棋盘, 有的格子是障碍, 要求从左下角走到右下角, 每个格子恰好经过一次, 问方案总数．(m, n ≤ 8)
只需要将棋盘改造一下, 问题就等价于Formula 1了．
.......
#.. 改造成 .#####.
... .##..#.
.......
介绍完简单回路问题的解法, 那么一般的简单路径问题又如何解决呢?
【例2】Formula 2 改编自Formula 1

问题描述
给你一个m * n的棋盘, 有的格子是障碍, 要求从一个非障碍格子出发经过每个非障碍格子恰好一次, 问方案总数．m, n ≤ 10．

如图, 一个2 * 2的无障碍棋盘, 共有4条满足要求的路径．
算法分析
确立状态: 按照从上到下, 从左到右依次考虑每一个格子, 设表示
转移完(i, j)这个格子, 轮廓线状态为S的方案总数．如果用一般的最小表示法, 不但需要记录每个插头的连通情况, 还需要额外记录每个插头是否连接了路径的一端, 状态表示相当复杂．依然从括号表示法这个角度来思考如何来存储轮廓线的状态:
这个问题跟简单回路问题最大的区别为: 不是所有的插头都两两匹配, 有的插头连接的路径的另一端不是一个插头而是整条路径的一端, 我们称这样的插头为独立插头．不妨将原来的3进制状态修改成4进制——0表示无插头, 1表示左括号插头, 2表示右括号插头, 3表示独立插头, 这样我们就能够用4进制完整地记录下轮廓线的信息, 图中状态表示为(1203)4．
状态转移: 依然设(i, j-1)的右插头为p, (i-1, j)的下插头为q, (i, j)的下插头为, 右插头为．部分转移同简单回路问题完全一样, 这里不再赘述, 下面分三类情况讨论与独立插头有关的转移:
情况1 W(p) = 0, W(q) = 0．当前格子可能成为路径的一端, 即右插头或下插头是独立插头, 因此← 3, ← 0或者← 3, ← 0．
情况2 W(p) > 0, W(q) > 0, 那么← 0, ← 0
　　情况2.1 W(p) =3, W(q) = 3, 将插头p和q连接起来就相当于形成了一条完整的路径, 这种情况只能出现在最后一个非障碍格子．
　　情况2.2 W(p) , W(q) 中有一个为3, 如果p为独立插头, 那么无论q是左括号插头还是右括号插头, 与q相匹配的插头v成为了独立插头, 因此,
W(v) ←3．如果q为独立插头, 类似处理．
情况3 W(p) , W(q) 中有一个>0, 即p, q中有一个插头存在．
　　情况3.1 如果这个插头为独立插头, 若在最后一个非障碍格子, 这个插头能够成为路径的一端, 否则能够用右插头或下插头来延续这个独立插头．
　　情况3.2 如果这个插头是左括号或右括号, 那么我们以将这个插头”封住”, 使它成为路径的一端, 需要将这个插头所匹配的另一个插头的状态修改成为独立插头．
情况2.2, 3.2需要计算某个左括号或右括号与之匹配的括号, 计算新的状态的时间复杂度为O(n), 其余情况计算新的状态的时间复杂度为O(1)．
特别需要注意, 任何时候轮廓线上独立插头的个数不能够超过2个．至此问题完整解决, m = n = 10的无障碍棋盘, 扩展的状态总数为3493315, 完全能够承受．
上面两类题目我们用括号表示法取得了很不错的效果, 可是它存在一定的局限性, 即插头必须满足两两匹配．那么对于更加一般的问题, 一个连通分量内出现大于2个插头, 上述的括号表示方法显得束手无策．下面将介绍一种括号表示法的变形, 它能够适用于出现连通块内大于2个插头的问题, 我们称之为广义的括号表示法:
假设一个连通分量从左到右有多个插头, 不妨将最左边的插头标记为”(”, 最右边的插头标记为”)”, 中间的插头全部标记为”)(”, 那么能够匹配的括号对应的插头连通．如果问题中可能出现一个连通分量只有一个插头, 那么这个插头标记为”( )”, 这样插头之间的连通性可用括号序列完整地记录下来, 比如对于一个连通性状态为{1,2,2,3,4,3,2,1}, 我们能够用(-(-)(-(-()-)-)-)记录．
这种广义的括号表示方法需要用4进制甚至5进制存储状态, 而且直接对状态连通性进行修改情况非常多, 最好还是将状态进行解码, 修改后再重新编码．下文我们将会运用广义的括号表示法解决一些具体的问题．
小结
本章针对一类简单路径问题, 提出了一种新的状态表示方法——括号表示法, 最后提出了广义的括号表示方法．相比普通的最小表示法, 括号表示法巧妙地把连通块与括号匹配一一对应, 使得状态更加简单明了, 虽然不会减少扩展的状态总数, 可是转移开销的常数要小很多, 是一个不错的方法．
三. 一类棋盘染色问题
有一类这样的问题——给你一个m * n的棋盘, 要求给每个格子染上一种颜色(共k种颜色), 每种颜色的格子相互连通 (4连通)．本章主要对这类问题的解法进行探讨, 我们从一个例题说起:
【例3】Black & White Source : Uva10572

问题描述
一个m * n的棋盘, 有的格子已经染上黑色或白色, 现在要求将所有的未染色格子染上黑色或白色, 使得满足以下2个限制:
1) 所有的黑色的格子是连通的, 所有的白色格子也是连通的．
2) 不会有一个2 * 2的子矩阵的4个格子的颜色全部相同．
问方案总数．(m, n ≤ 8)
如下图, m = 2, n = 3, 灰色格子为未染色格子, 共有9种染色方案．

算法分析
这是一个典型的棋盘染色问题, 着色规则有:
1) 只有黑白两种颜色, 即k = 2, 而且同色的格子互相连通．
2) 没有同色的2 * 2的格子．
对于简单路径问题来说, 相邻的格子是否连通取决于它们之间的插头是否存在, 状态记录轮廓线上每个插头是否存在以及插头之间的连通性; 而棋盘染色问题相邻的格子是否连通取决于它们的颜色是否相同, 这就需要记录轮廓线上方n个格子的颜色以及格子之间的连通性．
确立状态　设当前转移完Q(i, j)这个格子, 对以后的决策产生影响的信息有: 轮廓线上方n个格子的染色情况以及它们的连通性, 由第2条着色规则”没有同色的2 * 2的格子”可知P(i-1, j)的颜色会影响到(i, j+1)着色, 因此我们还需要额外记录格子的颜色．动态规划的状态为: 表示转移完(i, j), 轮廓线上从左到右n个格子的染色情况为S0 (0 ≤ S0 < 2n), 连通性状态为S1, 格子的颜色为cp(0或1)的方案总数．
状态的精简　如果相邻的2个格子不属于同一个连通块, 那么它们必然不同色, 因此只需要记录(i, 1)和(i-1, j+1)两个格子的颜色, 利用S1就能够推出n个格子的颜色．这个精简不会减少状态的总数, 依然需要一个变量来记录两个格子的颜色, 因此意义并不大, 这里只是提一下．
状态转移　枚举当前格子(i, j)的颜色, 计算新的状态: S0和cp都很容易O(1)计算出来．考虑计算S1: 轮廓线的变化相当于将记录(i-1, j)的连通性改成记录(i, j)的连通性．根据当前格子与上面的格子和左边的格子是否同色分四类情况讨论．应当注意的是如果(i, j)和(i-1, j)不同色, 而且(i-1, j)在轮廓线上为一个单独的一个连通块, 那么(i-1, j)以后都不可能与其它格子连通, 即剩余的格子都必须染上与(i-1, j)相反的颜色, 需要特殊判断．转移的时间复杂度为O(n)．计算新状态的S1程序框架如下:
将前一个状态的S1解码, 连通性存入c[1],c[2],…,c[n]．
If (i, j) 与 (i-1, j) 不同色而且 (i-1, j) 为一个单独的连通块Then
特殊判断
Else
If (i, j) 与 (i-1, j) 和 (i, j-1) 均同色Then
For k ← 1 to n
If c[k] = c[j] Then
c[k] ← c[j-1] // 合并两个连通块
EndIf
Else
If (i, j) 与 (i-1, j) 和 (i, j-1) 均不同色Then
c[j] ← 最大可能出现的连通块标号 // (i, j) 新建一个连通块．
Else
If (i, j) 与 (i, j-1) 同色与 (i-1, j) 不同色 Then
c[j] ← c[j-1] // (i, j) 的连通性标号跟 (i, j-1)相同．
EndIf
EndIf
EndIf
EndIf
对c[] O(n)扫描, 修改成最小表示, 利用c[]编码计算出新的S1．
对于m = n = 8的一个全部未染色的棋盘, 扩展出来的状态总数为122395, 转移需要时间为O(n), 因此总的时间复杂度为O(TotalState * n) = 979160, 运行时间<0.1s．至此问题完整解决．类似能够解决的问题还有 重庆市选拔赛 Rect和IPSC Delicious Cake．
扩展 上面提到的是4连通问题, 如果要求8连通呢?
4连通问题是两个格子至少有一条边重合为连通, 而8连通问题是两个格子至少有一个顶点重合为连通, 因此需要记录所有至少有一个顶点在轮廓线上的格子的连通和染色情况, 即包括(i-1, j)在内的n+1个格子．
一个优化的方向　扩展的状态中无效状态的总数很大程度上决定了算法的效率．比如Black & White中如果出现右图的状态, 那么无论之后如何决策, 都不可能满足