《算法设计动态规划》由会员分享，可在线阅读，更多相关《算法设计动态规划（8页珍藏版）》请在金锄头文库上搜索。
1、课题名称：动态规划编辑距离问题课题负责人名（学号）：同组成员名单（角色）：无扌旨导教师： 左劼评阅成绩：评阅意见：提交报告时间： 2010 年 6 月 23 日动态规划一一编辑距离问题计算机科学与技术专业学生指导老师左劼摘要动态规划的基本思想与分治法类似，也是将待求解的问题分解成若干份的子问题，先分别解决好子问题，然后从子问题中得到最终解。但动态规 划中的子问题往往不是相互独立的，而是彼此之间有影响，因为有些子问题可能 要重复计算多次，所以利用动态规划使这些子问题只计算一次。将字符串A变换为字符串所用的最少字符操作数称为字符串A到B的编辑距离。关键词：动态规划 矩阵 字符串操作数编辑距离一、问
2、题描述1、基本概念：设A和B是2个字符串。要用最少的字符操作将字 符串A转换为字符串B。字符串操作包括：(1) 删除一个字符；(2) 插入一个字符；(3) 将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。2、算法设计：设计一个有效算法，对于给定的任意两个字符串A和B，计算其编辑距离 d(A,B)。3、数据输入：输入数据由文件名为inpu t.tx 的文本文件提供。文件的第1行为字符串A，第二行为字符串B。4、结果输出：将编辑距离d(A,B)输出到文件oupu t.tx的第一行。输入文件示例 input .txt fxpimux
3、wrs输出文件示例outputtxt5二、分析对于本问题，大体思路为：把求解编辑距离分为字符串A从0个字符逐渐增加到全部字符分别想要变为字符串 B 该如何变化以及变化 的最短距离。具体来说，首先选用数组 a1 存储字符串 A( 设长度为 n)， a2 存储 字符串B(设长度为m) ，d矩阵来进行具体的运算；这里有两个特殊情况比较简单可以单独考虑，即 A的长度为0而B不为0还有A不为0B为0,这两种情况最后的编辑距离分别为m和n讨论一般情况，d矩阵为dnml假定我们从d00开始一直进行以下操作到了 di 的 位置，其中删除操作肯定是A比B长，同理，插入字符操作一定是A 比 B 短，更改字符操作说
4、明一样长，我们所要做的是对dij-1di-1jdi-lj-所存数进行比较，其中最小的即为当前长度和样式 的字符串A变为B的编辑距离，依次这样计算到最后的dnm中所存的数即为最终的编辑距离。三、证明1、理论前提：动态规划的基本思想与分治法类似，也是将待求 解的问题分解成若干份的子问题，先分别解决好子问题，然后从子问 题中得到最终解。但动态规划中的子问题往往不是相互独立的，而是 彼此之间有影响。该算法的有效性依赖于两个重要的性质：最优子结 构性质和问题重叠性质。最有子结构性：以自底向上的方法递归地从子问题的最优解逐步 构造出整个问题的最优解。重叠子问题性：每次产生的子问题并不总是新问题，利用动态规
5、 划对每一个子问题只解一次，并将其存入表格中，下次用到该子问题 的解时，只要查找表格即可。2、本题：本题首先符合最优子结构性，即让字符串A从1开始递增到最终长度n也就是从只有一个字符开始计算，每增加一个字符 计算一次，符合自底向上的方法递归地解决子问题；其次符合重叠子 问题性，每增加一个字符计算的时候总要用到前一状态时的编辑距 离，并且本题我采用了矩阵来存储旧子问题的数据，都只计算了一次，所以也符合。3、总结：综上两点，可知本题米用了动态规划的思想来解决， 并能得到正确的答案。四、代码及解释(注释)#include #include#include #include using namespa
6、ce std;const int MAX=1000;int min(int a,int b)if(a二b)return b;elsereturn a;int main()int dMAXMAX;int i,j;char a1MAX, a2MAX;FILE *fp;fp=fopen(input txt,r); fscanf(fp,%s,al); fscanf(fp,%s,a2);fclose(fp);int n=strlen(a1)-1;/字符串末尾多 1int m二strlen(a2)T;for(i=0;i二n;i+)/从i变到0字符串，i个需要次添加）for(i=0;i=m;i+)/从 0字
7、符串变到j j个需要次删除）=i；for(i=1;i=n;i+)for(j=1;j=m;j+)if(a1i!=a2j)二min(min(dij1,diTj),diTjT)+1;/加一个，减一个，变一个else: coutdnm;fp二fopen(output txt,w);fprintf(fp,%d,dnm);fclose(fp);return 0;*输入： fxpimuxwrs输出：5*/五、复杂度分析以下为核心代码部分：for(i=0;i=n;i+)di0=i;一重循环时间复杂度为 for(i=0;i=m;i+) d0i=i;一重循环时间复杂度为/从 i变到0字符串，T(n)/从 0字符串
8、变到 jT(m)i个需要次添加)j个需要次(删除)for(i=1;i=n;i+) for(j=1;j=m;j+) if(a1i!=a2j)dij=min(min(dij-1,di-1j),di-1j-1)+1;/加一个，减一个，变一个else二重循环：时间复杂度为T(n *m)总的时间复杂度为 T(n*m+n+m)= (n*m)O 2最好时间复杂度为 (n)；最坏时间复杂度为(n )参考文献1 王晓东.计算机算法设计与分析(第8 次印刷)P4& P53-54， P892 科曼(Cormen T.H.)等著潘金贵等译2008.6(第 9 次印刷)P202-2073版).电子工业出版社 ，2009.12 (第.算法导论 第二版).机械工业出版社，
