算法设计与分析报告课程设计

《算法设计与分析报告课程设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实用标准成绩评定表学生姓名班级学号专业课程设计题目编辑距离问题分支限界法0-1背包评语组长签字：成绩文案大全实用标准日期20年月日课程设计任务书学院专业学生姓名班级学号课程设计题目编辑距离问题分支限界法0-1背包文案大全实用标准实践教学要求与任务:要求：1．巩固和加深对基本算法的理解和运用，提高综合运用课程知识进行算法设计与分析的能力。2．培养学生自学参考书籍，查阅手册、和文献资料的能力。3．通过实际课程设计，掌握利用动态规划算法、回溯法、分支限界法等算法的基本思想，并能运用这些方法设计算法并编写程序解决实际问题。4．了解与课程有关的知识，能正确解

2、释和分析实验结果。任务：按照算法设计方法和原理，设计算法，编写程序并分析结果，完成如下内容：1.运用动态规划算法求解编辑距离问题。2.运用分支限界算法求解0-1背包问题。工作计划与进度安排:第11周：查阅资料。掌握算法设计思想，进行算法设计。第12周：算法实现，调试程序并进行结果分析。撰写课程设计报告，验收与答辩。指导教师：201年月日专业负责人：201年月日学院教学副院长：201年月日文案大全实用标准摘要算法设计与分析，其实可以解释为一类优化问题，一般针对可以利用计算机解决的离散型问题的优化。主要目的就是为了解决某一问题而提出各种不同的解决方案，

3、并且要针对具体的问题做细致的空间和时间复杂度分析。所有的算法中，应该尽量选取“好”的算法，这里所说的“好”，首先是正确的，其次是所选算法解决问题的效率要尽可能的高。计算机计算时间的长短以及所用空间的大小，跟算法有直接关系，用来衡量算法好坏的两个重要标准就是就是时间和空间复杂度，所以提出好的解决方案，其算法是重中之重。动态规划算法是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。首先找出最优解的性质，并刻其结构特征，然后递归的定义最优值（写出动态规划方程）并且以自底向上的方式计算出最优值，最后根据计算最优值时得到的

4、信息，构造一个最优解。分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。分支限界法的搜索策略是，在扩展结点处，先生成其所有的儿子结点(分支)，然后再从当前的活结点表中选择下一扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值(限界)，并根据函数值，从当前活结点表中选择

5、一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。这种方式称为分支限界法。人们已经用分支限界法解决了大量离散最优化的问题。关键词：动态规划分支限界法编辑距离问题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.参考文献13文案大全实用标准文案大全实用标准1

6、.动态规划法解决编辑距离问题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]

7、变换到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[

8、1:j]的转换，有三种情况可以导致上面设计的状态发生转移：（1）可以删除字符A[i]需要1次操作。只将字符A[i]从A串中