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

1、基于连接状态压缩的动态编程问题长沙市阿礼中学诊断值摘要基于状态压缩的动态计划问题是以集合信息为状态、状态总数呈指数级的特殊动态计划问题。基于状态压缩，需要记录某些元素的连接状态的问题。我们把这些问题称为基于连接状态压缩的动态规划问题，本文重点讨论和研究这种问题的解决方法和优化。本文主要在动态计划的几个阶段分割阶段建立状态、状态转移和程序实现，介绍了这些问题的一般解法，并具体讨论了迄今为止在信息学竞赛中出现的几种类型的问题型解法关键字状态压缩连接括号表示轮廓插接板型号。目录序言 3正文 5一.问题的一般解决办法5示例1formula 15问题说明5算法分析5摘要11二.简单路径问题的种类12示例

2、2fomula 215问题说明15算法分析15摘要16三.板染色问题的种类17示例3黑色白色17问题说明17算法分析17摘要19四。基于郑智薰棋盘模型的问题20示例4生成树数量20问题说明20算法分析20摘要21V.一类优化问题的修剪技术22示例5洛克特狂热22问题说明22算法分析22摘要25六。摘要26参考资料 27谢谢 27附录 27序言首先，非常经典的问题旅行上的问题(TSP问题，Traveling sales man Problem):n(15)答案是“否”。任何时候我们只要知道某一点已经通过，遍历点的具体顺序不会影响以后的决定，就可以将当前所在位置I，通过的点的集合S作为状态进行动态

3、计划。(莎士比亚，北方快车)。，其中Ji，I，j in S .动态编程的时间复杂性是金志洙级算法，但是对于n=15的数据大小，它已经比简单的搜索算法有效得多了。我们通常将此类集合中的元素信息视为状态，状态总和为金志洙级别的动态计划称为基于状态压缩的动态计划或集合动态计划。基于状态压缩的动态计划问题通常为1 .具有数据大小的一维或几维非常小的两个特征2。需要动态编程问题的两个基本特性：优化原理和非效用。一般状态压缩问题，压缩是小范围内每个元素的决定，状态内元素的信息相对独立。有些问题仅记录每个因素的决定是不够的。我再举一个例子。我再给你看一个m * n (m，n9)的矩阵。每个格子都有价值。必须

4、找到连接的块，最大限度地提高连接的块内所有网格的价值。没有从上到下或选择每个检查选择，下图是极端情况。其中黑色网格是选定的连接块。仅考虑前5行时，所有黑色网格形成3个连接块，最后所有黑色网格形成一个连接块。如果状态仅记录前几行或前几行。(阿尔伯特爱因斯坦，Northern Exposure(美国电视剧)，连接)不能准确地说明状态，因此在压缩状态下，我们必须增加一维度，记录多个网格之间的连接状态。我们把这种类型的几个因素之间的连接信息记录在状态中的问题称为基于连接状态压缩的动态计划问题。这篇文章着重讨论这种问题。连接是图论中一个非常重要的概念。在无方向图中，如果两个顶点之间存在路径，则称为两个点

5、连接在一起。基于连接状态压缩的动态规划问题与图论模型密切相关。例如，与后门相关的汉密尔顿循环、生成树等。通常，这些问题本身与连接性有关，或隐藏连接信息。全文共六章。第一章，问题的一般解法介绍了解决基于连接状态压缩的动态规划问题的一般思维和故障诊断技术。第二章，介绍了简单路径问题、基于板模型的简单路径问题的状态表示的改进括号表示和广义括号表示。第三章，介绍解决棋盘染色问题、棋盘染色问题的一般思维方式。第四章，介绍了基于非雨坝板模型的问题，解决非雨坝板模型连接状态压缩问题的一般思维方式。第五章，优化问题的修剪技巧，本章的重点是探讨通过修剪减少扩展状态的总数提高算法效率的方法。第六章，摘要，前期回顾

6、，问题解决方法摘要。正文一.问题的一般解决办法基于连接状态压缩的动态编程问题通常具有相对固定的模式，几乎所有主题都基于此模式变形和扩展。本章选择了代表性的例子，介绍了这类问题的一般解法。示例1 formula1 ural 1519，timus top coders :第三方挑战问题说明我给你一个M * n的棋盘。有些格子是障碍物。确保总共有几个循环正确地通过每个非物理晶格一次。m，N12。如图所示，m=n=4，(1，1)，(1，2)是障碍物，共有2个符合要求的电路。算法分析分割阶段这是典型的基于板模型的问题，板模型的特殊结构，成为连接状态压缩动态计划问题最常见的“阶段”。通常，电路板模型有三种

7、阶段划分方法：按行、按列、按网格。顾名思义，逐行从上到下或从下到上考虑。按列从左到右或从右到左移动到下一列，考虑每列的状态。格式按特定顺序(例如从上到下，从左到右)依次考虑每个格的状态，然后移到下一格。在这个问题上，标题与逐行递归和逐列递归几乎相似，逐行递归和逐列递归的状态表明了本文稍后将讨论的Rocket Mania等巨大差异。(莎士比亚，北方快车)。接下来，我们将确立逐行递归和格式递归的状态，并一一介绍状态转移及程序实现。设置状态首先提出一个非常重要的概念3354“插头”。4对于连接问题，通常有上下左右四个插头，一个方向的插头存在，表示可以在这个方向与外部连接。这个问题要求循环的数量，可以

8、观察到所有的非物理晶格必须从一个格子进来，从另一个格子出去。(阿尔伯特爱因斯坦，Northern Exposure)可以按行递归地从上到下依次考虑每件事。行。分析行I中的哪些信息影响行I 1。必须记录I行的每个栏是否有插头。确定I 1行的每个格子是否有插头。只记录插入是否有头是不够的，可能会发生多个电路(例如右侧)图)，这个问题需要循环。也就是说，由于最后所有无障碍的晶格通过插头连接到一个连接块，因此还必须记录I行中N个晶格的连接。插头：0011插头：1111插头：1001从左到右，0表示没有插头，1表示有插头连接性：(3，4)连接性：(1，2) (3，4)连接性：(1，2，3，4)括号中的数

9、字表示网格列号，括号中的网格属于连接的块我们把图中的蓝线称为轮廓，只有直接连接在轮廓上的格子和插头才能直接影响轮廓下的格子。通过以上分析，您可以写入动态计划的状态。第一行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)，

10、即连接块内的所有网格都显示为连接块最左侧网格的列号。例如，在上例中，我们标记为1，1，3，4，1，3.上图中的三种状态依次为、状态表示法的优化不再直接连接到轮廓下方的网格(如果轮廓上方N个网格中的任何一个网格没有插头)，并且该连接不再影响轮廓下方的网格。这将是“重复”信息。您可以将记录格点的连接变更为记录插头的连接性。如果存在此插头，则显示与此插头对应的光栅的连接标签。优化后，状态表达将更简单，状态的总数也将大大减少。按网格递归顺序从上到下从左到右依次考虑每个域。分析传输完成(I，j)后，分析哪些信息影响后面的决定。同样，轮廓线上方是决策层格点，下方是未决格点。如图所示，直接连接到轮廓的栅格为

11、N个，直接连接的插头为N个，插头为N个J)的右侧插头。要保持轮廓的“一致性”，可以从左到右给定N个检查标签，N个插头标签。同样，必须记录轮廓是否有一个直接连接的N个插头，以及N个检查连接状态。通过以上分析，可以很容易地编写动态计划状态，它表示当前转换完成(I，j)晶格，是否存在二进制S0(其中N个插头用n 1位表示)，以及N个晶格用S1连接的方案总数。逐行递归时，我们提到了状态的优化。同样，我们也可以把晶格的连接性记录在插头上。新状态按上述图3状态的顺序排列，过渡状态状态的变换开销主要由两个方面组成：每个状态变换的状态数，计算新状态的时间。从逐行递归假设I行到I 1行，我们需要列出I 1行中每

12、个栏的状态(共6种情况)，对于任何非极性栏，是否知道上插头和左插头，列出I 1行中的每个晶格状态后，必须计算I 1行N个晶格之间的最小连接表示。通常，您可以使用并行检查集的Father数组重新编号或重新运行BFS/DFS。时间复杂度为O(n)，最后，可以将晶格的连接转移到插头的连接性。特别要注意，除了最后一行外，一次在一个连接元件内有一个或多个网格向下插头，这样在前面的过程中就不会出现多个连接块。按网格递归地仔细观察下图，在传输时勾勒出轮廓。联机n个网格将仅(i-1，j)更改为(I，j)，n个插头将仅更改2个插头。即，(I，j-1)的右插头与(I，j)的下插头和(I-；Condition IC

13、ondition IIICondition II情况1创建具有(I，j)右插头和下插头的新连接元件。新创建的两个插头连接在一起，而不是连接到其他插头。在这种情况下，必须将两个插头连接元件标签标记为未标记的正数，并再次进行O(n)扫描以确保新状态满足最小表示法。实例2将具有(I，j)上插头和左侧插头的两个连接元件组合在一起。如果两个插头未连接，则具有两个插头的连接元件将合并，以显示相同的连接块标签。O(n)扫描可确保最小表示。如果已经连接，就等于发生了循环。这种情况只能发生在最后的非脾脏物晶格上。情况3保留原始连接组件。(I，j)的顶部插头和左侧插头正好有一个，底部插头和右侧插头也正好有一个。底

14、部插头或右侧插头与左侧插头或顶部插头的顺序相同，连接块标签相同，并且不影响其他插头的连接块标签。计算新状态的时间为O (1)。从一行的最后一个网格移动到下一行的第一个网格时，轮廓需要特殊处理。在上述三种情况下，计算新状态的时间分别为O(n)、O(n)、O(1)，使用前面提到的第二种最小显示方法时，案例1仅需要O如果比较逐行递归和逐格递归状态的转换，则逐行递归的每个转换的状态总数为指数级，格式递归的状态总数为O(1)，每次计算新状态时，最差的情况为O(n)，但从逐行递归的常数大于每格递归的常数，从以前开销的角度来看，每格递归的优点是毋庸置疑的。程序实施行递归和格式递归程序的实现基本一致。下面以格式递归为例说明。首先要解决的一个问题是，对于这种状态，我们应该如何存储，打开