算法设计与分析课程设计

成绩评定表学生姓名班级学号专业课程设计题目编辑距离问题分支限界法0-1背包评语组长签字：成绩日期20年月日课程设计任务书学院专业学生姓名班级学号课程设计题目编辑距离问题分支限界法0-1背包实践教学要求与任务:要求：1．巩固和加深对基本算法的理解和运用，提高综合运用课程知识进行算法设计与分析的能力。2．培养学生自学参考书籍，查阅手册、和文献资料的能力。3．通过实际课程设计，掌握利用动态规划算法、回溯法、分支限界法等算法的基本思想，并能运用这些方法设计算法并编写程序解决实际问题。4．了解与课程有关的知识，能正确解释和分析实验结果。任务：按照算法设计方法和原理，设计算法，编写程序并分析结果，完成如下内容：1.运用动态规划算法求解编辑距离问题。2.运用分支限界算法求解0-1背包问题。工作计划与进度安排:第11周：查阅资料。掌握算法设计思想，进行算法设计。第12周：算法实现，调试程序并进行结果分析。撰写课程设计报告，验收与答辩。指导教师：201年月日专业负责人：201年月日学院教学副院长：201年月日摘要算法设计与分析，其实可以解释为一类优化问题，一般针对可以利用计算机解决的离散型问题的优化。主要目的就是为了解决某一问题而提出各种不同的解决方案，并且要针对具体的问题做细致的空间和时间复杂度分析。所有的算法中，应该尽量选取“好”的算法，这里所说的“好”，首先是正确的，其次是所选算法解决问题的效率要尽可能的高。计算机计算时间的长短以及所用空间的大小，跟算法有直接关系，用来衡量算法好坏的两个重要标准就是就是时间和空间复杂度，所以提出好的解决方案，其算法是重中之重。动态规划算法是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。首先找出最优解的性质，并刻其结构特征，然后递归的定义最优值（写出动态规划方程）并且以自底向上的方式计算出最优值，最后根据计算最优值时得到的信息，构造一个最优解。分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。分支限界法的搜索策略是，在扩展结点处，先生成其所有的儿子结点(分支)，然后再从当前的活结点表中选择下一扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值(限界)，并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。这种方式称为分支限界法。人们已经用分支限界法解决了大量离散最优化的问题。关键词：动态规划分支限界法编辑距离问题0-1背包问题目录1.动态规划法解决编辑距离问题..........................11.1问题描述.....................................................11.2问题分仔.....................................................11.3算法设计.....................................................21.4算法实现.....................................................31.5结果分析.....................................................51.6复杂度分析...................................................52.分支限界法解决0-1背包问题..........................62.1问题描述.....................................................62.2问题分析.....................................................62.3算法设计.....................................................72.4算法实现.....................................................72.5结果分析....................................................122.6复杂度分析.................................................123.参考文献..........................................1311.动态规划法解决编辑距离问题1.1问题描述设A和B是2个字符串。要用最少的字符操作将A转换为字符串B。这里所说的字符操作包括：（1）删除一个字符；（2）插入一个字符：（3）将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的2个字符串A和B，计算其编辑距离d（A,B）。1.2问题分仔设所给的两个字符串为A[1:m]和B[1:n]，定义一个二维数组dp[i][j]表示状态，dp[i][j]=(A[1:i],B[1:j])表示字符串A[1:m]的子串A[1:i]变换到B[1:n]的子串B[1:j]的编辑距离，即子串A[1:i]至少要经过多少次操作（插入、删除、修改）可以变为B[1:j]。单字符a,b间的编辑距离定义为例如，字符串A:AGTAAGTAGGC转换为字符串B:AGTCTGACGC。操作一：A串：AGTAAGT*AGGCB串：AGT*C*TGACGC需要5步操作（2次删除，2次修改，1次删除）操作二：A串：AGTAAGTAGGCB串：AGTCTG*ACGC需要4次操作（3次修改，1次删除）我们计算的编辑距离是变换的最小步数，所以要取其中的最小值。考察从字符串A[1:i]到字符串B[1:j]的转换，有三种情况可以导致上面设计的状态发生转移：bababad,1,0,2（1）可以删除字符A[i]需要1次操作。只将字符A[i]从A串中删除，对序列B[1:j]没有任何影响，此时问题的最优子结构形式为将A[1:i-1]变为B[1:j]，再加一步删除操作，可得dp[i][j]=dp[i-1][j]+1。（2）可以在A[i]后面插入一个字符ch（ch==B[j]）需要1次操作。在进行插入操作时，串A[1:i]无任何变化，在A串i+1位置上插入字符B[j],问题的最优子结构形式为将A[1:i]变为B[1:j-1],再加一步插入操作，可得dp[i][j]=dp[i][j-1]+1。（3）可以修改字符A[i]，使它变为B[j]，若A[i]=B[j]，修改其实相当于用了0步；若A[i]!=B[j]，修改相当于用了1步。所以dp[i][j]=dp[i-1][j-1]+（A[i]==B[j]?0：1）。最后的dp[i][j]就是选择上述3种状态转移中的最小值。综上所述，状态转移方程dp[i][j]可归结为如下情况：(1)当两个字符相同，即A[i]=B[j]时，dp[i][j]=min{dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]}(2)当两个字符不同，即A[i]!=B[j]时，dp[i][j]=min{dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]+1}需要注意的是，要对dp[0][0:m]，dp[0:n][0]进行初始化。*dp[0][i],就是说A串是一个空串，而B串是个长度为i的串，很显然A串变为B串就是插入i个字符，即dp[0][i]=i。*dp[i][0]，就是说A串是个长度为i的串，而B串是一个空串，很显然A串变为B串就是删除i个字符，即dp[i][0]=i。1.3算法设计数据输入：输入数据的第一行是一个正整数，表示一共有几组数据。每组数据两行，每行一个字符串。*每个字符串长度不超过1000结果输出：输出编辑距离。对于每组数据，请输出一个整数表示两个字符串的编辑距离。每个答案占一行。31.4算法实现#includecstdio#includeiostream#includecstring#definemin(a,b)(a)(b)?(b):(a)#defineN1005usingnamespacestd;intdp[N][N];//dp[i][j]表示串s1的前i位变换到串s2的前j位的最小步数intDP(char*s1,char*s2){inti,j,m=strlen(s1),n=strlen(s2),tem;//初始化for(i=0;i=n;i++)dp[0][i]=i;//从0个字符转换为i个字符，需要插入i次for(i=0;i=m;i++)dp[i][0]=i;//从i个字符转换为0个字符，需要删除i次//用动态规划方法计算编辑距离for(i=1;i=m;i++)for(j=1;j=n;j++){4if(s1[i-1]==s2[j-1])tem=dp[i-1][j-1];//当两个字符相同时，替换操作代价为0，直接将dp[i-1][j-1]转移过来elsetem=dp[i-1][j-1]+1;//当s1[i-1]!=s2[j-1]时,替换操作代价为1tem=min(tem,dp[i][j-1]+1);//dp[i][j-1]+1为在s1的i+1位置上插入字符s2[j]tem=min(tem,dp[i-1][j]+1);//dp[i-1][j]+1为在s1的i位置上删除字符s1[i]dp[i][j]=tem;//dp[i][j]取3种状态的最小值}returndp[m][n];//返回dp[m][n]}intmain(){intc;chars1[N],s2[N];printf(输入一个整数：);5scanf(%d,&c);getchar();while(c--){printf(\n输入两个字符串：\n);gets(s1);gets(s2);printf(其编辑距离为：%d\n,DP(s1,s2));}return0;}1.5结果分析1.6复杂度分析时间复杂度：总的时间复杂度为T(n*m+n+m)=O(m*n)最坏的时间复杂度为O(n^2)62.分支限界法解决0-1背包问题2.1问题描述给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。0-1背包问题的形式化描述是，给定c0,Wi0,Vi0，1in，要求找出一个n元0-1向量（x1，x2，……xn），Xi{0,1},1in，使得n1iiXiWc，而且n1iiiXV达到最大。因此0-1背包问题是一个特殊的整数规划问题：2.2问题分析0-1背包问题是一类典型的离散型优化问题，问题的约束条件和要求都很简单。求解方案也比较多，本论文就几种典型的求解方案做简单的分析，但是主要实现的是利用分支限界法解决的方案。下面是几种典型算法的简单分析：分支限界法：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一