算法设计和分析课程设计.docx

成 绩 评 定 表 学生姓名 班级学号 专 业 课程设计题目 编辑距离问题 分支限界法0-1背包 评 语 组长签字： 成绩 日期 20 年 月 日 课程设计任务书 学 院 专 业 学生姓名 班级学号 课程设计题目 编辑距离问题 分支限界法0-1背包 实践教学要求与任务: 要求： 1．巩固和加深对基本算法的理解和运用，提高综合运用课程知识进行算法设计与分析的能力。 2．培养学生自学参考书籍，查阅手册、和文献资料的能力。 3．通过实际课程设计，掌握利用动态规划算法、回溯法、分支限界法等算法的基本思想，并能运用这些方法设计算法并编写程序解决实际问题。 4．了解与课程有关的知识，能正确解释和分析实验结果。 任务： 按照算法设计方法和原理，设计算法，编写程序并分析结果，完成如下内容： 1. 运用动态规划算法求解编辑距离问题。 2. 运用分支限界算法求解0-1背包问题。 工作计划与进度安排: 第11周：查阅资料。掌握算法设计思想，进行算法设计。 第12周：算法实现，调试程序并进行结果分析。 撰写课程设计报告，验收与答辩。 指导教师： 201 年 月 日 专业负责人： 201 年 月 日 学院教学副院长： 201 年 月 日 摘要 算法设计与分析，其实可以解释为一类优化问题，一般针对可以利用计算机解决的离散型问题的优化。主要目的就是为了解决某一问题而提出各种不同的解决方案，并且要针对具体的问题做细致的空间和时间复杂度分析。所有的算法中，应该尽量选取“好”的算法，这里所说的“好”，首先是正确的，其次是所选算法解决问题的效率要尽可能的高。计算机计算时间的长短以及所用空间的大小，跟算法有直接关系，用来衡量算法好坏的两个重要标准就是就是时间和空间复杂度，所以提出好的解决方案，其算法是重中之重。 动态规划算法是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。首先找出最优解的性质，并刻其结构特征，然后递归的定义最优值（写出动态规划方程）并且以自底向上的方式计算出最优值，最后根据计算最优值时得到的信息，构造一个最优解。 分支限界法类似于回溯法，也是在问题的解空间上有哪些信誉好的足球投注网站问题解的算法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。分支限界法的有哪些信誉好的足球投注网站策略是，在扩展结点处，先生成其所有的儿子结点(分支)，然后再从当前的活结点表中选择下一扩展结点。为了有效地选择下一扩展结点，加速有哪些信誉好的足球投注网站的进程，在每一个活结点处，计算一个函数值(限界)，并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使有哪些信誉好的足球投注网站朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。这种方式称为分支限界法。人们已经用分支限界法解决了大量离散最优化的问题。 关键词：动态规划 分支限界法 编辑距离问题 0-1背包问题 目录 TOC \o 1-3 \h \z \u HYPERLINK \l _Toc482820338 1.动态规划法解决编辑距离问题 PAGEREF _Toc482820338 \h 1 HYPERLINK \l _Toc482820339 1.1问题描述 PAGEREF _Toc482820339 \h 1 HYPERLINK \l _Toc482820340 1.2问题分仔 PAGEREF _Toc482820340 \h 1 HYPERLINK \l _Toc482820341 1.3算法设计 PAGEREF _Toc482820341 \h 2 HYPERLINK \l _Toc482820342 1.4算法实现 PAGEREF _Toc482820342 \h 3 HYPERLINK \l _Toc482820343 1.5结果分析 PAGEREF _Toc482820343 \h 5 HYPERLINK \l _Toc482820344 1.6复杂度分析 PAGEREF _Toc482820344 \h 5 HYPERLINK \l _Toc482820345 2.分支限界法解决0-1背包问题 PAGEREF _Toc482820345 \h 6 HYPERLINK \l _Toc482820346 2.1问题描述 PAGEREF _Toc482820346 \h 6 HYPERLINK \l _Toc482820347 2.2问题分析 PAGEREF _Toc482820347 \h 6 HYPERLINK \l _Toc48282