homework-02 一坑到底的最大和联通图

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

你在这个作业中学到了什么? 有什么好的设计值得分享? 感想如何 (太容易 / 太难 / 太无趣)?

我觉得这套题目有点偏难，我不像大牛那样，有很多算法可以选择，我是0算法基础的，所以遇到这题我一个就是想到我一维的应用，我的一维思想不是动态规划，而是通过最大和的特质即：当一段连续的数的总和小于零时这段数一定不会与其他段的数字相连，我们设这段数字为连续A段，然后通过统计A段中当前最大的结尾数字的后几位的和，若大于0则加入到最大序列并更改结尾数字，否则继续搜索下一个数字并继续统计当前借位数字的后几位之和再次运算。这样就能保证能对给定的数组统计出多段类似于A段的最长子连续串，然后比较他们的的大小就可以。而拿到这题之后我的第一个想法就是迪杰斯特拉算法，把整个矩阵看做一张图，通过寻找正数的节点间的最短距离，构建一个相对简单的图，然后在对这个只有在正数节点和路径长度的简单的图进行简单地搜索，但是我之后发先一个致命的问题，就是正数节点之间的相连有可能有一部分重复，即A,B,C为正节点，B到A的最短路径与B到C的最短路径之间可能只有一部分是重复的，但是如果在这种情况下还按照我的算法来算的话就会把这一重复的段，重复计算两次。所以这个方法不行。

我之后苦苦思索纠正这个方法的办法，但是发现可能要把所有的点都当成节点，这种情况下复杂度为(n^4),但是在这之上的讨论极为复杂，而作业又是如此急促，所以万般无奈下只能想做出来的大神请教相对简单的方法。看过大家的讨论后，状态压缩dp或联通状态压缩dp是一个出口。大家好像都说状态压缩dp相对好写也好理解，所以先看状态压缩dp，自己做了几道题，然后对这个算法有了一定的理解，发现这道题用状态压缩来解不错，至少思路相对简单，我一开始的状态压缩dp思想复杂度为(n*4^n),主要是通过第i-1行的状态来从i行的2^n个状态中筛选出存在联通可能的状态，然后对筛选出的状态的纵向进行求最大的运算，纵向的意思就是跟自己比，因为第i-1行的多个状态可能对应第i行的同一个状态，所以state(i,k)(0=<k<2^n)（表示第i行的2^n的状态中的一个）中的每一项都有多种取值，但是肯定要取和最大的嘛，因为就连通性来说第i+1行只与第i行的有关所以这是对于i—1行来说，一定要最大的嘛。然后这样就会有一个递推公式state(i,k)=MAX(state(i-1,j)+sum(i,k),sum(i,k)),sum(i,k)为第i行第k个状态的的值，这样的话最后需要处理的只是，结尾判断整个图的连通性的问题，但是显然这个问题有一个最大的难点就是本题的矩阵最大为32*32，而2^32已经是4GB了，如此再开32个就是128GB，肯定行不通的。

又是在万般无奈下，只能选择状态压缩dp复杂度为2^(mn)的算法，偏暴力的。这个就不细说了。最后的作业交的也是这个，实在很抱歉。

但是，灵光一现，在即将交作业的最后一天，我突然有一个优化复杂度(n*4^n)的算法的方法，记得我之前说过的一维的思想吧，一维的思想是把一个一维数组分成几个单独的块，而这些块有一个特点就是如果其中任意一个块的任意一点连接到最佳图上，则这一个快一定会连接到最佳图上，按照这种思路就可以把这一块当成复杂度(n*4^n)的算法中的2^n种可能中的一种，这样的话会大大减少2^n的个数，其次，可以利用状态压缩dp的思想，可以把一行当成一维数组的一个元素，这样的话这道题跟一位数组的题的区别就是n个数中每一个数有优化了的2^n个选择，然后在顶层的想法就是跟一维数组一样。

代码较长，就不在这里贴了，代码里面有注释，有兴趣就看看吧，不过就是无力的暴力，意义不大。

	Personal Software Process Stages	时间百分比(%)	实际花费的时间 (分钟)	原来估计的时间 (分钟)
Planning	计划	40	400分钟	无
· Estimate	· 估计这个任务需要多少时间，把工作细化并大致排序
Development	开发	58	580分钟	无
· Analysis	· 需求分析 (包括学习新技术)
· Design Spec	· 生成设计文档
· Design Review	· 设计复审 (和同事审核设计文档)
· Coding Standard	· 代码规范 (制定合适的规范)
· Design	· 具体设计
· Coding	· 具体编码
· Code Review	· 代码复审
· Test	· 测试（自我测试，修改代码，提交修改）
Reporting	总结报告	2	1小时	无
Test Report 测试报告
Size Measurement 计算工作量 Postmortem & Improvement Plan 事后总结, 并提出改进

Total	总计	100%	总用时	总估计的用时