《算法导论课程设计》由会员分享，可在线阅读，更多相关《算法导论课程设计（15页珍藏版）》请在金锄头文库上搜索。
1、课 程 设 计 报 告课程名称 算法导论 .课题名称. 编辑距离问题 专 业 信息与计算科学 班 级 1402 班 学 号 14 20 32 姓 名 王玉杰 范才建 蒋少能 指导教师 阳卫峰 2016年 11月 28日湖 南 工 程 学 院课 程 设 计 任 务 书课程名称 算法导论 课 题 编辑距离问题 专业班级 信息与计算科学1402 班 学生姓名 王玉杰 范才建 蒋少能 学 号 14 20 32 指导老师 阳卫峰 审 批 任务书下达日期 2016 年 11月 16 日任务完成日期 2016年 11月28日一、设计内容与设计要求1设计内容： 设A 和B 是2 个字符串。要用最少的字符操作将
2、字符串A 转 换为字符串B。 这里所说的 字符操作包括 1)删除一个字符； 2)插入一个字符； 3)将一个字符改为另一个字符。 将字符串A变换为字符串B 所用的最少字符操作数称为字符串A到B 的编辑距离，记为 d(A,B)。试设计一个有效算法，对任给的2 个字符串A和B，计算出它们的编辑距离d(A,B)。2设计要求：l 课程设计报告正文内容(一)问题的描述；(二)算法设计与分析，内容包括 1) 算法设计，对问题的分析和算法的设计 2)算法描述，以伪代码形式的算法 3)算法分析，主要是算法的正确性和运行时间的分析(三)算法实现 所有程序的原代码，要求用java语言程序实现，并对程序写出必要的注释
3、。摘要 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法其基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。我们保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。 因此在考虑编辑距离问题时，我们可以利用动态规划的思想找到最优解。在这里我们利
4、用Java语言实现了编辑距离问题的算法。关键字：动态规划；Java；一、 问题描述1.基本情况 1）设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。 这里所说的 字符操作包括 i)删除一个字符； ii)插入一个字符； iii)将一个字符改为另一个字符。 2）将字符串A变换为字符串B 所用的最少字符操作数称为字符串A到B 的编辑距离， 3）记为 d(A,B)。试设计一个有效算法，对任给的2 个字符串A和B，计算出它们的编辑距离d(A,B)。2. 需要解决的问题算法设计，对问题的分析和算法的设计找出字符串的编辑距离，即把一个字符串s1最少经过多少步操作变成编程字符串s2，
5、操作有三种：1.添加一个字符 2.删除一个字符 3.修改一个字符二、 算法设计与分析1.算法设计1)本题提出了一些关于将字符串x1.m转换成y1.n的操作。这些操作有替代、删除、插入。这些操作所需的开销是不同的，但每个操作的开销都可以看是一个我们已经的常量，我们假设复制和替代这类操作的开销要比插入和删除这类操作的开销一样。我们用x1.m来保存原字符串，数组下标用i表示，初始化为1；用y1.n来保存转换后的字符串，数组下标用j来表示，初始化为1；数组z用来存放中间结果，下标用j来表示，初始化为0。 2)题目有两个待解决的问题：第一，给定两个序列x1.m和y1.n以及变换操作开销的集合。从x到y的
6、编辑距离指的就是将x转换成y时的最小开销的操作序列。用动态规划的算法找出从x到y的编辑距离并输出最优操作序列。分析算法的时空复杂度。第二，解释如何从给定的编辑操作集选择一个子集，从而把寻找总分最高的对齐结果的问题，转化为求序列编辑距离的问题的一个特例。因此，我仿照最长公共子序列问题的方法来求解这个问题。首先，定义了两个序列Xi=x1,2,.,m和Yj=y1,2,n，题目所求的就是将序列xi变为yj的编辑操作序列的最小开销。 3)刻画最优解的结构：对于序列Xi(0im)和序列Yj(0jn)来说，定义ci,j为Xi转换成Yj的操作序列的最小开销。假定我们已经知道了最后一次执行的操作，此时分情况讨论
7、问题的最优解结构。 4)最后一次操作为copy。此时，根据题目的定义可知xi=yj，我们待解决的问题就转化成了求将Xi-1转换为Yj-1的最小开销。将Xi-1转换为Yj-1的最优解一定包含在Xi转换为Yj的最优解内。用反证法证明：若存在从Xi-1到yj-1转换的更小的开销，那么用这个更小的开销来代替Xi-1转换为yj-1的最优解，这样就会得到一个更小的从Xi转换为Yj的开销，与已知的Xi转换为Yj的最优解矛盾，所以假设不成立。因此，当最后一次操作为copy时，可以定义ci,j=ci-1,j-1+cost(copy)。 5)最后一次操作为replace。此时，根据题目的定义可知xiyj。仿照上述
8、分析，可以得到相同的最优子结构。此时ci,j=ci-1,j-1+cost(replace)。 6)最后一次操作为delete。根据题意，这时只是将xi从序列Xi中除去，对序列Yj没有任何影响，此时问题的最优子结构的形式为将Xi-1转换成Yj，于是可以得到ci,j=ci-1,j+cost(delete)。7) 最后一次操作为insert。根据题意，在进行插入操作时，序列Xi无任何变化，序列Yj添加一个字符，因此，这时候问题的最优子结构的形式为将Xi转换成为Yj-1，此时ci,j=ci,j-1+cost(insert),即求得编辑距离。算法分析 Distance(编辑距离)算法详解编辑距离即从一个
9、字符串变换到另一个字符串所需要的最少变化操作步骤（以字符为单位，如son到sun，s不用变，将o-s,n不用变，故操作步骤为1）。为了得到编辑距离，我们画一张二维表来理解，以beauty和batyu为例：2.算法描述 初始化过程: public int getDistance(char str1, char str2) int n = str1.length;int m = str2.length;int C = new intn + 1m + 1;int i, j;int x = 0, y = 0, z = 0;for (i = 0; i = n; i+) Ci0 = i;for (i =
10、0; i = m; i+) C0i = i;for (i = 0; i n; i+) for (j = 0; j m; j+) x = Cij + 1 + 1;y = Ci + 1j + 1;if (str1i = str2j)z = Cij;elsez = Cij + 1;Ci + 1j + 1 = Math.min(Math.min(x, y), z); return Cnm;3.算法时间复杂度分析该算法是对一个(m+1)(n+1)的表格进行填写的过程，填写每一个格cij花费的开销，只是根据 ci-1j, cij-1, ci-1j-1, ci-2j-1进行简单的加减运算，得到五个数字，选择
11、其中最小的一个。所以该算法的时间复杂度为O(mn)。因此有以下程序:Edit-Distance(char str1, char str2)int , C = new intn + 1,m + 1;int i, j;int x = 0, y = 0, z = 0;for i = 0 to n /循环n次，是O(n)Ci,0 = i;for i = 0 to n /循环m次,是O(m)C0,i = i;for i = 0 to n /循环n次,是O(n)for j = 0 to m /循环n*m次,是O(m*n)x = Ci,j + 1 + 1;y = Ci + 1,j + 1;if str1i
12、= str2jz = Ci,j;elsez = Ci,j + 1;Ci + 1,j + 1 = Math.min(Math.min(x, y), z);return Cnm; 三、 程序调试1. 使用说明 1）输入两个字符串，每个字符串以 结束输入 2）在控制台上将输出从文本一转到文本二的最优编辑距离2. 输入样例 输入第一个文本：(注：以 enter + # 号结束)： 2016中国无人机摄影大赛，作品征集已近尾声。期间，组委会以散片或专题形式，在搜狐新闻、搜狐新闻客户端焦点图或资讯流等重要位置，向搜狐网友推送了参赛选手的航拍作品，这些作品，本身即是视觉大片，俯瞰的角度更为网友打开了新的视界。# 输入第二个文本：(注：以 enter + # 号结束) 出差之余，总会停下匆忙的脚步，去记录每一座城市不同视角的景与物。大自然变化万千，却也稍纵即逝。#3.控制台结果：输入第一个文本：(注：以 enter + # 号结束) 2016中国无人机摄影大赛，作品征集已近尾声。期间，组委会以散片或专题形式，在搜狐新闻、搜狐新闻客户端焦点图或资讯流等重要位置，向搜狐网友推送了参赛选手的航拍作品，这些作品，本身即是视觉大片，俯瞰的角度更为网友打开了新的视界。# 文本一 录
