算法概念介绍及举例说明.ppt

例子:给定两个正整数m和n,求它们的最大公因子算法:欧几里德算法输入:正整数m、n输出：m和n的最大公因子,第一章 算法引论,1.1 算法的基本概念,一、什么是算法及其与程序的区别,S1:保证m=n,如果mn，则m、n的值互换，否则转S2.S2:求余数。令r=m mod n,（0=rn)S3:判断余数r是否为0。如果r是0，则算法终止，n为答案，否则转S4.S4:置换。即mn,nr,转S2.,什么是算法？,它是一组有穷规则的集合，它规定了解决某一特定类型问题的一系列运算。,二、算法的特征 1、确定性 2、能行性 3、输入 4、输出 5、有穷性:一个算法总是在有限步之后结束，且每一步都可在有穷时间内完成.,算法与程序的区别：程序：与某种语言有关，能直接在机器上运行。算法：与特定的语言无关，可用任何语言实现，甚至可以用自然语言实现，但是一般为了避免二义性，本书采用类C语言描述。,一个算法总是在执行了有穷步骤的运算后终止，否则就是一个计算过程。,有穷性与有效性的关系：,三、评价算法的标准,有穷性是对算法的基本要求，如果一个算法要能使用，必须具有有效性。有效性是指算法在规定的时间里终止。,时间复杂性和空间复杂性,1.2 算法设计的步骤,一、问题的描述,例:货郎担问题 设售货员在一天内要到5个城市去推销货物，已知从一个城市到其他城市的费用，求总费用最少的路线。给出的信息主要有五个城市的关系图及相应的费用矩阵。,二、模型的拟制 建模阶段至少要考虑以下两个基本问题：1）最适合于这个问题的数学结构是什么？2）有没有已经解决了的类似问题可供借鉴？,在模型建立好了以后，应该依据所选定的模型对问题重新陈述,并考虑下列问题:,(1)模型是否清楚地表达了与问题有关的所有重要的信息?(2)模型中是否存在与要求的结果相关的数学量?(3)模型是否正确反映了输入、输出的关系?(4)对这个模型处理起来困难吗？,对于货郎担问题，其数学模型是带权图，与此图相关的是费用矩阵。,以货郎担问题为例：采用枚举法。分析：,三、算法的详细设计,算法的详细设计是指设计求解某个具体问题的一系列步骤，并且这些步骤可以通过计算机的各种操作来实现。,输入：城市数目n;费用矩阵C=(cij)n*n输出：旅行路线TOUR;最小费用MIN,Salesman(n)i 1;tour0;min while i=(n-1)!do pPHRMUTI(n-1,i);/PHRMUTI(n-1,i)是生成1到n-1的第i个排列的子过程 cost(T(p)EFP(c,T(p)；/EFP(c,T)是由费用矩阵c及路线T(p)所算得的总费用 if cost(T(p)min tourT(p);mincost(T(p)ii+1;print min,tour,四、算法的正确性 可以分两步考虑:(1)算法的终止性；(2)算法的每一步是否都正确 算法的正确性并不蕴涵算法的有效性。,五、算法分析 时间复杂性和空间复杂性 以上货郎担问题的时间复杂性是：O(n!),六、文档的编制,（1）注释（2）算法的流程图（3）对输入/输出的要求（4）正确性证明（5）时间复杂性和空间复杂性的分析,二、算法分析的要点 1、确定使用的运算和执行这些运算所用的时间。运算分为两类(1)基本运算；(2)“组合”运算由基本运算组成。,1.3 算法分析,一、算法分析的原因 1、为了对算法的某些特定的输入，估计或限界该算法所需要的空间和运行时间。2、为了建立衡量算法优劣的标准，用以比较同一问题的不同算法。,时间是固定量,时间是变化量,2、确定能反映出算法在各种情况下工作的数据集构造出能产生最好、最坏和有代表性情况的数据配置。,三、算法分析的两个阶段,1、事前分析求出该算法的一个时间限界函数。,2、事后测试收集此算法的执行时间和实际占用空间的统计资料。,就算法分析而言，一条语句的数量级指的是执行它的频率，而一个算法的数量级则指的是它所有语句执行频率的和。确定一个算法的数量级是十分重要的，它在本质上反映了一个算法所需要的计算时间。,四、计算时间的渐进表示 假设某种算法的计算时间是f(n),其中变量n可以是输入或输出量，也可以是两者之和，还可以是它们之一的某种测度（例如，数组的维数，图的边数等等）。g(n)是在事前分析中确定的某个形式很简单的函数，例如，nm,logn,2n,n!等。它是独立于机器和语言的函数，而f(n)则与机器和语言有关。,定义1.2 如果存在两个正常数c和n0，对于所有的nn0，|f(n)|c|g(n)|则记作f(n)=(g(n).因此，当说一个算法具有O(g(n)的计算时间时，指的是如果此算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个上界函数，f(n)的数量级就是g(n)。,定义1.1：算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间度量记作:T(n)O(f(n)随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。,证明：取n0=1,当n=n0时，利用A(n)的定义和 一个简单的不等式，有取c=|am|+.+|a0|定理得证.事实上，只要将n0取得足够大，可以证明只要c是比|am|大的任意一个常数，此定理都成立。,定理1.1 若A(n)=amnm+a1n+a0是一个m次多项式，则A(n)=O(nm)。,此定理表明，变量n的固定阶数为m的任一多项式，与此多项式的最高阶nm同阶，因此计算时间为m阶的多项式的算法，其时间都可用O(nm).例如，若一个算法有数量级为c1nm1,c2nm2,cknmk 的k个语句，则此算法的数量级就是 c1nm1+c2nm2+cknmk 由定理1.1，它等于O(nm),其中m=maxmi|1i k,例子：假设有解决同一个问题的两个算法，它们有n个输 入，分别要求n2和nlogn次运算。,定义1.3 如果存在两个正常数c和n0,对于所有n n0,有|f(n)|c|g(n)|则记为f(n)=(g(n)。定义1.4 如果存在两个正常数c1,c2,和n0,对于所有的n n0,有 则记为f(n)=(g(n)。一个算法的f(n)=(g(n)意味着该算法在最好和最坏情况下的计算时间就一个常因子范围内而言是相同的。,五、算法分类（按时间）多项式时间算法：凡可用多项式来对其计算时间界限的算法。指数时间算法：计算时间用指数函数界限的算法。,以下六种计算时间的多项式时间算法是最为常见的，其关系为：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间算法一般有O(2n)、O(n!)和O(nn)等。其关系为 O(2n)O(n!)O(nn),注意：当数据集的规模很大时，要在现代计算机上运行具有比O（nlogn)复杂度高的算法往往是很困难的。,六、最好、最坏和平均情况以顺序检索为例,第二章 分治法2.1 方法概述,一、基本思想 1、设计思想：将整个问题分成若干个小问题后,分而治之。2、适用条件：问题规模很大；可以分成若干个与原问题性质相同的子问题，并可以分别求解。子问题的解通过整合可以得到原问题的解。3、设计方法：使用递归策略。,4、设计步骤(1)分解：将原问题分解为若干个相互独立、与原问题形式相同的子问题；(2)求解：若子问题容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决；(3)合并：将已求解的各个子问题的解，逐步合并以得到原问题的解。,二、分治法的算法设计模式Divide-and-Conquer(n)/n为问题规模1if n=n0/n0 为可解子问题的规模2then 3 4 解子问题5 return(子问题的解)64for i 1 to k/分解为k个子问题5 do yi Divide-and-Conquer(|Pi|)/递归解决Pi6 T MERGE(y1,y2,.,yk)/合并子问题7 return T,递归过程,注意：分治法可以用递归实现，也可以用循环实现。,其中：其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。算法MERGE(y1,y2,.,yk)是该分治法中的合并子算法，用于将P的子问题P1,P2,.,Pk的相应的解y1,y2,.,yk合并为P的解。,时间复杂性分析：,其中，T(n)是输入规模为n的Divide-and-Conquer的时间，g(n)是对足够小的输入规模能直接计算出答案的时间，f(n)是MERGE的时间。,倘若所分成的两个子问题的输入规模大致相等，则Divide-and-Conquer总的计算时间可以用下面的递推关系来表示：(n足够小)(否则),2.2 二 分 检 索,一、问题描述 已知一个按非降次序排列的元素表a1,a2,an,要求判定某给定元素x是否在该表中出现。若是，则找出x在表中的位置，并将此下标值赋给变量j；若非，则将j置成0。,对于I2，通过比较x和ak容易得到解决。如果x=ak,则j=k且不需再对I1和I3求解；否则，在I2 子问题的j=0，此时若xak,只有I3留待求解，在I1子问题中的j=0。在ak作了比较之后，留待求解的问题（如果有的话）可以再一次使用分治法来求解。如果对所求解的问题（或子问题）所选的下标k都是其元素的中间元素下标（例如，对于I，k=(n+1)/2）,则所产生的算法就是通常所说的二分检索。,三、二分检索算法 算法2.3 二分检索/给定一个按非降次序排列的元素数组A(1:n),n1,判 断x是否出现。若是，置j，使得x=A(j),若非，j=0/BINSEARCH(A,n,x)1 low 12 high n,3 while lowhigh，数组A中没有找到x，返回j04 do5 6/取处于low和high之间的中间值7 if x=Amid/找到值为x的元素，mid即为其下标，返回mid8 thenreturn mid9 else if x Amid/如果x Amid，则x可能位于low与mid之间，10/否则x可能位于mid与high之间11 then high mid-112 else low mid+113 14 retrun 0,非递归形式,四、算法的证明假定在A9中顺序存放着以下9个元素：-15，-6，0，7，9，23，54，82，101。要求检索下列x的值：101，-14和82是否在A中出现。,从算法中可以看到,所有的运算基本上都是进行比较和数据传送，前两条是赋值语句,频率计数均为1。在while循环中，我们集中考虑循环的次数，而其他运算的频率计数显然与这些元素比较运算的频率计数具有相同的数量级，找到这九个元素中的每一个所需的元素循环的次数如下：,五、时间复杂性分析(1)(log n)(log n)(log n)(log n)(log n),分析：对于A中的n个数，如果x在A中出现，则是成功检索，所以成功检索共有n种情况，而不成功的检索，x将取n+1个区间中的不同值，因此在计算出x在这2n+1种情况下的执行时间后，就可以求出其在各种情况下的时间复杂性了。,例子：A：（1）（2）（3）（4）（5）（6）（7）（8）（9）元素：-15-6 0 7 9 23 54 82 101 比较次数：3 2 3 4 1 3 2 3 4,成功检索的比较次数是25/92.77。不成功检索有10种，如果xA（1）,A(1)xA(2),A(2)xA(3),A(5)xA(6),A(6)xA(7),A(7)xA(8)，为了判断x不在A中，算法要比较3次，而其余的情况要比较4次，因此一次不成功检索的元素平均比较次数就是（3+3+3+4+4+3+3+3+4+4）/10=3.4。由于算法的执行过程实质上是x与一系列中间元素A（mid）的比较过程，所以可以用一个二元比较树来描述。,二元比较树：（1）此树的结点由内结点和外结点组成；（2）每个内结点表示一次元素比较，用圆形结点表示，在以元素比较为基础的二分检索中，每个内结点存放一个mid值；（3）外结点用方形结点表示，在二分检索中它表示一次不成功的检索；（4）x如果在A 中出现，则算法就在一个圆形结点处结束，该结点将指出x在A中的下标；x如果不在A 中出现，则算法就在一个方形结点处结束，如图所示。,证明：考察以n个结点描述BINSRCH执行过程的二元比较树，所有成功检索都在内部结点处结束，而所有不成功的检索都在外部结点处结束。由于2k-1n2k，因此所有的内部结点在1，2，3，k级，而所有的外部结点在k,k+1级（注意：根在1 级）。即是，成功检索在i级终止所需要的元素比较次数是i,而不成功检索在i级外部结点终止的元素比较数是i-1.因此定理得证。,定理2.1 若n在区域2k-1,2k)中，则对于一次成功的检索，BINSRCH 至多作k次比较，而对于一次不成功的检索，或者作k-1次比较或者作k次比较。,由此：最坏情况下的成功检索和不成功检索的计算时间是（logn）,最好情况下的成功检索在根结点处到达，时间是（1），而最好情况的不成功检索要logn次元素比较，所以时间是（logn）。由于外部节点都在k和k+1级，因此，每种不成功检索的时间都是（logn），故平均情况下不成功检索的计算时间是（logn）。,E=I+2n(1)令S(n)是成功检索的平均比较数，则 S（n)=I/n+1(2),平均情况下成功检索的时间复杂性分析：设根到所有内部结点的距离之和称为内部路径长度I，由根到所有外部结点的距离之和称为外部路径长度E，可以证明：,为什么要+1,令U（n)是不成功检索的平均情况比较数，而任何一个外部结点所需要的比较数是由根到该结点路径的长度，由此得：U(n)=E/(n+1)(3)利用（1）-（3）可以得到：S(n)=(1+1/n)U(n)-1因此：平均情况下成功检索的时间复杂性为：(log n)。,五、一种二分检索的变形BINSEARCH1。BINSEARCH1的while循环中x和Amid之间只用作一次比较。,BINSEARCH1(A,n,x,j)1 low 12 high n+13 while low high4do56 mid(low+high)/27 if(x Amid)/在循环中只比较一次8 then high mid9else lowmid10 11 if x=Alow12 then j low/x出现13 else j=0/x不出现14 return j,BINSEARCH和BINSEARCH1相比较可看出，对于任何一种成功的检索，BINSEARCH1平均要比BINSEARCH多作 次比较。BINSEARCH1的最好、平均和最坏情况时间对于成功和不成功的检索都是。,六、以比较为基础检索的时间下界 1.什么是以比较为基础的检索算法 检索一给定元素x是否在A中出现。如果只允许进行元素间的比较而不允许对它们实施运算，在这种条件下所设计的算法都称为是以比较为基础的算法。2.二分检索是以比较为基础的检索算法中最坏情况下的最优算法.,一、直接求最大、最小元素算法2.5 直接找最大和最小元素maxmin(A,n)/将A(1:n)中的最大元素置于max，最小元素置于min/1 max A12 min A1;3 for i 2 to n4 do5 6 if max Ai 7 then min Ai8,2.3 找最大和最小元素,时间复杂性分析：STRAITMAXMIN在最好、平均和最坏情况下均需要作2(n-1)次元素比较。,如果稍做修改：用下面的语句代替for循环中的语句：if A(i)max then maxA(i)else if A(i)min then minA(i)endif endif 最好情况将在元素按递增次序排列时出现，元素比较数是n-1；最坏情况将在递减次序时出现，元素比较是 2（n-1）；至于在平均情况下,A(i)将有一半的时间比max大，因此平均比较数是3/2(n-1)。,二、用分治法求最大、最小元素 1、问题分析 使用分治策略设计是将任一实例I=(n，A(1)，A(n)分成一些较小的实例来处理，例如，可以把分成两个这样的实例I1=(n/2，A(1)，A(n/2)和=(n-n/2,A(n/2+1),A(n)。如果()和（）是中的最大和最小元素，则（）等于（）和（）中的大者，（）等于（）和（）中的小者。如果只包含一个元素，则不需要作任何分割直接就可得到其解。,2.算法算法.递归求取最大和最小元素float An;maxmin（i,j,fmax,fmin）/最大和最小元素赋给fmax和fmin1 if i=j 2 then3 4 fmax Ai;5 fmin Ai;,7 else if i=j-18 then if AiAj 9 then10 11 fmax Aj；12 fmin Ai13 14 else 15 16 fmax Ai;17 fmin Aj;18,19 else 20 21 mid(i+j)/2;22 maxmin(i，mid，lmax，lmin)23 maxmin(mid+1，j，rmax，rmin）24 if lmax rmax25 then fmax lmax;26 else fmax rmax27 if lmin rmin28 then fmin rmin;29 else fmin lmin;30,递归调用,利用层次分析法分析此递归调用过程。（要求掌握）,考虑如下例子：A：（1）（2）（3）（4）（5）（6）（7）（8）（9）22 13-5-8 15 60 17 31 47,?,讨论：以上算法是否是最优的？1）递归带来的额外的空间开销。2）当元素A(i)和A(j)的比较时间i和j的比较时间相差不大时，过程maxmin并不可取。,因此：当n是的幂时，3n/2-2是最好，平均及最坏情况的比较数,和直接算法的比较数n相比，它少了。可以证明，任何一种以元素比较为基础的找最大和最小元素的算法，其元素比较下界均为 次。,为说明问题，假设元素比较与i和j间的比较时间相同，又设maxmin的频率计数为C(n)，n=2k，,k是某个正整数，并且对前两种情况，用ij-1来代替i=j和i=j-1这两次比较，这样，只用对i和j-1作一次比较就足以实现被修改过的语句。于是maxmin频率计数 C(n)=n=2 n2,?,解此关系式可得 C(n)=2C(n/2)+3=4C(n/4)+6+3=2k-1C(2)+=2k+3*2k-1-3=5n/2-3,分析：STRAITMAXMIN的比较数是3(n-1)(包括实现for循环所要的比较)。尽管它比5n/2-3大些，但由于递归算法中i，j，fmax，fmin进出栈所带来的开销，因此maxmin在这种情况下反而比STRAITMAXMIN还要慢些。,根据以上分析可以得出结论：如果A的元素间的比较远比整数变量的比较代价昂贵，则分治方法产生效率较高（实际上是最优）的算法；反之，就得到一个效率较低的程序。因此，分治策略只能看成是一个较好的然而并不总是能成功的算法设计指导。,2.4斯特拉森矩阵乘法,一、一般的矩阵乘法 设C=A*B,则利用常规方法计算，所需时间是,二、分治法求矩阵乘法 设n=2k，则可以将两个矩阵的乘法做如下划分：,其中：C11=A11B11+A12B21 C12=A11B12+A12B21 C21=A21B11+A22B21 C22=A21B12+A22B22可以证明:C=AB=,三.斯特拉森矩阵乘法 斯特拉森矩阵乘法的设计思想:增加加法的次数,减少乘法的次数.,如果分块矩阵的级大于2,则可以继续将这些子矩阵分成更小的方阵,直至每个方阵只含有一个元素,以至可以直接计算其乘积.时间复杂性分析:n 2 n2则T(n)=O(n3),先用七个乘法和十个加（减）法来算出以下的P-VP=(A11+A22)(B11+B22)，Q=(A21+A22)B11R=A11(B12-B22)，S=A22(B21-B11)T=(A11+A12)B22，U=(A21-A11)(B11+B12)V=(A12-A22)(B21+B22)然后用8个加减法算出这些 Cij C11=P+S-T+VC12=R+TC21=Q+SC22=P+R-Q+U,以上共用了7次乘法,18次加减法.n 2 n2 其中a和b是常数。解：T(n)=7T(n/2)+an2=72T(n2/4)+(7/4)an2+an2=73T(n3/8)+(7/4)2an2+(7/4)an2+an2=an2(1+(7/4)+(7/4)2+.+(7/4)k-1)+7kT(1)cn2(7/4)logn+7logn(1),因为：7logn=nlog7 cn2(7/4)logn=cnlog4*nlog7-log4=cnlog4+log7-log4=cnlog7因此上式(1)=cnlog7+7logn=cnlog7+nlog7=(c+1)nlog7=O(nlog7)O(n2.81).,注意：（1）当n小于120时，斯特拉森矩阵乘法与普通的乘法没有太大的区别。（2）斯特拉森矩阵乘法的核心就是降低乘法的次数而增加加法的次数，那么是否可以使乘法由7次降低为6次呢？已经证明7次是必须的，这一方面改进只能从更高维数如3*3，或4*4并用递归分治的合并方法来实现，现在可以达到o(n2.495364).,一、基本方法1例子：背包问题：已知有n种物品和一个容量大小为M的背包，每种物品i的容量为wi。假定将物品i的一部分xi放入背包就会得到pixi的效益，这里，0 xi1，pi0。采用怎样的装包方法才会使装入背包物品的总效益最大呢？显然，由于背包容量是M，因此，要求所有选中要装入背包的物品总容量不得超过M。如果这n件物品的总容量不超过M，则把所有物品装入背包自然获得最大效益。如果这些物品容量的和大于M，则在这种情况下该如何装包呢？,第三章贪心方法31方法概述,例:考虑下列情况下的背包问题：n=3，M20，(25，24，15）,=(18,15,10)。其中的四个可行解是:（1/2,1/3,1/4）16.5 24.25（1，2/15，0）20 28.2（0，23，1）20 31（0，1，12）20 31.5在这些可行解中，如何得到最优解，正是贪心方法要解决的问题。,2、适用条件：（1）有n个输入；（2）它的解就由这n个输入的某个子集组成；（3）这个子集必须满足一定的约束条件-可行解；（4）可行解一般不止一个，但是要求的是最优解即使目标函数取得极值的解。,3有关概念（1）约束条件：把子集必须满足的基本条件称为约束条件。（2）可行解：把满足约束条件的子集称为该问题的可行解。（3）目标函数：（可行解一般来说是不唯一的）为了衡量可行解的优劣，事先也给出了一定的标准，这些标准一般以用函数形式给出，这些函数称为目标函数。（4）最优解：那些使目标函数取极值（极大或极小）的可行解，称为最优解。,二、贪心方法的算法设计模式GREEDY（A，n）/An 包含n个输入/1 solution/将解向量solution初始化为空/2 for i1 to n do3 xSELECT（A）/按最优量度标准在A中选择一个输入4 if FEASIBLE（solution，x）then solutionUNION（solution，x）return（solution）,三、设计要点：选择能产生问题最优解的最优量度标准是使用贪心法设计求解的核心问题。,3.2 背包问题一、问题的描述 背包问题：已知有n种物品和一个容量为M的背包，每种物品i的容量为wi，效益为pi，假定将物品i的一部分xi放入背包就会得到pixi的效益，这里，0=xi=1，pi0。采用怎样的装包方法才会使装入背包物品的总效益最大呢？显然，由于背包容量是M，因此，要求所有选中要装入背包的物品总容量不得超过M。如果这n件物品的总容量不超过M，则把所有物品装入背包自然获得最大效益。如果这些物品容量的和大于M，则在这种情况下该如何装包呢？,由以上叙述，可将这个问题形式描述如下：约束条件：目标函数：其中：0 xi 1,pi0,wi0,0 in M背包的容量n物品种类wi第i物品的容量pi第i种物品价值 显然，满足约束条件的任一集合 是一个可行解，使目标函数取最大值的可行解是最优解。,例31考虑下列情况下的背包问题：n=3，M20，（pl，p2，p3）（25，24，15），（w1，w2，w3）=(18,15,10)。其中的四个可行解是:（x1，x2，x3）（12，13，14）16.5 24.25（1，2/15，0）20 28.2（0，23，1）20 31（0，1，12）20 31.5在这四个可行解中，第个解的效益值最大。下面将可看到，这个解是背包问题在这一情况下的最优解。,二、问题的分析 为了获取背包问题的最优解，必须要把物品放满背包。由于可以只放物品i的一部分到背包中，因此这一要求是可以达到的。如果用贪心策略来求解背包问题则正如31节中所说的一样，首先要选出最优的量度标准。以下不妨分三种情况进行分析：(1)取效益值作为量度标准。即每装入一件物品就使背包获得最大可能的效益值增量。在这种量度标准下的贪心方法就是按效益值的非增次序将物品一件件放到背包中去。如果正在考虑中的物品放不进去，则可只取其一部分来装满背包。,量度标准选取,此种选择策略得到的解，总效益值是28.2。它是一个次优解。由此例可知，按物品效益值的非增次序装包不能得到最优解。为什么上述贪心策略不能获得最优解呢？原因在于，背包可用容量消耗过快。由此，很自然地启发我们用容量作为量度，让背包容量尽可能慢地被消耗。,（2）用容量作为量度标准 在这种量度标准下的贪心方法就是按物品容量的非降次序来把物品放入背包。例3.1的解就是使用这种贪心策略得到的，它仍是一个次优解。这种策略也只能得到次优解，其原因在于容量虽然慢慢地被消耗，但效益值没能迅速地增加。以上策略也只能得到次优解，其原因在于容量虽然慢慢地被消耗，但效益值没能迅速地增加。这又启发我们应采用在效益值的增长速率和容量的消耗速率之间取得平衡的量度标准。即每装入一件物品应使它占用的每一单位容量获得当前最大的效益。,三、算法设计算法3.3 背包问题的贪心算法,（3）用效益和容量的比值作为量度标准。(即)这就需使物品的装入次序按 比值的非增次序来考虑，在这种策略下的量度是已装入物品的累计效益值与所用容量之比。其量度标准是每次装入要使累计效益值与所用容量的比值有最多的增加或最少的减小（第二次和以后的装入可能使此比值减小）。将此贪心策略应用于例3.l的数据，得到解。,Knapsack(ElemtypeW pn,ElemtypeP wn,float yn,ElemtypeW C,int n)/pn和wn分别含有按piwi，pi1wi+1排序的n件物品的效益值和容量。M是背包的容量大小，而yn是解向量/1 for i1 to n 2 do yi0;/将解向量初始化为0；3 cu C;/cu是背包中剩余的空间；4 for i1 to n 5 do/依次考察下一个物品是否可以放入背包；6 if wi cu break;/物品i无法全部放入背包,退出for循环；7 then yi1;8 cu cu-wi;9 10 if in 11 then yi cu/wi;/不能完全装入的物品的部分装入量,量度标准,值得指出的是：（a）如果把物品事先按效益值的非增次序或容量的非降次序分好类，再使用以上算法就可分别得到量度标准为（2）或（3）（使每次效益增量最大或使容量消耗最慢）的解。(b)该算法的解的形式为（1，.1,x，0，0）,其中x在0，1。由背包问题量度选取的研究可知，选取最优的量度标准实为用贪心方法求解问题的核心。,小结：贪心方法设计步骤：找出问题的约束条件和目标函数。选取合适的量度标准。按照“贪心方法的算法设计模式”的步骤进行算法设计.,四、算法分析 如果将物体事先按Pi/wi的非增次序分好类，则过程Knapsack就得出这一策略下背包问题的解。如果将物品分类的时间不算在内，则此算法所用时间为O（n）。,五、算法的证明 证明的基本思想是：把这贪心解与任一最优解相比较，如果这两个解不同，就去找开始不同的第一个xi，然后设法用贪心解的这个xi去代换最优解的那个xi，并证明最优解在分量代换前后的总效益无任何变化。反复进行这种代换，直到新产生的最优解与贪心解完全一样，从而证明了贪心解是最优解。,掌握,定理31 如果p1/wl p2/w2 pn/wn。则算法GREEDYKNAPSACK对于给定的背包问题实例生成一个最优解。证明：设X=（x1，xn）是GREEDYKNAPSACK所生成的解。如果所有的xi等于1，显然这个解就是最优解。于是，设j是使xj 1的最小下标。由算法可知，对于1ij，xi=1；对于jin，xi=0。对于j，0 xj1。,如果X不是一个最优解，则必定存在一个可行解Y=(y1,y2,yn),使得；不失一般性，可以假定wiyi=M。设k是使得yk xk的最小下标。显然，这样的k必定存在。由上面的假设，可以推得ykj分别得证明：若k xk，显然有wiyiM,与Y是可行解矛盾。若yk=xk,与假设yk xk矛盾，故ykj，则wiyiM,这是不可能的。现在，假定把yk增加到xk，那末必须从（yk1，yn）中减去同样多的量，使得所用的总容量仍是M。,这导致一个新的解Z=（z1，z2，,zn），其中zi=xi,1ik,且，因此，对于Z有：,若 0时，则Y不是最优解，此与假设矛盾，所以不可能，即=0。当=0时，则Z=X或ZX，则若Z=X，则pizi=piyi，由于Y是最优解，因此Z也是最优解，X也是最优解。若ZX，重复上面的讨论，用Z代替Y，则又可求得相应的 0，重复以上过程，直到X=Z为止，可得X为最优解。,讨论：,3.3带有限期的作业排序 一、问题的描述 假定只能在一台机器上处理n个作业，每个作业均可在单位时间内完成；又假定每个作业i都有一个截止期限di0（它是整数），当且仅当作业i在它的期限截止以前被完成时，则获得pi0的效益，求具有最大效益值的可行解,也就是最优解。分析：约束条件：每个作业均要在截止期限前完成。目标函数：例子：n=4,(p1,p2,p3,p4)=(100,10,15,20)和(d1,d2,d3,d4)=(2,1,2,1)。,可行解 处理顺序 效益值（1）1 100（2）2 10（3）3 15（4）4 20（1，2）2，1 110（1，3）1，3或3，1 115（1，4）4，1 120（2，3）2，3 25（3，4）4，3 35,二、问题的分析 最优量度标准：目标函数pi作为量度，即按照pi的非增次序来考虑这些作业。使用这一量度，下一个要计入的作业将是使得在满足所产生的J是一个可行解的限制条件下让pi得到最大增加的作业。,应用以上的量度标准：开始时J=0，由于作业1有最大效益且J=1是一个可行解，于是把作业1计入J。下一步考虑作业4，J=1，4也是可行解。然后考虑作业3，因为1，3，4不是可行解，故作业3被舍弃。最后考虑作业2，由于1，2，4也不可行，作业2被舍弃。最终所留下的是效益值为120的解J=1，4。它是这个问题的最优解。,三、算法的粗略描述 GREEDY-JOB(D,J,n)/作业按p1p2pn的次序输入，它们的期限值Di1,1in,n1.J是在它们的截止期限前完成的作业的集合/1 J12 for i2 to n do3 if Ji的所有作业都有能在它们的截止期限前完成 then JJi4 endif5,由前面贪心方法的算法设计模式得到,J是一个作业的集合，而不是调度表,四、算法的证明定理3.2 以上算法所描述的贪心方法对于作业排序问题总是得到一个最优解。,思路：J是由贪心方法所选择的作业的集合；I是一个最优解的作业集合。可证明J和I具有相同的效益值，从而J也是最优的。（I,J是作业的集合，而不是作业的调度表）,证明：假定（1）IJ，因为若I=J，则J即为最优解。（2）如果I J，则I就不可能是最优的。（3）由贪心法的工作方式也排斥了J I。,因此，至少存在这样的两个作业a和b，使得aJ且a I，bI且b J。设a是使得aJ且a I的一个具有最高效益值的作业。由贪心方法可以得出，对于在I中又不在J中的所有作业b，都有papb。这是因为若pb pa，则贪心方法会先于作业a考虑作业b并且把b计入到J中去。,设SI和SJ分别是I和J的可行调度表。（调度表与作业集的区别）(1)设i是既属于J又属于I的一个作业,把他们调换到相同的时刻去调度，且尽量将调度时间往后移。,设i在SI中在t到t+1时刻被调度，而在SJ中则在t到t+1时刻被调度。如果tt，则可以将SI中t，t+1时刻所调度的那个作业（如果有的话）与i相交换。如果J中在t，t+1时刻没有作业被调度，则将i移到t，t+1调度。所形成的这个调度表也是可行的。如果tt，则可在和SI中作类似的调换。,（2）对于I,J中不同的作业，则以J为标准，将其中不属于I的那些作业找出，设a是这样的作业，它在SJ 中 时刻被调度。设作业b在I中的这一时刻被调度。根据对a的选择 在SI 的 时刻去掉作业b而去调度作业a，这就给出了一张关于作业集合I=I-ba可行的调度表。,显然I的效益值不小于I的效益值，并且I比I少一个与J不同的作业。重复使用上述的转换，将使I能在不减效益值的情况下转换成J，因此J也必定是最优解，证毕。,五、算法的实现 考虑对于一个给定的J，如何确定它是否为可行解的问题，一个明显的方法是检验J中作业的所有可能的排列。对于任一种次序排列的作业序列，判断这些作业是否能在其限期前完成。,J是作业集，不是调度表,假定J中有k个作业，这就需要检查k！个排列。对于所给出的一个排列=i1i2i3ik，由于完成作业ij（1jk）的最早时间是j，因此，只要判断出排列中的每个作业的dijj，就可得知是一个允许的调度序列，从而J就是一个可行解。反之，如果排列中有一个dijj，则是一个行不通的调度序列，因为至少作业ij不会在它的限期前完成，故必须去检查J的另外形式的排列。事实上，对于J的可行性可以通过只检验J中作业的一种特殊的排列来确定，这个排列是按期限的非降次序来完成的。,定理3.3 设J是k个作业的集合，=i1i2i3ik是J中作业的一种排列，它使得di1di2dik。J是一个可行解，当且仅当J中的作业可以按照的次序而又不违反任何一个期限的情况下来处理。(说明了什么),证明：现证，若J是可行解，则表示可以处理这些作业的一种允许的调度序列。由于J可行，则必存在，使得 假设，那末，令a是使得 的最小下标。设，显然ba。在中将 与 相交换，因为，故作业可依新产生的排列 的次序处理而不违反任何一个期限。连续使用这一方法，就可将转换成且不违反任何一个期限。定理得证。,算法设计思路：首先将作业按照效益值的非增次序排列，然后试着将作业逐个与当前的部分可行解合并，检查是否可产生新的可行解，（注意当前的部分可行解已经按期限值的非降次序排列），其方法是在部分可行解中，看能否找到新作业的合适的位置，使加入了新的作业后，其期限值仍按非降次序排列，且每个作业均在其截止期限前完成。,算法3.4 带有限期和效益的单位时间的作业排序贪心算法GreedyJob(int n,int d,int,体现了量度标准,11 12if dJrdi and di r/判断此作业是否可以插入J；13then14 for j k to r+1/j是递减的15 do/将第k到第r+1个作业依次后移一位以插入新的作业；16 Jj+1 Jj;17 18Jr+1 i;/将作业插入位置r+1；19k k+1;/记入J的作业数加1;20 21 22return k;/返回记入J中的作业数。,七、一种更快的实现 通过使用不相交集合的UNION与FIND算法以及使用一个不同的方法来确定部分解的可行性，可以把JS的计算时间由O（n2）降低到数量级相当接近于O(n)。,六、时间复杂性分析 经过分析知道，算法JS所需要的总时间是O（sn）。由于sn(s为包含在解中的作业数)，因此JS的最坏计算时间为O（