最优化方法在计算机专业的应用.docx

动态规划方法在计算机专业的应用科目：最优化方法姓名：*专业：计算机科学与技术学号：201320405指导老师：*日期：2019/2/3动态规划方法在计算机专业的应用摘要：最优化方法是一门很有用的学科，本文结合计算机专业，讨论了用动态规划方法解决计算最长公共子序列、最大字段和、背包问题的过程，并对比其它算法以说明动态规划方法的高效、实用。关键词：动态规划，最优化，算法分析Abstract: The optimization method is a useful discipline, this paper, a computer professional, discusses the process used to calculate the dynamic programming method to solve the longest common subsequence, the maximum field and, knapsack problem, and compared to other algorithms to illustrate the dynamic programming method efficient and practical.Keywords: dynamic programming, optimization, algorithm analysis动态规划（dynamic programming）是通过结合子问题的解而解决整个问题的。（此处“programming”是指一种规划，而不是指写计算机代码。）动态规划适用于子问题不是独立的情况，也就是各子问题包含公共的子子问题。在这种情况下，若用分治法则会做很多不必要的工作，即重复地求解公共的子子问题。动态规划算法对每个公共的子子问题只求解一次，将其结果保存在一张表中，从而避免了每次遇到各个子问题时重新计算答案。一、 算法设计与优化 动态规划通常应用于最优化问题。此类问题可能有很多可行解。每个解有一个值，而我们希望找出一个具有最优（最大或最小）值的解。称这样的解为该问题的“一个”最优解（而不是“确定的”最优解），因为可能存在多个取最优值的解。 动态规划算法的设计可以分为如下4个步骤：1） 描述最优解的结构。2） 递归定义最优解的值。3） 按自底向上的方式计算最优解的值。4） 由计算出的结果构造一个最优解。第13步构成问题的动态规划解的基础。第4步在只要求计算最优解的值时可以略去。如果的确做了第4步，则有时要在第3步的计算中记录一些附加信息，使构造一个最优解变得容易。 接下来的各节利用动态规划方法来求解一些最优化问题。比如包括两个汽车装配线的调度问题，在经过每个装配站后，组装中的汽车可以留在同一条装配线上，或者移动到另外一条装配线。如何通过做一连串的矩阵乘法，使得所做的标量乘法总次数最少。此外，例如如何在已知待搜索的关键字分布的情况下，如何利用动态规划构造最优的二叉查找树，这些算法问题都可利用动态规划方法来解决。（一）最长公共子序列1、具体问题（1）、若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。（2）、给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。（3）、给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。 2、分析设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk ，则(1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。(2)若xmyn且zkxm，则Z是xm-1和Y的最长公共子序列。(3)若xmyn且zkyn，则Z是X和yn-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。3、子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其它情况下，由最优子结构性质可建立递归关系如下：由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。计算最优值：4、 算法的改进在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素cij的值仅由ci-1j-1，ci-1j和cij-1这3个数组元素的值所确定。对于给定的数组元素cij，可以不借助于数组b而仅借助于c本身在时间内确定cij的值是由ci-1j-1，ci-1j和cij-1中哪一个值所确定的。（二）最大子段和1、分治法n个数(可能是负数）组成的序列求该序列形如 的子序列的最大值。也就是：例如: 序列(-2,11,-4,13,-5,-2) ，最大子段和：11-4+1320。穷举算法： O(n3), O(n2)将序列a1:n从n/2处截成两段：a1:n/2, an/2+1:n（1） 最大子段和出现在左边一段（2） 最大子段和出现在右边一段（3） 最大子段和跨越中间的断点对于第三种情况：那么，S1+S2是第三种情况的最优值。int MaxSubSum(int *a, int left, int right)int sum;if (left=right) sum=aleft0?aleft:0; return sum; /左边区域的最大子段和；int leftSum=MaxSubSum(a,left,(left+right)/2); /右边区域的最大子段和；int rightSum=MaxSubSum(a,(left+right)/2+1,right); /求S1,S2;sum=S1+S2;return (sum,leftSum,rightSum);复杂度分析T(n)=O(nlogn) 渐进意义下的最优算法 2、动态规划方法求解定义bj： 含义：从元素i开始，到元素j为止的所有的元素构成的子段有多个，这些子段中的子段和最大的那个。那么：如果：bj-10, 那么bj=bj-1+aj如果：bj-1=0,那么bj=aj这样，显然，我们要求的最大子段和，是bj数组中最大的那个元素。int MaxSum(int n, int *a)int sum=0, b=0;for (int i=1;i0) b+=ai;else b=ai;if (bsum) sum=b;return sum;时间复杂度： O(n)空间复杂度： O(n)（三）、0-1背包问题 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?0-1背包问题是一个特殊的整数规划问题。例如：最优解为：(1,0,1)此时的价值为：6 设所给0-1背包问题的子问题1、递归方法分析最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。算法复杂度分析：从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c2n时，算法需要(n2n)计算时间。 2、贪心算法（1）贪心算法的基本原理与分析 贪心算法总是作出在当前看来是最好的选择，即贪心算法并不从整体最优解上加以考虑，它所作出的选择只是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好近似解。贪心算法求解的问题一般具有两个重要性质：贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。（2）0-1背包问题的实现对于0-1背包问题，设A是能装入容量为c的背包的具有最大价值的物品集合，则Aj=A-j是n-1个物品1,2,.,j-1,j+1,.,n可装入容量为c-wj的背包的具有最大价值的物品集合。用贪心算法求解0-1背包问题的步骤是，首先计算每种物品单位重量的价值vi/wi；然后，将物品进行排序，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总量未超过c，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直进行下去，直到背包装满为止。（3）算法设计如下：#include#define max 100 /最多物品数void sort (int n,float amax,float bmax)/按价值密度排序int j,h,k;float t1,t2,t3,cmax;for(k=0;kn;k+)ck=ak/bk;for(j=0;jn;j+)if(cjcj+1)t1=aj;aj=aj+1;aj+1=t1;t2=bj;bj=bj+1;bj+1=t2;t3=cj;cj=cj+1;cj+1=t3;void knapsack(int n,float limitw,float vmax,float wmax,int xmax)float c1; /c1为背包剩余可装载重量int i;sort(n,v,w); /物品按价值密度排序c1=limitw;for(i=0;ic1)break;xi=1; /xi为1时，物品i在解中c1=c1-wi;void main()int n,i,xmax;float vmax,wmax,totalv=0,totalw=0,limitw;coutn limitw;for(i=1;i=n;i+)xi=0; /物品选择情况表初始化为0cout请依次输入物品的价值：endl;for(i=1;ivi;coutendl;cout请依次输入物品的重量：endl;for(i=1;iwi;coutendl;knapsack (n,limitw,v,w,x);coutthe selection is:;for(i=1;i=n;i+)coutxi;if(xi=1)totalw=totalw+wi;totalv=totalv+vi;coutendl;cout背包的总重量为：totalwendl; /背包所装载总重量cout背包的总价值为：totalvendl; /背包的总价值运行结果：3、动态规划算法（1）、动态规划的基本原理与分析动态规划算法的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。它把已知问题分为很多子问题，按顺序求解子问题，在每一种情况下，列出各种情况的局部解，按条件从中选取那些最有可能产生最佳的结果舍弃其余。前一子问题为后面子问题提供信息，而减少计算量，最后一个子问题的解即为问题解。采用此方法求解0-1背包问题的主要步骤如下： 析最优解的结构：最有子结构性质； 建立递归方程； 计算最优值； 构造最优解4。（2）、问题的实现 最优子结构性质0-1背包问题具有最优子结构性质。设(y1，y2yn)是所给0-1背包问题的一个最优解，则(y2，y3yn)是下面相应子问题的一个最优解：若不然，设(z2，z3zn)是上述问题的一个最优解，而(y2，y3yn)不是它的最优解，由此可见,且c。因此c这说明(y1，z2zn)是所给0-1背包问题的一个更优解，从而(y1，y2yn)不是所给0-1背包问题的最优解。此为矛盾1。 递归关系设所给0-1背包问题的子问题的最优值为m(i,j)，即m(i,j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下：分析：利用动态规划求解0-1背包问题的复杂度为0(minnc,2n。动态规划主要是求解最优决策序列，当最优决策序列中包含最优决策子序列时，可建立动态规划递归方程，它可以帮助高效地解决问题。总结：最优化方法是一门很有用的课程，可以应用到数学、物理、化学、计算机、管理等多种领域，有利于解决科研和实践中遇到的理论