《最优化方法在计算机专业的应用》由会员分享，可在线阅读，更多相关《最优化方法在计算机专业的应用（10页珍藏版）》请在金锄头文库上搜索。
1、动态规划方法在计算机专业的应用科目：最优化方法姓名：*专业：计算机科学与技术学号：201320405指导老师：*日期：2014/1/9动态规划方法在计算机专业的应用摘要：最优化方法是一门很有用的学科，本文结合计算机专业，讨论了用动态规划方法解决计算最长公共子序列、最大字段和、背包问题的过程，并对比其它算法以说明动态规划方法的高效、实用。关键词：动态规划，最优化，算法分析Abstract: The optimization method is a useful discipline, this paper, a computer professional, discusses the proce
2、ss 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动
3、态规划（dynamic programming）是通过结合子问题的解而解决整个问题的。（此处“programming”是指一种规划，而不是指写计算机代码。）动态规划适用于子问题不是独立的情况，也就是各子问题包含公共的子子问题。在这种情况下，若用分治法则会做很多不必要的工作，即重复地求解公共的子子问题。动态规划算法对每个公共的子子问题只求解一次，将其结果保存在一张表中，从而避免了每次遇到各个子问题时重新计算答案。一、 算法设计与优化 动态规划通常应用于最优化问题。此类问题可能有很多可行解。每个解有一个值，而我们希望找出一个具有最优（最大或最小）值的解。称这样的解为该问题的“一个”最优解（而不是“
4、确定的”最优解），因为可能存在多个取最优值的解。 动态规划算法的设计可以分为如下4个步骤：1） 描述最优解的结构。2） 递归定义最优解的值。3） 按自底向上的方式计算最优解的值。4） 由计算出的结果构造一个最优解。第13步构成问题的动态规划解的基础。第4步在只要求计算最优解的值时可以略去。如果的确做了第4步，则有时要在第3步的计算中记录一些附加信息，使构造一个最优解变得容易。 接下来的各节利用动态规划方法来求解一些最优化问题。比如包括两个汽车装配线的调度问题，在经过每个装配站后，组装中的汽车可以留在同一条装配线上，或者移动到另外一条装配线。如何通过做一连串的矩阵乘法，使得所做的标量乘法总次数最
5、少。此外，例如如何在已知待搜索的关键字分布的情况下，如何利用动态规划构造最优的二叉查找树，这些算法问题都可利用动态规划方法来解决。（一）最长公共子序列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,y
6、2,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记录序列和的最长公共子序列的长度。
7、其中， 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中
8、哪一个值所确定的。（二）最大子段和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=alef
9、t0?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, 那么b
10、j=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
11、 设所给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）贪心算法的基本原理与分析 贪心算法总是作出在当前看来是最好的选择，即贪心算法并不从整体最优解上加以考虑，它所作出的选择只是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但
12、对范围相当广的许多问题它能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好近似解。贪心算法求解的问题一般具有两个重要性质：贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。（2）0-1背包问题的实现对于0-1背包问题，设A是能装入容量为c的背包的具有最大价值的物品集合，则Aj
13、=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,
14、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;
