算法设计与分析课程设计-编辑距离问题分支限界法0-1背包.docx

成 绩 评 定 表学生姓名班级学号专 业课程设计题目编辑距离问题分支限界法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.参考文献131.动态规划法解决编辑距离问题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问题分仔设所给的两个字符串为A1:m和B1:n，定义一个二维数组dpij表示状态，dpij= (A1:i,B1:j)表示字符串A1:m的子串A1:i变换到B1:n的子串B1:j的编辑距离，即子串A1:i至少要经过多少次操作（插入、删除、修改）可以变为B1:j。单字符a,b间的编辑距离定义为 例如，字符串A:AGTAAGTAGGC转换为 字符串B:AGTCTGACGC 。 操作一：A串：A G T A A G T * A G G C B串：A G T * C * T G A C G C 需要5步操作（2次删除，2次修改，1次删除） 操作二：A串：A G T A A G T A G G C B串：A G T C T G * A C G C 需要4次操作（3次修改，1次删除）我们计算的编辑距离是变换的最小步数，所以要取其中的最小值。考察从字符串A1:i到字符串B1:j的转换，有三种情况可以导致上面设计的状态发生转移：（1）可以删除字符Ai需要1次操作。只将字符Ai从A串中删除，对序列B1:j没有任何影响，此时问题的最优子结构形式为将A1:i-1 变为B1:j ，再加一步删除操作，可得dpij = dpi-1j + 1。（2）可以在Ai后面插入一个字符ch（ch=Bj）需要1次操作。在进行插入操作时，串A1:i 无任何变化，在A串i+1位置上插入字符Bj,问题的最优子结构形式为将A1:i变为B1:j-1,再加一步插入操作，可得dpij = dpi j-1 + 1。（3）可以修改字符Ai，使它变为Bj，若Ai=Bj，修改其实相当于用了0步；若Ai != Bj，修改相当于用了1步。所以dpij = dpi - 1j - 1 + （Ai = Bj ? 0：1）。 最后的dpij就是选择上述3种状态转移中的最小值。综上所述，状态转移方程dpij可归结为如下情况： (1)当两个字符相同，即Ai=Bj时， dpij = mindpij-1+1, dpi-1j+1, dpi-1j-1 (2)当两个字符不同，即Ai != Bj时， dpij = mindpij-1+1, dpi-1j+1, dpi-1j-1+1需要注意的是，要对dp00:m，dp0:n0进行初始化。*dp0i,就是说A串是一个空串，而B串是个长度为i的串，很显然A串变为B串就是插入i个字符，即dp0i=i。*dpi0 ，就是说A串是个长度为i的串，而B串是一个空串，很显然A串变为B串就是删除i个字符，即dpi0=i。1.3算法设计数据输入：输入数据的第一行是一个正整数，表示一共有几组数据。每组数据两行，每行一个字符串。*每个字符串长度不超过1000结果输出：输出编辑距离。对于每组数据，请输出一个整数表示两个字符串的编辑距离。每个答案占一行。1.4算法实现#includecstdio #includeiostream #includecstring #define min(a,b) (a)(b)?(b):(a) #define N 1005 using namespace std; int dpNN; /dpij表示串s1的前i位变换到串s2的前j位的最小步数int DP(char *s1,char *s2) int i,j,m=strlen(s1),n=strlen(s2),tem;/初始化 for(i=0;i=n;i+) dp0i=i; /从0个字符转换为i个字符，需要插入i次 for(i=0;i=m;i+) dpi0=i; /从i个字符转换为0个字符，需要删除i次 /用动态规划方法计算编辑距离 for(i=1;i=m;i+) for(j=1;j=n;j+) if(s1i-1=s2j-1) tem=dpi-1j-1; /当两个字符相同时，替换操作代价为0 ，直接将dpi-1j-1 转移过来 else tem=dpi-1j-1+1; /当s1i-1!=s2j-1时, 替换操作代价为1 tem=min(tem,dpij-1+1); /dpij-1+1为在s1的i+1位置上插入字符s2j tem=min(tem,dpi-1j+1); /dpi-1j+1为在s1的i位置上删除字符s1i dpij=tem; /dpij取3种状态的最小值 return dpmn; /返回dpmn int main() int c; char s1N,s2N; printf(输入一个整数：); scanf(%d,c); getchar(); while(c-) printf(n输入两个字符串：n); gets(s1); gets(s2); printf(其编辑距离为：%dn,DP(s1,s2); return 0; 1.5结果分析1.6复杂度分析时间复杂度：总的时间复杂度为T(n*m+n+m)=O(m*n) 最坏的时间复杂度为O(n2) 2.分支限界法解决0-1背包问题2.1问题描述给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。0-1背包问题的形式化描述是，给定c0,Wi0,Vi0，1in，要求找出一个n元0-1向量（x1，x2，xn），Xi0,1,1in，使得，而且达到最大。因此0-1背包问题是一个特殊的整数规划问题：2.2问题分析0-1背包问题是一类典型的离散型优化问题，问题的约束条件和要求都很简单。求解方案也比较多，本论文就几种典型的求解方案做简单的分析，但是主要实现的是利用分支限界法解决的方案。下面是几种典型算法的简单分析：分支限界法：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法： 队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 最大优先队列：使用最大堆，体现最大效益优先 最小优先队列：使用最小堆，体现最小费用优先 2.3算法设计分支限界法的分析：已知有N个物品和一个可以容纳M重量的背包，每种物品I的重量为WEIGHT，一个只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的总效益最大。对物品的选取与否构成一棵解树，左子树表示不装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。分支限界法的描述：首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。2.4算法实现#include stdio.h#include stdlib.h#include iostream.h#define MaxSize 100 /初始化队列长度为100typedef struct QNodefloat weight; float value; intceng; struct QNode *parent; bool leftChild;QNode,*qnode; /定义队列类型typedef structqnode QMaxSize; int front,rear;SqQueue; /定义队列SqQueue sq;float bestv=0; /最优解int n=0; /实际物品数float wMaxSize; /物品的重量float vMaxSize; /物品的价值int bestxMaxSize; / 存放最优解qnode bestE;void InitQueue(SqQueue sq ) /队列初始化sq.front=1;sq.rear=1;bool QueueEmpty(SqQueue sq) /队列判空if(sq.front=sq.rear)return true;elsereturn false;void EnQueue(SqQueue sq,qnode b)/结点入队函数if(sq.front=(sq.rear+1)%MaxSize)cout队满，请修改队列初始大小!endl;exit(1); /队满出错，不再继续计算return ;sq.Qsq.rear=b;sq.rear=(sq.rear+1)%MaxSize;qnode DeQueue(SqQueue sq)/出队qnode e;if(sq.front=sq.rear)return 0;e=sq.Qsq.front;sq.front=(sq.front+1)%MaxSize;return e;void EnQueue1(float wt,float vt, int i , QNode *parent, bool leftchild)qnode b;if (i=n) /可行叶子结点if (vt=bestv)bestE=parent;bestxn=(leftchild)?1:0;return;b=(qnode)malloc(sizeof(QNode); /非叶子结点b-weight=wt;b-value=vt;b-ceng=i;b-parent=parent;b-leftChild=leftchild;EnQueue(sq,b);void maxLoading(float w,float v,int c)float wt=0;float vt=0;int i=1; /当前的扩展结点所在的层float ew=0; /扩展节点所相应的当前载重量float ev=0; /扩展结点所相应的价值qnode e=NULL;qnode t=NULL;InitQueue(sq);EnQueue(sq,t); /空标志进队列while (!QueueEmpty(sq)wt=ew+wi;vt=ev+vi;if (wt = c)if(vtbestv)bestv=vt;EnQueue1(wt,vt,i,e,true); / 左儿子结点进队列EnQueue1(ew,ev,i,e,false); /右儿子总是可行；e=DeQueue(sq); / 取下一扩展结点if