基于连通性状态压缩的动态规划问题Word格式文档下载.docx

1、【例4】生成树计数 20问题描述 20算法分析 20小结 215.一类最优性问题的剪枝技巧 22【例 5】Rocket Mania 22问题描述 22算法分析 23小结 256.总结 25【参考文献】 26【感谢】 26【附录】 26【序言】先看一个非常经典的问题 旅行商问题（即TSP问题，Traveling SalesmanProblem）： 个n（W5）个点的带权完全图，求权和最小的经过每个点恰好一次 的封闭回路.这个问题已经被证明是NP完全问题，那么对于这样一类无多项式 算法的问题，搜索算法是不是解决问题的唯一途径呢 ？答案是否定的不难发现任何时候我们只需要知道哪些点已经被遍历过而遍历点

2、的具体顺序对以后的 决策是没有影响的，因此不妨以当前所在的位置 i，遍历过的点的集合S为状态作动态规划：f（ i, S minf j（寻 i）dist,（j其中 jvi，i, j in S.动态规划的时间复杂度为0（2n* n2），虽然为指数级算法，但是对于 n = 15 的数据规模来说已经比朴素的 0（n!）的搜索算法高效很多了我们通常把这样一类以一个集合内的元素信息作为状态且状态总数为指数级别的动态规划称为基 于状态压缩的动态规划或集合动态规划基于状态压缩的动态规划问题通常具有以下两个特点：1数据规模的某一维或几维非常小； 2它需要具备动态规划问题的两个基本性质：最优性原理和无后效性.一般

3、的状态压缩问题，压缩的是一个小范围内每个元素的决策，状态中元 素的信息相对独立.而有些问题，仅仅记录每个元素的决策是不够的，不妨再 看一个例子：给你一个 m * n （m, nWJ）的矩阵，每个格子有一个价值，要求 找一个连通块使得该连通块内所有格子的价值之和最大按从上到下的顺序依 次考虑每个格子选还是不选，下图为一个极端情况，其中黑色的格子为所选的 连通块只考虑前5行的时候，所有的黑色格子形成了三个连通块，而最后所有的黑色格子形成一个连通块如果状态中只单纯地 记录前一行或前几行的格子选还是不选，是无法准确 描述这个状态的，因此压缩的状态中我们需要增加一 维，记录若干个格子之间的连通情况我们把

4、这一类 必须要在状态中记录若干个元素之间的连通信息的问 题称为基于连通性状态压缩的动态规划问题.本文着 重对这类问题进行研究.连通是图论中一个非常重要的概念，在一个无向图中，如果两个顶点之间 存在一条路径，则称这两个点连通.而基于连通性状态压缩的动态规划问题与 图论模型有着密切的关联，比如后文涉及到的哈密尔顿回路、生成树等等.通 常这类问题的本身与连通性有关或者隐藏着连通信息.全文共有六个章节.第一章，问题的一般解法，介绍解决基于连通性状态压缩的动态规划问题 的一般思路和解题技巧；第二章，一类简单路径问题，介绍一类基于棋盘模型的简单路径问题的状 态表示的改进 括号表示法以及提出广义的括号表示法

5、；第三章，一类棋盘染色问题，介绍解决一类棋盘染色问题的一般思路； 第四章，一类基于非棋盘模型的问题，介绍解决一类非棋盘模型的连通性 状态压缩问题的一般思路；第五章，一类最优性问题的剪枝技巧，本章的重点是优化，探讨如何通过 剪枝来减少扩展的状态的总数从而提高算法的效率；第六章，总结，回顾前文，总结解题方法.【正文】一 问题的一般解法基于连通性状态压缩的动态规划问题通常具有一个比较固定的模式，几乎 所有的题目都是在这个模式的基础上变形和扩展的.本章选取了一个有代表性 的例题来介绍这一类问题的一般解法.【例 1】Formula 1 问题描述给你一个m *n的棋盘，有的格子是障碍，问共有多少条回路使得

6、经过每个 非障碍格子恰好一次.m, n 12.算法分析【戈U分阶段】 这是一个典型的基于棋盘模型的问题，棋盘模型的特殊结构，使得它成为连通性状态压缩动态规划问题最常见的“舞台” .通常来说，棋盘模型有三种划分阶段的方法：逐行，逐列，逐格.顾名思义，逐行即从上到 下或从下到上依次考虑每一行的状态，并转移到下一行；逐列即从左到右或从 右到左依次考虑每一列的状态，并转移到下一列；逐格即按一定的顺序 （如从上到下，从左到右）依次考虑每一格的状态，并转移到下一 个格子.对于本题来说，逐行递推和逐列递推基本类似,接 下来我们会对逐行递推和逐格递推的状态确立，状态转 移以及程序实现一一介绍.【确立状态】 先

7、提出一个非常重要的概念一一“插头”对于一个4连 通的问题来说，它通常有上下左右 4个插头，一个方向的插头存在表示这个格 子在这个方向可以与外面相连本题要求回路的个数，观察可以发现所有的非 障碍格子一定是从一个格子进来，另一个格子出去，即 4个插头恰好有2个插头存在，共6种情况.逐行递推不妨按照从上到下的顺序依次考虑每 一行.分析第i行的哪些信息对第i + 1行有影响： 我们需要记录第i行的每个格子是否有下插头，这决 定了第i+1行的每个格子是否有上插头.仅仅记录插 头是否存在是不够的，可能导致出现多个回路（如右 图），而本题要求一个回路，也就隐含着最后所有的非障碍格子通过插头连接成 了一个连通

8、块，因此还需要记录第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个格子属于一

9、个连通块.为了避免出现同一个连通信息 有不同的表示，一般会使用最小表示法.一种最小表示法为：所有的障碍格子标记为 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

10、,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）.优化后不仅状态

11、表示更加简单，而且状态总数将会大大减少.逐格递推 按照从上到下，从左到右的顺序依次考虑每一格.分析转移完（i, j）这个格子后哪些信息对后面的决策有影 响：同样我们可以刻画出轮廓线，即轮廓 线上方是已决策格子，下方是未决策格 子.由图可知与轮廓线直接相连的格子有 n个，直接相连的插头有n+1个，包括n 个格子的下插头以及（i, j）的右插头.为了 保持轮廓线的“连贯性”，不妨从左到右依 次给n个格子标号，n+1个插头标号.类似地，我们需要记录与轮廓线直接相连 的n+1个插头是否存在以及n个格子的连通情况.通过上面的分析，很容易写出动态规划的状态： f（i,j,S,S）表示当前转移完（i, j）

12、这个格子，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行转移到

13、第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）时，轮廓线上

14、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）有上插头和左插头如果 两个插头不连通，那么将两

15、个插头所处的连通分量合并，标记相同的连通块标 号，O（n）扫描保证最小表示；如果已经连通，相当于出现了一个回路，这种情 况只能出现在最后一个非障碍格子.情况3保持原来的连通分量，这种情况出现在（i, j）的上插头和左插头恰好 有一个，下插头和右插头也恰好有一个下插头或右插头相当于是左插头或上 插头的延续，连通块标号相同，并且不会影响到其他的插头的连通块标号，计 算新的状态的时间为0（1）.注意当从一行的最后一个格子转移到下一行的第一个格子的时候，轮廓线 需要特殊处理值得一提的是，上面三种情况计算新的状态的时间分别为 O（n）,O（n）, 0（1），如果使用前面提到的第二种最小表示方法，情况 1

16、只需要0（1），但是情况3可能需要O（n）重新扫描.比较一下逐行递推和逐格递推的状态的转移，逐行递推的每一个转移的状 态总数为指数级，而逐格递推为 0（1），每次计算新的状态的时间两者最坏情况 都为0（n），但是逐行递推的常数要比逐格递推大，从转移开销这个角度来看， 逐格递推的优势是毋庸置疑的.【程序实现】逐行递推和逐格递推的程序实现基本一致，下面以逐格递推为例来说明.首 先必须解决的一个问题是，对于像f（3,2,1,0,1,2,2）这样的一个状态我们该如何 存储，可以开一个长度为n+1的数组来存取n+1个插头的连通性，但是数组判 重并不方便，而且空间较大不妨将 n+1个元素进行编码，用一个或

17、几个整数来存储，当我们需要取一个状态出来对它进行修改的时候再进行解码.编码最简单的方法就是表示成一个 n+1位的p进制数，p可以取能够达到的 最大的连通块标号加1,对本题来说，最多出现_n/2 0，W（q） 0，W（p ） - 0， W（q） - 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情况 2.1 图 情况 2.2 图情况2.3 W（

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

19、, W（q ） 中也恰好一个为0 那么无论p，q 中哪个插头存在，都相当于是 p, q中那个 存在的插头的延续，括号性质一样，因此 W（p ） - W（p） + W（q），W（q ） J 0或 者W（q） J W（p） + W（q），W（p） - 0 计算新的状态的时间复杂度为 0（1）.通过上面的分析可以看出，括号表示法利用了简单回路问题的“一个连通 分量内只有2个插头”的特殊性质巧妙地用 3进制状态存储下完整的连通信息， 插头的连通性标号相对独立，不再需要通过O（n）扫描大范围修改连通性标号.实 现的时候，我们可以用4进制代替3进制而提高程序运算效率，下面对最小表 示法与括号表示法的程序效率进行比较：表3.不同的状态表示的程序效率的比较最小表示法7Based8Based括号表示法3Based4Based