算法设计与分析_课程报告.pdf-资料库

85c74812-e97f-4a18-b1a7-b1fd95b6392c.pdf-第1页.png

第1页 / 共8页

85c74812-e97f-4a18-b1a7-b1fd95b6392c.pdf-第2页.png

第2页 / 共8页

85c74812-e97f-4a18-b1a7-b1fd95b6392c.pdf-第3页.png

第3页 / 共8页

85c74812-e97f-4a18-b1a7-b1fd95b6392c.pdf-第4页.png

第4页 / 共8页

85c74812-e97f-4a18-b1a7-b1fd95b6392c.pdf-第5页.png

第5页 / 共8页

85c74812-e97f-4a18-b1a7-b1fd95b6392c.pdf-第6页.png

第6页 / 共8页

85c74812-e97f-4a18-b1a7-b1fd95b6392c.pdf-第7页.png

第7页 / 共8页

85c74812-e97f-4a18-b1a7-b1fd95b6392c.pdf-第8页.png

第8页 / 共8页

学号：201526703032 姓名：晏夏伟 17-18-1 算法（2）班《算法设计与分析》课程论文 ——对动态规划算法的实例评述注：本部分保留，供老师打分使用。教师评语：  算法介绍  例题解答过程  开放性应用算法和算法与应用相关性  卷面格式  是（）否（）有抄袭或被抄袭。 /10 /30 /30 /10 总分： 0

学号：201526703032 姓名：晏夏伟 17-18-1 算法（2）班一. 简述该算法的基本理论、特点算法，无非是解决某个问题的方式方法或者说思想，而在计算机编程当中，而动态规划，是一种通过“大事化小”的思路解决问题的算法，其目的是解决一些有某种特征的复杂问题，其主要思想是将一个规模比较大的复杂问题分解为若干个简单的子问题并依次求解，而大问题的解可通过其子问题的结果得到。此方法有点类似于递归的算法（递归的概念及思想在此不做赘述）。然而每次都只解决一个子问题，并将其解决方案存储起来，如果计算过程中再次发现同样的子问题，不必重复求解，而是直接查找之前的解决方案，从而减少计算次数达到节省时间即降低时间复杂度。例如： Fabonacci 数列问题的动态规划解决方案： Fn=F(n- 1)+F(n-2)，其定义的基本子问题是 F(1)=F(2)=1。若求 F(100)，将 F(100) 分解为若干子问题，即 F(100)=F(99)+F(98) ， … ， F(3)=F(2)+(1)，以 F(98)为例，假定已计算出 F(98)，并将 F(98)的结果保留起来，所以当最后一步求解 F(100)的时候，需要 F(99)求解，递推到 F(98)的时候不用再次求解 F(98)，只需要查找之前得到的解即可。其特点主要有：  该类算法问题必须有一个出口即边界值与递归类似  下一个阶段的解需要依赖于上一个子阶段的结果  子问题已其母问题本质是一样的，与递归类似  相比递归减少计算次数从而降低了时间复杂度，节省了时间  但因要存储子问题的解而牺牲了部分存储空间（但在如今硬件发展也极快的情况下好像显得没有时间那么宝贵）二. 给出该题的求解过程（可拍照插图）本算法实例是《算法设计与分析_习题二》中的求两个基因序列的最长公共子序列。为避免篇幅过长，具体题目在此就不列出，以下是该题的分析与求解过程。如果这个问题使用暴力穷举，列出所有的子序列再进行匹配的话，这将有 2n 个子序列，那么解决这个问题的时间复杂度将是指 1

学号：201526703032 姓名：晏夏伟 17-18-1 算法（2）班数级的，一般不太可取。而如果使用所以要解决此问题，我们先分析此问题的特征。首先，我们先定义输入的两个基因序列的长度分别为 a 和 b 的两个一维数组 X[0,..,a-1] 和 Y[0,..,b-1] 。然后令 Length(X[0,..,a- 1]),Y[0,..,b-1])为两个基因序列的最长公共子序列的长度,Max(a,b)为 a 和 b 比较取其中较大的值。取该问题中序列前四个和前五个字符做列子，由此通过分析我们不难发现：  如果这两个序列的最后一个符号相等即(X[a-1]==Y[b-1])，则最长公共子序列的长度为 Length(X[0,..,a-1]),Y[0,..,b-1])= Length(X[0,..,a-2]),Y[0,..,b-2])+1 。例如： Length(ACAA, TATA)= Length(ACA, TAT)+1。  如果这两个序列的最后一个符号不相等即(X[a-1]！=Y[b-1])，则最长公共子序列的长度为 Length(X[0,..,a-1]),Y[0,..,b- 1])=Max(Length(X[0,..,a-2]),Y[0,..,b-1]),Length(X[0,..,a-1]),Y[0,..,b- 2])) 。例如： L(ACAAG, TATAA)=Max(L(ACAA, TATAA), L(ACAAG, TATA))。然而，如果单纯的用递归来实现上面的描述如下图 2-1：在递归的过程中，很多子问题比如 L(ACA,TATA)被重复执行了两次，而如果全部画出来的话，重复执行的操作就更为恐怖了，时间复杂度在最差的情况下即所有字符都不匹配的情况下为 O(2n)。图 2-1 递归树 2

学号：201526703032 姓名：晏夏伟 17-18-1 算法（2）班所以运用动态规划的思想，我们需要用一个数组来记录中间结果，避免重复计算，将每次的到的结果用数组保存起来。其伪代码描述如下： Descroptions:Longest Common Subsequence Input:X=(X1,X2,X3,...Xa); Y=(Y1,Y2,Y3,...,Yb); L[a,b];P[i][j] Init:L[a,b]==0; Function LCS(C) { L[a+1][b+1]=0;i=1;j=1; FOR i TO M FOR j TO N IF i EQUAL TO 0 AND J ENUQL TO 0 L[i][j]=0; ELSE IF X[i-1] EQUAL TO Y[j-1] L[i][j]=L[i-1][j-1]+1; P[i][j]=1; ElSE L[i][j]=MAX(L[i-1][j],L[i][j-1]); P[i][j]=2 OR P[i][j]=3; ENDIF ENDFOR ENDFOR } Output:L[a][b] 3

学号：201526703032 姓名：晏夏伟 17-18-1 算法（2）班现在我们来看下问题具体求解过程，而因为不只要求出最大长度，还要找到公共最长子序列，如果想要直接找到最长公共子序列的中间结果应该是不可能的，所以我们需要借助最长公共子序列的长度矩阵来，利用上述定义，用 L[i][j]来表示最长公共子序列的长度，以段落一和段落二的前六个序列为例来画出长度矩阵图 2-2。 j T A T A A A i 0 0 0 0 0 0 0 A C A A G A 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 2 2 2 图 2-2 长度矩阵 0 0 1 1 2 3 3 0 0 1 1 2 3 3 0 0 1 1 2 3 4 所以在填表 L[i][j]过程中，再填一个表 P[i][j]来表示当前的 L[i][j]的值是由哪一个子问题来得到的，  若 Xi 等于 Yj，设置 P[i][j] = 1；  若 Xi 不等于 Yj，并且 L[i - 1][j] >=L[i][j ]，设置 P[i][j] =2；  若 Xi 不等于 Yj，并且 L[i][j] < L[i][j + 1]，设置 P[i][j] = 3；将 P 画出来所以可以得到一个矩阵，避免画在上图 2-2 中看不清，我重画一个矩阵用来表示前序矩阵如图 2-3 i 0 0 0 0 0 0 0 j T A T A A A A C A A G A 0 0 1 2 1 1 1 0 0 3 2 3 3 2 0 0 1 2 1 1 1 0 0 1 2 1 1 1 0 0 3 2 2 1 2 0 0 1 2 1 1 1 图 2-3 前序矩阵 4

学号：201526703032 姓名：晏夏伟 17-18-1 算法（2）班如图 2-2 所示，绿色标注的路径为前序路径，再如图 2-3，用黄色标注的部分为最长公共子序列，所以两个段落的用于举例基因序列的前六个符号的最长公共子序列为 AAAA。同理，推广到两个基因段落的全部序列，此方法同样适用。最后再分析一下此算法的时间复杂度，由于每次调用向上或向左（或向上向左同时）移动一步，故算法时间复杂度为 O(mn), 这比单纯的递归算法的最坏情况的时间复杂度 O(2n)，最后于我们这里暂且不讨论空间复杂度的问题，虽消耗了一部分的内存用于存储中间数组，但无疑大大降低了计算时间，相比之下也无疑优化了很多！三. 介绍该算法的个人理解，可应用领域，如何应用在之前未修过算法设计与分析这个门课以前，在大一大二的学习过程中，碰到一些问题也是一知半解，到大三做项目的时候，深感算法对于程序的重要性，就像对于递归这个概念，以前对的理解只是知道循环调用它本身，然而对于动态规划这个概念，只闻其名而不知其所以然。通过最近的学习，也算有了一个自己大概的理解。对于这个算法最深的体验也不是这个算法可以解决什么 Fibonacci 等编程问题，它更像由生活中一步步解决简单的问题从而完成一个很大的目标，而运用这种生活思维，从而有了动态规划这个算法，并且这重思维还可以运用到除了编程以外的其他很多领域，由此我认为，算法本身不是最重要的，最重要的还是需要人思考动态规划相关原理及思想在解决实际问题中的优势与不足，并且提升自己的思维能力。当然，这里还是要回归这个算法本身，来谈一谈此算法的一下的应用领域，关于上面的问题，我们已经知道其可以用在生物学领域，应用于 DNA 序列比对，基因预测等。并由此最长公共子序列问题，很容易联系到文本匹配，文本检索，语音识别等等。并由文本的匹配问题，我想到了近年来的大学生毕业论文甚至是学术界等的抄袭事件频频发生如图 3-1[1]，给整个教育环境以及学术界的声誉造成了很大的影响。也许可以利用动态规划思想以及最长公共子序列的实例可以设计出一个论文查重的算法。 5

学号：201526703032 姓名：晏夏伟 17-18-1 算法（2）班图 3-1 安徽大学曝论文抄袭所以基于此问题，通过该算法检测文本的相识度，完全可以提供一个检测论文等等是否有抄袭文本和重复文本的重要依据，然而对于文本的相似度的判定，匹配的方法就是求两个序列的公共长度和公共序列，从而比较文本的相似性。其相关原理以及方法，详见上文，在此不再赘述！由此可见，基于动态规划和最长公共子序列的论文查重，如果有很大数据的支持下，可以应用在检测大学生提交的报告或毕业论文以及学生界的论文的抄袭现象上，将提交的报告或论文进行检测，为论文查重提供一个有力的方法。 6

学号：201526703032 姓名：晏夏伟 17-18-1 算法（2）班参考资料： [1] Tank.安徽大学曝论文抄袭除一个单词外其他一字不差 http://xinxi.51offer.com/xinxi/html/2016/jynews_0322/286588.html， 2016-03-22/2017-12-24. 7

资料库

算法设计与分析_课程报告.pdf

相关推荐

课程资源

热门标签

最新资料