高中数学 第11章 算法初步 11.1 算法概念和例子课件 湘教版必修5

《高中数学 第11章 算法初步 11.1 算法概念和例子课件 湘教版必修5》由会员分享，可在线阅读，更多相关《高中数学 第11章 算法初步 11.1 算法概念和例子课件 湘教版必修5（197页珍藏版）》请在金锄头文库上搜索。

1、例子例子: :给定两个正整数给定两个正整数m m和和n,n,求它们的最大公因子求它们的最大公因子算法算法: :欧几里德算法欧几里德算法输入输入: :正整数正整数m m、n n输出：输出：m m和和n n的最大公因子的最大公因子11.1 11.1 算法概念和例子算法概念和例子一、什么是算法及其与程序的区别一、什么是算法及其与程序的区别S1:S1:保证保证m=n,m=n,如果如果mnmn，则，则m m、n n的值互换，否则转的值互换，否则转S2.S2.S2:S2:求余数。令求余数。令r=m mod n,r=m mod n,（0=rn)0=rn)S3:S3:判断余数判断余数r r是否为是否为0 0。

2、如果。如果r r是是0 0，则算法终止，则算法终止，n n为答为答案，否则转案，否则转S4.S4.S4:S4:置换。即置换。即m mn,nn,nr r, ,转转S2.S2.什么是算法？什么是算法？ 它是一组它是一组有穷规则有穷规则的集合，它规定了解决某一特定类的集合，它规定了解决某一特定类型问题的一系列运算。型问题的一系列运算。 二、算法的特征二、算法的特征 1 1、确定性、确定性 2 2、能行性、能行性 3 3、输入、输入 4 4、输出、输出 5 5、有穷性、有穷性: :一个算法总是在有限步之后结束，且每一步一个算法总是在有限步之后结束，且每一步都可在有穷时间内完成都可在有穷时间内完成. .

3、 算法与程序的区别：算法与程序的区别： 程序：与某种语言有关，能直接在机器上运行。程序：与某种语言有关，能直接在机器上运行。 算法：与特定的语言无关，可用任何语言实现算法：与特定的语言无关，可用任何语言实现 ，甚至，甚至可以用自然语言实现，但是一般为了避免二义性，本书可以用自然语言实现，但是一般为了避免二义性，本书采用类采用类C C语言描述。语言描述。 一个算法总是在执行了有穷步骤的运算后终止，否则就一个算法总是在执行了有穷步骤的运算后终止，否则就一个算法总是在执行了有穷步骤的运算后终止，否则就一个算法总是在执行了有穷步骤的运算后终止，否则就是一个计算过程。是一个计算过程。是一个计算过程。是一

4、个计算过程。 有穷性与有效性的关系有穷性与有效性的关系：三、评价算法的标准三、评价算法的标准 有穷性是对算法的基本要求，如果一个算法要能使用，有穷性是对算法的基本要求，如果一个算法要能使用，必须具有有效性。有效性是指算法在必须具有有效性。有效性是指算法在规定的规定的时间里终止。时间里终止。时间复杂性和空间复杂性时间复杂性和空间复杂性1.2 1.2 算法设计的步骤算法设计的步骤一、问题的描述一、问题的描述例例: :货郎担问题货郎担问题 设售货员在一天内要到设售货员在一天内要到5 5个城市去推销货物，已知从一个个城市去推销货物，已知从一个城市到其他城市的费用，求总费用最少的路线。给出的城市到其他城

5、市的费用，求总费用最少的路线。给出的信息主要有五个城市的关系图及相应的费用矩阵。信息主要有五个城市的关系图及相应的费用矩阵。二、模型的拟制二、模型的拟制 建模阶段至少要考虑以下两个基本问题：建模阶段至少要考虑以下两个基本问题： 1 1）最适合于这个问题的数学结构是什么？）最适合于这个问题的数学结构是什么？ 2 2）有没有已经解决了的类似问题可供借鉴？）有没有已经解决了的类似问题可供借鉴？ 在模型建立好了以后，应该依据所选定的模型对在模型建立好了以后，应该依据所选定的模型对问题重新陈述问题重新陈述, ,并考虑下列问题并考虑下列问题: : (1)(1)模型是否清楚地表达了与问题有关的所有重要模型是

6、否清楚地表达了与问题有关的所有重要的信息的信息? ?(2)(2)模型中是否存在与要求的结果相关的数学量模型中是否存在与要求的结果相关的数学量? ?(3)(3)模型是否正确反映了输入、输出的关系模型是否正确反映了输入、输出的关系? ?(4)(4)对这个模型处理起来困难吗？对这个模型处理起来困难吗？152434724335211 对于货郎担问题，其数学模型是带权图，与此图相关的对于货郎担问题，其数学模型是带权图，与此图相关的是费用矩阵。是费用矩阵。以货郎担问题为例：采用枚举法。以货郎担问题为例：采用枚举法。分析：分析：三、算法的详细设计三、算法的详细设计 算法的详细设计是指设计求解某个具体问题的算

7、法的详细设计是指设计求解某个具体问题的一系列步骤，并且这些步骤可以通过计算机的各种一系列步骤，并且这些步骤可以通过计算机的各种操作来实现。操作来实现。输入：城市数目输入：城市数目n;n;费用矩阵费用矩阵C=(C=(c cijij) )n n*n*n输出：旅行路线输出：旅行路线TOUR;TOUR;最小费用最小费用MINMINSalesman (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

8、,T)是由费用矩阵是由费用矩阵c及路线及路线T(p)所算得的总费用所算得的总费用 if cost(T(p)=nn=n0 0时，利用时，利用A(nA(n) )的定义和的定义和 一个简单的不一个简单的不等式，有等式，有取取c=|ac=|am m|+|+.+|a.+|a0 0| | 定理得证定理得证. .事实上，只要将事实上，只要将n n0 0取得足够大，可以证明只要取得足够大，可以证明只要c c是比是比|a|am m| |大的大的任意一个常数，此定理都成立。任意一个常数，此定理都成立。定理定理1.1 1.1 若若A(nA(n)=)=a am mn nm m+ + a+ a1 1n+ an+ a0

9、0是一个是一个m m次多项式，则次多项式，则A(nA(n)=)=O O(n(nm m) )。 此定理表明，此定理表明，变量变量n n的固定阶数为的固定阶数为m m的任一多项式，的任一多项式，与此多项式的最高阶与此多项式的最高阶n nm同阶，同阶，因此计算时间为因此计算时间为m m阶的多项阶的多项式的算法，其时间都可用式的算法，其时间都可用O(nO(nm).).例如，若一个算法有数例如，若一个算法有数量级为量级为c c1 1n nm1m1, c, c2 2n nm2m2, , , c ck kn nmkmk 的的k k个语句，则此算法的数个语句，则此算法的数量级就是量级就是 c c1 1n nm

10、1m1 +c +c2 2n nm2m2+ + +c ck kn nmkmk 由定理由定理1.11.1，它等于，它等于O(nO(nm m),),其中其中m=maxmm=maxmi i|1|1i k n2nlognn=1024104857610240时间（n=1024)1.05s0.01sn=2048419430422528时间（n=2048)4.2s0.02s例子：假设有解决同一个问题的两个算法，它们有例子：假设有解决同一个问题的两个算法，它们有n n个输个输 入，分别要求入，分别要求n n2 2和和nlognnlogn次运算次运算。定义定义1.3 1.3 如果存在两个正常数如果存在两个正常数c

11、 c和和n n0 0, ,对于所有对于所有n nn n0 0, ,有有 | |f(nf(n)| )| c|g(nc|g(n)|)| 则记为则记为f(nf(n)=)=(g(n(g(n)。定义定义1.4 1.4 如果存在两个正常数如果存在两个正常数c1 ,c2,c1 ,c2,和和n n0 0, ,对于所有的对于所有的n n n n0 0, ,有有 则记为则记为f(nf(n)=)=(g(n(g(n)。 一个算法的一个算法的一个算法的一个算法的f(nf(nf(nf(n)=)=)=)=(g(n(g(n(g(n(g(n)意味着该算法在最好和最坏情意味着该算法在最好和最坏情意味着该算法在最好和最坏情意味着该

12、算法在最好和最坏情况下的计算时间就一个常因子范围内而言是相同的。况下的计算时间就一个常因子范围内而言是相同的。况下的计算时间就一个常因子范围内而言是相同的。况下的计算时间就一个常因子范围内而言是相同的。五、算法分类（按时间）五、算法分类（按时间） 多项式时间算法：凡可用多项式时间算法：凡可用多项式多项式来对其计算时间界限的算法。来对其计算时间界限的算法。 指数时间算法：计算时间用指数时间算法：计算时间用指数函数指数函数界限的算法。界限的算法。以下六种计算时间的多项式时间算法是最为常见的，其关以下六种计算时间的多项式时间算法是最为常见的，其关系为：系为： O(1) O(1) O(lognO(lo

13、gn) ) O(nO(n) ) O(nlognO(nlogn) O(n) O(n2 2) O(n) O(n3 3) )指数时间算法一般有指数时间算法一般有O(2O(2n n) )、O(nO(n!) !) 和和O(nO(nn n) )等。其关系为等。其关系为 O(2O(2n n) ) O(nO(n!) !) O(nO(nn n) ) 注意：注意：注意：注意：当数据集的规模很大时，要在现代计算机上运当数据集的规模很大时，要在现代计算机上运行具有比行具有比O O（nlognnlogn) )复杂度高的算法往往是很困难的。复杂度高的算法往往是很困难的。六、最好、最坏和平均情况六、最好、最坏和平均情况以顺

14、序检索为例以顺序检索为例第二章第二章 分治法分治法2.1 2.1 方法概述方法概述一、基本思想一、基本思想 1 1、设计思想：将整个问题分成若干个小问题后、设计思想：将整个问题分成若干个小问题后, ,分而治之。分而治之。 2 2、适用条件：、适用条件： 问题规模很大；问题规模很大； 可以分成若干个与原问题性质相同的子问题，并可以可以分成若干个与原问题性质相同的子问题，并可以分别求解。分别求解。 子问题的解通过整合可以得到原问题的解。子问题的解通过整合可以得到原问题的解。 3 3、设计方法：使用递归策略。、设计方法：使用递归策略。4 4、 设计步骤设计步骤(1)(1)分解：分解：将原问题分解为若

15、干个相互独立、与原问题形式相将原问题分解为若干个相互独立、与原问题形式相同的子问题；同的子问题； (2)(2)求解求解：若子问题容易被解决则直接解，否则再继续分解为：若子问题容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决；更小的子问题，直到容易解决； (3)(3)合并合并：将已求解的各个子问题的解，逐步合并以得到原问：将已求解的各个子问题的解，逐步合并以得到原问题的解。题的解。二、分治法的算法设计模式二、分治法的算法设计模式Divide-and-Divide-and-Conquer(nConquer(n) ) /n/n为问题规模为问题规模1 1if n = n0 if n =

16、n0 /n0 /n0 为可解子问题的规模为可解子问题的规模2 2then then 3 3 4 4 解子问题解子问题5 5 return( return( 子问题的解子问题的解 ) )6 6 4 4for i for i 1 to k 1 to k /分解为分解为k k个子问题个子问题5 5 do do yiyi Divide-and- Divide-and-Conquer(|PiConquer(|Pi|)/|)/递归解决递归解决PiPi6 6 T T MERGE(y1,y2,., MERGE(y1,y2,.,ykyk) ) /合并子问题合并子问题7 7 return Treturn T递归过

17、程递归过程注意：分治法可以用递归实现，也可以用循环实现。注意：分治法可以用递归实现，也可以用循环实现。 其中：其中其中：其中|P|P|表示问题表示问题P P的规模；的规模；n0n0为一阈值，表示为一阈值，表示当问题当问题P P的规模不超过的规模不超过n0n0时，问题已容易直接解出，不必时，问题已容易直接解出，不必再继续分解。算法再继续分解。算法MERGE(y1,y2,.,MERGE(y1,y2,.,ykyk) )是该分治法中的是该分治法中的合并子算法，用于将合并子算法，用于将P P的子问题的子问题P1 ,P2 ,.,P1 ,P2 ,.,PkPk的相应的的相应的解解y y1 1,y,y2 2,.

18、,.,y yk k合并为合并为P P的解。的解。时间复杂性分析时间复杂性分析时间复杂性分析时间复杂性分析： 其中，其中，T(nT(n) )是输入规模为是输入规模为n n的的Divide-and-ConquerDivide-and-Conquer的的时间，时间，g(ng(n) )是对足够小的输入规模能直接计算出答案是对足够小的输入规模能直接计算出答案的时间，的时间，f(nf(n) )是是MERGEMERGE的时间。的时间。 倘若所分成的两个子问题的输入规模大致相等，则倘若所分成的两个子问题的输入规模大致相等，则Divide-and-ConquerDivide-and-Conquer总的计算时间可

19、以用下面的递推关系总的计算时间可以用下面的递推关系来表示：来表示： (n(n足够小足够小) ) ( (否则否则) ) 2.2 2.2 二二 分分 检检 索索一、问题描述一、问题描述 已知一个按非降次序排列的元素表已知一个按非降次序排列的元素表a a1 1,a,a2 2, ,a an n, ,要求判定要求判定某给定元素某给定元素x x是否在该表中出现。若是，则找出是否在该表中出现。若是，则找出x x在表中的在表中的位置，并将此下标值赋给变量位置，并将此下标值赋给变量j j；若非，则将；若非，则将j j置成置成0 0。二、问题分析二、问题分析 设该问题用设该问题用I=(n, aI=(n, a1 1

20、,a,a2 2, ,a an n,x,x) )来表示，可以将它分解来表示，可以将它分解成一些子问题，一种可能的做法是，选取一个下标成一些子问题，一种可能的做法是，选取一个下标k k，由此得到，由此得到三个子问题：三个子问题：I I1 1=(k-1, a=(k-1, a1 1,a,a2 2, ,a ak-1k-1,x),I,x),I2 2=(1,a=(1,ak k,x),x)和和I I3 3=(=(n-kn-k, , a ak+1k+1, ,a an n,x,x) )。 对于对于I I2 2，通过比较，通过比较x x和和a ak k容易得到解决。如果容易得到解决。如果x= x= a ak k,

21、,则则j=kj=k且且不需再对不需再对I I1 1和和I I3 3求解；否则，在求解；否则，在I I2 2 子问题的子问题的j=0j=0，此时若，此时若xxxa ak k, ,只有只有I I3 3留待留待求解，在求解，在I I1 1子问题中的子问题中的j=0j=0。在。在a ak k作了比较之后，留待求解的作了比较之后，留待求解的问题（如果有的话）可以再一次使用分治法来求解。如果对问题（如果有的话）可以再一次使用分治法来求解。如果对所求解的问题（或子问题）所选的下标所求解的问题（或子问题）所选的下标k k都是其元素的中间元都是其元素的中间元素下标（例如，对于素下标（例如，对于I I，k=(n+

22、1)/2k=(n+1)/2）, ,则所产生的算法就是则所产生的算法就是通常所说的二分检索。通常所说的二分检索。三、二分检索算法三、二分检索算法 算法算法2.3 2.3 二分检索二分检索 /给定一个按非降次序排列的元素数组给定一个按非降次序排列的元素数组A(1:n),n1,A(1:n),n1,判判 断断x x是否出现。若是，置是否出现。若是，置j j，使得，使得x=x=A(jA(j),),若非，若非，j=0/j=0/BINSEARCH(A,n,xBINSEARCH(A,n,x) )1 low 1 low 1 12 high 2 high n n 3 3 while low=highwhile l

23、owhighlowhigh，数组，数组A A中没有找到中没有找到x x，返回，返回j j0 04 do4 do5 5 6 6 / /取处于取处于lowlow和和highhigh之间的中间值之间的中间值7 if x=7 if x=AmidAmid/找到值为找到值为x x的元素，的元素，midmid即为其下标，返回即为其下标，返回midmid8 then8 thenreturn midreturn mid9 else if x 9 else if x AmidAmid/如果如果x x AmidAmid ，则，则x x可能位于可能位于lowlow与与midmid之间，之间，1010 /否则否则x x

24、可能位于可能位于midmid与与highhigh之间之间1111 then high then high mid - 1 mid - 11212 else low else low mid + 1 mid + 113 13 14 14 retrunretrun 0 0 非递归形式非递归形式四、算法的证明四、算法的证明假定在假定在A9A9中顺序存放着以下中顺序存放着以下9 9个元素：个元素：-15-15，-6-6，0 0，7 7，9 9，2323，5454，8282，101101。要求检索下列。要求检索下列x x的值：的值：101101，-14-14和和8282是否是否在在A A中出现。中出现。

25、 X=101low high midX=-14low high midX=82low high mid19519519569714269789811199921找不到898找到找到A（1）（2） （3） （4） （5） （6） （7） （8） （9）元素-15-6079235482101比较次数323413234从算法中可以看到从算法中可以看到, ,所有的运算基本上都是进行比较和所有的运算基本上都是进行比较和数据传送，前两条是赋值语句数据传送，前两条是赋值语句, ,频率计数均为频率计数均为1 1。在。在whilewhile循循环中，我们集中考虑循环的次数，而其他运算的频率计数显环中，我们集中考

26、虑循环的次数，而其他运算的频率计数显然与这些元素比较运算的频率计数具有相同的数量级，找到然与这些元素比较运算的频率计数具有相同的数量级，找到这九个元素中的每一个所需的元素循环的次数如下：这九个元素中的每一个所需的元素循环的次数如下： 五、时间复杂性分析五、时间复杂性分析五、时间复杂性分析五、时间复杂性分析 (1) (log n) (log n) (log n) (log n) (log n) 分析：对于分析：对于A A中的中的n n个数，如果个数，如果x x在在A A中出现，则是成功检索，所中出现，则是成功检索，所以成功检索共有以成功检索共有n n种情况，而不成功的检索，种情况，而不成功的检索

27、，x x将取将取n+1n+1个区间中的个区间中的不同值，因此在计算出不同值，因此在计算出x x在这在这2n+12n+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。 不成功检索有不成功检索有1010种，如果种，如果xAxA（1 1）,A(1)xA

28、(2), ,A(1)xA(2), A(2)xA(3), A(5)xA(6),A(6)xA(7),A(7)xA(8)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 x与一系列中间元素与一系列中间元素与一

29、系列中间元素与一系列中间元素A A（midmid）的）的）的）的比较过程，所以可以用一个二元比较树来描述比较过程，所以可以用一个二元比较树来描述比较过程，所以可以用一个二元比较树来描述比较过程，所以可以用一个二元比较树来描述。二元比较树：二元比较树：二元比较树：二元比较树： （1）此树的结点由此树的结点由内结点和外结点内结点和外结点组成；组成； （2）每个内结点表示一次元素比较，用）每个内结点表示一次元素比较，用圆形结点圆形结点表示，在表示，在以元素比较为基础的二分检索中，每个内结点存放一个以元素比较为基础的二分检索中，每个内结点存放一个mid值；值； （3） 外结点用外结点用方形结点方形结点

30、表示，在二分检索中它表示一次不表示，在二分检索中它表示一次不成功的检索；成功的检索； （4）x如果在如果在A 中出现，则算法就在一个圆形结点处结束，中出现，则算法就在一个圆形结点处结束，该结点将指出该结点将指出x在在A中的下标；中的下标； x如果不在如果不在A 中出现，则算法中出现，则算法就在一个方形结点处结束，如图所示。就在一个方形结点处结束，如图所示。529713486xA(1)A(1)xA(2)A(3)xA(4)A(2)xA(3)A(6)xA(7)A(5)xA(6)A(4)xA(5)A(8)xA(9)A(7)xA(8)证明：考察以证明：考察以n n个结点描述个结点描述BINSRCHBIN

31、SRCH执行过程的二元比较树，执行过程的二元比较树，所有成功检索都在内部结点处结束，而所有不成功的检索都所有成功检索都在内部结点处结束，而所有不成功的检索都在外部结点处结束在外部结点处结束。由于。由于2 2k-1k-1n n2 2k k ，因此所有的内部结点在，因此所有的内部结点在1 1，2 2，3 3，k k级，而所有的外部结点在级，而所有的外部结点在k,k+1k,k+1级（注意：根级（注意：根在在1 1 级）。即是，成功检索在级）。即是，成功检索在i i级终止所需要的元素比较次数级终止所需要的元素比较次数是是i,i,而而不成功检索在不成功检索在i i级外部结点终止的元素比较数是级外部结点终

32、止的元素比较数是i-1.i-1.因因此定理得证。此定理得证。 定理定理2.1 2.1 若若n n在区域在区域22k-1k-1, 2, 2k k) )中，则对于一次成功的检索，中，则对于一次成功的检索，BINSRCH BINSRCH 至多作至多作k k次比较，而对于一次不成功的检索，或者作次比较，而对于一次不成功的检索，或者作k-k-1 1次比较或者作次比较或者作k k次比较。次比较。 由此：最坏情况下的成功检索和不成功检索的计算时间是由此：最坏情况下的成功检索和不成功检索的计算时间是（lognlogn）, ,最好情况下的成功检索在根结点处到达，时间是最好情况下的成功检索在根结点处到达，时间是（

33、1 1），），而最好情况的不成功检索要而最好情况的不成功检索要lognlogn次元素比较，所以次元素比较，所以时间是时间是（lognlogn）。由于外部节点都在。由于外部节点都在k k和和k+1k+1级，因此，每级，因此，每种不成功检索的时间都是种不成功检索的时间都是（lognlogn），），故平均情况下不成功故平均情况下不成功检索的计算时间是检索的计算时间是（lognlogn）。 E=I+2n E=I+2n (1) (1)令令S(nS(n) )是成功检索的平均比较数，则是成功检索的平均比较数，则 S S（n)=I/n+1n)=I/n+1 (2) (2) 平均情况下成功检索的时间复杂性分析：平

34、均情况下成功检索的时间复杂性分析： 设根到所有内部结点的距离之和称为内部路径长度设根到所有内部结点的距离之和称为内部路径长度I I，由根到所有外部结点的距离之和称为外部路径长度由根到所有外部结点的距离之和称为外部路径长度E E，可以，可以证明：证明：为什么要为什么要+1+1 令令U U（n)n)是不成功检索的平均情况比较数，而任何一个是不成功检索的平均情况比较数，而任何一个外部结点所需要的比较数是由根到该结点路径的长度，由外部结点所需要的比较数是由根到该结点路径的长度，由此得：此得： U(nU(n)=E/(n+1)=E/(n+1) (3) (3)利用（利用（1 1）- -（3 3）可以得到：）

35、可以得到： S(nS(n)=(1+1/n)U(n)-1)=(1+1/n)U(n)-1因此：平均情况下成功检索的时间复杂性为：因此：平均情况下成功检索的时间复杂性为： (log n)。五、一种二分检索的变形五、一种二分检索的变形BINSEARCH1BINSEARCH1。 BINSEARCH1BINSEARCH1的的whilewhile循环中循环中x x和和AmidAmid 之间只用作一次比较。之间只用作一次比较。 BINSEARCH1(A,n,x,j)1 low 12 high n+13 while low high4do56 mid (low + high) / 27 if (x Amid)/

36、在循环中只比较一次8 then high mid9else lowmid10 11 if x = Alow12 then j low/x出现13 else j=0 / x不出现14 return j BINSEARCHBINSEARCH和和BINSEARCH1BINSEARCH1相比较可看出，对于任何一种成相比较可看出，对于任何一种成功的检索，功的检索，BINSEARCH1BINSEARCH1平均要比平均要比BINSEARCHBINSEARCH多作多作 次比较。次比较。BINSEARCH1BINSEARCH1的最好、平均和最坏情况时间对于成的最好、平均和最坏情况时间对于成功和不成功的检索都是功

37、和不成功的检索都是 。 六、以比较为基础检索的时间下界六、以比较为基础检索的时间下界 1. 什么是以比较为基础的检索算法什么是以比较为基础的检索算法 检索一给定元素检索一给定元素x是否在是否在A中出现。如果只允许进行元素中出现。如果只允许进行元素间的比较而不允许对它们实施运算，在这种条件下所设计的间的比较而不允许对它们实施运算，在这种条件下所设计的算法都称为是以比较为基础的算法算法都称为是以比较为基础的算法 。 2. 二分检索是以比较为基础的检索算法中最坏情况下的最优二分检索是以比较为基础的检索算法中最坏情况下的最优算法算法. 定理定理2.3 2.3 设设A A（1 1：n n）含有）含有n

38、n个不同的元素，个不同的元素，n1n1，它们，它们被排序为被排序为A(1)A(2)A(1)A(2) A(nA(n) )。又设用以比较为基础去判断。又设用以比较为基础去判断是否是否xAxA（1 1：n n）的任何算法在最坏情况下所需的最小比）的任何算法在最坏情况下所需的最小比较次数是较次数是FINDFIND（n n），那么），那么FINDFIND（n n） 结论：结论：由于二分检索所产生的比较树中所有的外部结点都由于二分检索所产生的比较树中所有的外部结点都在相邻接的两个级上在相邻接的两个级上，不难证明这样的二元树使得由根到不难证明这样的二元树使得由根到结点的最长路径减至最小，因此，结点的最长路径

39、减至最小，因此，二分检索是解决检索问二分检索是解决检索问题在最坏情况下的最优算法。题在最坏情况下的最优算法。证明：通过考虑模拟求解检索问题的各种算法的比较树可证明：通过考虑模拟求解检索问题的各种算法的比较树可知，知，FINDFIND（n n）不大于树中根到一个叶子最长路径的距离。）不大于树中根到一个叶子最长路径的距离。在这所有的树中都必定有在这所有的树中都必定有n n个内结点与个内结点与x x在在A A中可能的中可能的n n种出种出现相对应，如果一棵二元树的所有内结点所在的级数小于现相对应，如果一棵二元树的所有内结点所在的级数小于级数级数k k，则最多有，则最多有2 2k k-1-1个内结点，

40、因此个内结点，因此n 2n 2k k-1,-1,即即FINDFIND（n n）=k=k 一、直接求最大、最小元素一、直接求最大、最小元素算法算法2.5 2.5 直接找最大和最小元素直接找最大和最小元素maxmin(A,nmaxmin(A,n) ) /将将A(1:n)A(1:n)中的最大元素置于中的最大元素置于maxmax，最小元素置于，最小元素置于min/min/1 max 1 max A1A12 min 2 min A1;A1;3 for i 3 for i 2 to n2 to n4 4 dodo5 5 6 6 if max if max 6 if min AiAi 7 7 then mi

41、n then min AiAi 8 8 2.3 2.3 找最大和最小元素找最大和最小元素 时间复杂性分析：时间复杂性分析： STRAITMAXMIN在最好、平均和最坏情况下均需要作在最好、平均和最坏情况下均需要作2(n-1)次元素比较。次元素比较。 如果稍做修改：如果稍做修改： 用下面的语句代替用下面的语句代替forfor循环中的语句：循环中的语句： if if A(iA(i)max then )max then maxmaxA(iA(i) ) else if else if A(iA(i)min then )min then minminA(iA(i) ) endifendif endife

42、ndif 最好情况将在元素按递增次序排列时出现，元素比较最好情况将在元素按递增次序排列时出现，元素比较数是数是n-1n-1；最坏情况将在递减次序时出现，元素比较是；最坏情况将在递减次序时出现，元素比较是 2 2（n-1n-1）；至于在平均情况下）；至于在平均情况下, ,A(iA(i) )将有一半的时间比将有一半的时间比maxmax大，因此平均比较数是大，因此平均比较数是3/2(n-1)3/2(n-1)。二、用分治法求最大、最小元素二、用分治法求最大、最小元素 1、问题分析、问题分析 使使用用分分治治策策略略设设计计是是将将任任一一实实例例I=(n，A(1)，A(n)分分成成一一些些较较小小的的

43、实实例例来来处处理理，例例如如，可可以以把把分分成成两两个个这这样样的的 实实 例例 I1=(n/2， A(1)， ， A(n/2)和和 =(n-n/2,A(n/2+1),A(n)。如如果果()和和（）是是中中的的最最大大和和最最小小元元素素，则则（）等等于于（）和和（）中中的的大大者者，（）等等于于（）和和（）中中的的小小者者。如如果果只只包包含含一一个个元元素，则不需要作任何分割直接就可得到其解。素，则不需要作任何分割直接就可得到其解。 2.2.算法算法算法算法. .递归求取最大和最小元素递归求取最大和最小元素float float AnAn;maxminmaxmin（i, j, i, j

44、, fmaxfmax, , fminfmin）/最大和最小元素赋给最大和最小元素赋给fmaxfmax和和fminfmin1 if i = j 1 if i = j 2 2 then then3 3 4 4 fmaxfmax AiAi;5 5 fminfmin AiAi;6 6 7 else if i = j-17 else if i = j-18 8 then if then if AiAi rmaxrmax25 25 then then fmaxfmax lmaxlmax; ;26 else 26 else fmaxfmax rmaxrmax27 if 27 if lminlmin rmin

45、rmin28 28 then then fminfmin rminrmin; ;29 else 29 else fminfmin lminlmin; ;30 30 递归调用递归调用利用层次分析法分析此递归调用过程。（要求掌握）利用层次分析法分析此递归调用过程。（要求掌握）利用层次分析法分析此递归调用过程。（要求掌握）利用层次分析法分析此递归调用过程。（要求掌握）考虑如下例子：考虑如下例子：A A：（：（1 1） （2 2） （3 3） （4 4） （5 5） （6 6） （7 7） （8 8） （9 9） 22 13 -5 -8 15 60 17 31 4722 13 -5 -8 15 60

46、17 31 473.时间复杂性分析时间复杂性分析 0 n=1 (n)= 1 n=2 n2当当n是的幂时，即对于某个正整数是的幂时，即对于某个正整数k，nk ，有，有 T(n)=2T(n/2)+2=2(2T(n/4)+2)+2=4T(n/4)+4+2 =k-1 T(2)+ =k-1 T+k-2 =3n/2-2?讨论：以上算法是否是最优的？讨论：以上算法是否是最优的？1 1）递归带来的额外的空间开销。）递归带来的额外的空间开销。2 2）当元素当元素A(iA(i) )和和A(jA(j) )的比较时间的比较时间i i和和j j的比较时间相差不大的比较时间相差不大时，过程时，过程maxminmaxmin

47、并不可取。并不可取。因此：当因此：当n是的幂时，是的幂时，3n/2-2是最好，平均及最坏情况的比是最好，平均及最坏情况的比较数较数,和直接算法的比较数和直接算法的比较数n相比，它少了。相比，它少了。 可以证明，任何一种以元素比较为基础的找最大和最小元素可以证明，任何一种以元素比较为基础的找最大和最小元素的算法，其元素比较下界均为的算法，其元素比较下界均为 次。次。 为说明问题，假设元素比较与为说明问题，假设元素比较与i和和j间的比较时间相同，又设间的比较时间相同，又设maxmin的频率计数为的频率计数为C(n) ，n=2k，,k是某个正整数，并且对是某个正整数，并且对前两种情况，用前两种情况，

48、用ij-1来代替来代替i=j和和i=j-1这两次比较，这样，这两次比较，这样，只用对只用对i和和j-1作一次比较就足以实现被修改过的语句。于是作一次比较就足以实现被修改过的语句。于是maxmin频率计数频率计数 C(nC(n)= )= n=2 n2? ?解此关系式可得解此关系式可得 C(n)=2C(n/2)+3=4C(n/4)+6+3C(n)=2C(n/2)+3=4C(n/4)+6+3 =2 =2k-1k-1C(2)+C(2)+ =2=2k k+3*2+3*2k-1k-1-3-3 =5n/2-3 =5n/2-3分分析析：STRAITMAXMINSTRAITMAXMIN的的比比较较数数是是3(n

49、-1)(3(n-1)(包包括括实实现现forfor循循环环所所要要的的比比较较) )。尽尽管管它它比比5n/2-35n/2-3大大些些，但但由由于于递递归归算算法法中中i i，j j，fmaxfmax，fminfmin进进出出栈栈所所带带来来的的开开销销，因因此此maxminmaxmin在在这这种种情情况况下下反而比反而比STRAITMAXMINSTRAITMAXMIN还要慢些。还要慢些。 根根根根据据据据以以以以上上上上分分分分析析析析可可可可以以以以得得得得出出出出结结结结论论论论：如如如如果果果果A A A A的的的的元元元元素素素素间间间间的的的的比比比比较较较较远远远远比比比比整整整

50、整数数数数变变变变量量量量的的的的比比比比较较较较代代代代价价价价昂昂昂昂贵贵贵贵，则则则则分分分分治治治治方方方方法法法法产产产产生生生生效效效效率率率率较较较较高高高高（实实实实际际际际上上上上是是是是最最最最优优优优）的的的的算算算算法法法法；反反反反之之之之，就就就就得得得得到到到到一一一一个个个个效效效效率率率率较较较较低低低低的的的的程程程程序序序序。因因因因此此此此，分分分分治治治治策策策策略略略略只只只只能能能能看看看看成成成成是是是是一一一一个个个个较较较较好好好好的的的的然然然然而而而而并并并并不不不不总总总总是是是是能成功的算法设计指导。能成功的算法设计指导。能成功的算法

51、设计指导。能成功的算法设计指导。2.42.4斯特拉森矩阵乘法斯特拉森矩阵乘法一、一般的矩阵乘法一、一般的矩阵乘法 设设C=A*B,C=A*B, 则利用常规方法计算，所需时间是则利用常规方法计算，所需时间是 二、二、分治法分治法求矩阵乘法求矩阵乘法 设设n=2n=2k k，则可以将两个矩阵的乘法做如下划分：，则可以将两个矩阵的乘法做如下划分：其中：其中：C C1111=A=A1111B B1111+A+A1212B B2121 C C1212=A=A1111B B1212+A+A1212B B2121 C C2121=A=A2121B B1111+A+A2222B B2121 C C2222=A

52、=A2121B B1212+A+A2222B B2222可以证明可以证明: : C=AB= C=AB= 三三. .斯特拉森矩阵乘法斯特拉森矩阵乘法 斯特拉森矩阵乘法的设计思想斯特拉森矩阵乘法的设计思想: :增加加法的次数增加加法的次数, ,减少乘减少乘法的次数法的次数. . 如果分块矩阵的级大于如果分块矩阵的级大于2,2,则可以继续将这些子矩阵分成则可以继续将这些子矩阵分成更小的方阵更小的方阵, ,直至每个方阵只含有一个元素直至每个方阵只含有一个元素, ,以至可以直接以至可以直接计算其乘积计算其乘积. .时间复杂性分析时间复杂性分析: n 2 n2则则T(n)=O(n3)先用七个乘法和十个加（

53、减）法来算出以下的先用七个乘法和十个加（减）法来算出以下的P-VP-VP=(AP=(A1111+A+A2222)(B)(B1111+B+B2222) ) ，Q=(AQ=(A2121+A+A2222)B)B1111R=AR=A1111(B(B1212-B-B2222) )， S=AS=A2222(B(B2121-B-B1111) )T=(AT=(A1111+A+A1212)B)B2222 ，U=(AU=(A2121-A-A1111)(B)(B1111+B+B1212) )V=(AV=(A1212-A-A2222)(B)(B2121+B+B2222) )然后用然后用8 8个加减法算出这些个加减法算

54、出这些 C Cij ij C C1111=P+S-T+V=P+S-T+VC C1212=R+T=R+TC C2121=Q+S=Q+SC C2222=P+R-Q+U=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 c

55、n2(7/4)logn=cnlog4*nlog7-log4=cnlog4+log7-log4=cnlog7因此上式因此上式(1)=cnlog7+7logn=cnlog7+nlog7=(c+1)nlog7=O(nlog7)O(n2.81).注意：注意：注意：注意：（1 1）当）当n n小于小于120120时，斯特拉森矩阵乘法与普通的乘法没时，斯特拉森矩阵乘法与普通的乘法没有太大的区别有太大的区别 。（2 2）斯特拉森矩阵乘法的核心就是降低乘法的次数而增）斯特拉森矩阵乘法的核心就是降低乘法的次数而增加加法的次数，那么是否可以使乘法由加加法的次数，那么是否可以使乘法由7 7次降低为次降低为6 6次呢

56、？次呢？已经证明已经证明7 7次是必须的，这一方面改进只能从更高维数如次是必须的，这一方面改进只能从更高维数如3*33*3，或，或4*44*4并用递归分治的合并方法来实现，现在可以达并用递归分治的合并方法来实现，现在可以达到到o(no(n2.4953642.495364).).一、基本方法一、基本方法1 1例子：例子：背背包包问问题题：已已知知有有n n种种物物品品和和一一个个容容量量大大小小为为M M的的背背包包，每每种种物物品品i i的的容容量量为为w wi i。假假定定将将物物品品i i的的一一部部分分x xi i放放入入背背包包就就会会得得到到p pi ix xi i的的效效益益，这这

57、里里，0 0 x xi i1 1，p pi i0 0。采采用用怎怎样样的的装装包包方方法法才才会会使使装装入入背背包包物物品品的的总总效效益益最最大大呢呢？显显然然，由由于于背背包包容容量量是是M M，因因此此，要要求求所所有有选选中中要要装装入入背背包包的的物物品品总总容容量量不不得得超超过过M M。如如果果这这n n件件物物品品的的总总容容量量不不超过超过M M，则把所有物品装入背包自然获得最大效益。，则把所有物品装入背包自然获得最大效益。如果这些物品容量的和大于如果这些物品容量的和大于M M，则在这种情况下该如何装包呢？，则在这种情况下该如何装包呢？第三章贪心方法第三章贪心方法3 31

58、1方法概述方法概述例例: :考考虑虑下下列列情情况况下下的的背背包包问问题题：n=3n=3，M M2020， (25(25，2424，1515）, =(18,15,10), =(18,15,10)。其中的四个可行解是。其中的四个可行解是: : （1/2,1/3,1/41/2,1/3,1/4） 16.5 16.5 24.2524.25（1 1，2/152/15，0 0） 20 20 28.228.2（0 0，2 23 3，1 1） 20 20 3131（0 0，1 1，1 12 2） 20 20 31.531.5在这些可行解中，如何得到最优解，正是贪心方法要解决的问题。在这些可行解中，如何得到最

59、优解，正是贪心方法要解决的问题。在这些可行解中，如何得到最优解，正是贪心方法要解决的问题。在这些可行解中，如何得到最优解，正是贪心方法要解决的问题。2 2、 适用条件：适用条件：（1 1）有）有n n个输入；个输入；（2 2）它的解就由这）它的解就由这n n个输入的个输入的某个子集某个子集组成；组成；（3 3）这个子集必须满足一定的约束条件）这个子集必须满足一定的约束条件-可行解；可行解；（4 4）可可行行解解一一般般不不止止一一个个，但但是是要要要要求求求求的的的的是是是是最最最最优优优优解解解解即即即即使使使使目目目目标标标标函函函函数取得极值的解。数取得极值的解。数取得极值的解。数取得极

60、值的解。 3 3有关概念有关概念（1 1） 约束条件：约束条件：约束条件：约束条件：把子集必须满足的基本条件称为约束条件。把子集必须满足的基本条件称为约束条件。（2 2） 可行解可行解可行解可行解：把满足约束条件的子集称为该问题的可行解。：把满足约束条件的子集称为该问题的可行解。（3 3） 目标函数：目标函数：目标函数：目标函数：（可行解一般来说是不唯一的）为了衡量可（可行解一般来说是不唯一的）为了衡量可行解的优劣，事先也给出了一定的标准，这些标准一般以用函行解的优劣，事先也给出了一定的标准，这些标准一般以用函数形式给出，这些函数称为目标函数。数形式给出，这些函数称为目标函数。（4 4） 最优

61、解：最优解：最优解：最优解：那些使目标函数取极值（极大或极小）的可行那些使目标函数取极值（极大或极小）的可行解，称为最优解解，称为最优解。4 4基本方法：基本方法： 贪心方法是一种改进了的分级处理方法。它首先根据题意，选贪心方法是一种改进了的分级处理方法。它首先根据题意，选取一种量度标准。然后按这种量度标准对这取一种量度标准。然后按这种量度标准对这n n个输入排序，并按序个输入排序，并按序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部部分最优解加在一起不能产生一个可行

62、解，则不把此输入加到这部分解中。这种能够得到某种量度意义下的最优解的分级处理方法称分解中。这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法。为贪心方法。注意：注意：对于一个给定的问题，往往可能有好几种量度标准对于一个给定的问题，往往可能有好几种量度标准对于一个给定的问题，往往可能有好几种量度标准对于一个给定的问题，往往可能有好几种量度标准( ( ( (贪贪贪贪心准则心准则心准则心准则) ) ) )。选择能产生问题最优解的最优量度标准是使用贪心。选择能产生问题最优解的最优量度标准是使用贪心。选择能产生问题最优解的最优量度标准是使用贪心。选择能产生问题最优解的最优量度标准是使用贪心法设

63、计求解的核心问题法设计求解的核心问题法设计求解的核心问题法设计求解的核心问题。二、贪心方法的算法设计模式二、贪心方法的算法设计模式GREEDYGREEDY（A A，n n）/An /An 包含包含n n个输入个输入/1 solution1 solution / /将解向量将解向量solutionsolution初始化为空初始化为空/2 for i1 to n do2 for i1 to n do3 x3 xSELECTSELECT（A A）/按最优量度标准在按最优量度标准在A A中选择一个输入中选择一个输入4 if 4 if FEASIBLEFEASIBLE（solutionsolution，

64、x x） 5 5 then solutionthen solutionUNIONUNION（solutionsolution，x x） 6 6 7 7 return return（solutionsolution） 三、设计要点：三、设计要点： 选择能产生问题最优解的最优量度标准是使用贪选择能产生问题最优解的最优量度标准是使用贪选择能产生问题最优解的最优量度标准是使用贪选择能产生问题最优解的最优量度标准是使用贪心法设计求解的核心问题。心法设计求解的核心问题。心法设计求解的核心问题。心法设计求解的核心问题。3.2 3.2 背包问题背包问题一、问题的描述一、问题的描述 背包问题：已知有背包问题：已

65、知有n n种物品和一个容量为种物品和一个容量为M M的背包，每种物的背包，每种物品品i i的容量为的容量为w wi i，效益为，效益为p pi i ，假定将物品，假定将物品i i的一部分的一部分x xi i放入背放入背包就会得到包就会得到p pi ix xi i的效益，这里，的效益，这里，0=x0=xi i=10 ,w0 ,wi i0, 00, 0 i inn M M背包的容量背包的容量n n物品种类物品种类w wi i第第i i物品的容量物品的容量p pi i第第i i种物品价值种物品价值 显然，满足约束条件的任一集合显然，满足约束条件的任一集合 是是一个可行解，一个可行解，使目标函数取最大

66、值的可行解是最优解。使目标函数取最大值的可行解是最优解。例例3 31 1考考虑虑下下列列情情况况下下的的背背包包问问题题：n=3n=3，M M2020，（plpl， p2p2， p3p3） （ 2525， 2424， 1515） ， （ w1w1， w2w2，w3w3）=(18,15,10)=(18,15,10)。其中的四个可行解是。其中的四个可行解是: :（x1x1，x2x2，x3x3） （1 12 2，1 13 3，1 14 4） 16.5 24.2516.5 24.25（1 1，2/152/15，0 0） 20 28.220 28.2（0 0，2 23 3，1 1） 20 3120 31

67、（0 0，1 1，1 12 2） 20 31.520 31.5在在这这四四个个可可行行解解中中，第第个个解解的的效效益益值值最最大大。下下面面将将可可看到，看到，这个解是背包问题在这一情况下的最优解。这个解是背包问题在这一情况下的最优解。二、问题的分析二、问题的分析 为为了了获获取取背背包包问问题题的的最最优优解解，必必须须要要把把物物品品放放满满背背包包。由由于于可可以以只只放放物物品品i i的的一一部部分分到到背背包包中中，因因此此这这一一要要求求是是可可以以达达到到的的。如如果果用用贪贪心心策策略略来来求求解解背背包包问问题题则则正正如如3 31 1节节中中所所说说的一样，的一样，首先要

68、选出最优的量度标准。首先要选出最优的量度标准。以下不妨分三种情况进行分析：以下不妨分三种情况进行分析：(1(1) ) ) ) 取效益值作为量度标准。取效益值作为量度标准。取效益值作为量度标准。取效益值作为量度标准。 即每装入一件物品就使背包获得最大可能的效益值增量。即每装入一件物品就使背包获得最大可能的效益值增量。在这种量度标准下的贪心方法就是按效益值的非增次序将物品在这种量度标准下的贪心方法就是按效益值的非增次序将物品一件件放到背包中去。如果正在考虑中的物品放不进去，则可一件件放到背包中去。如果正在考虑中的物品放不进去，则可只取其一部分来装满背包只取其一部分来装满背包。量度量度标准标准选取选

69、取此此种种选选择择策策略略得得到到的的解解，总总效效益益值值是是28.228.2。它它是是一一个个次次优优解解。由此例可知，按物品效益值的非增次序装包不能得到最优解。由此例可知，按物品效益值的非增次序装包不能得到最优解。 为为什什么么上上述述贪贪心心策策略略不不能能获获得得最最优优解解呢呢？原原因因在在于于，背背包包可可用用容容量量消消耗耗过过快快。由由此此，很很自自然然地地启启发发我我们们用用容容量量作作为为量量度度，让背包容量尽可能慢地被消耗。让背包容量尽可能慢地被消耗。 （2 2）用容量作为量度标准用容量作为量度标准用容量作为量度标准用容量作为量度标准 在这种量度标准下的贪心方法就是按物

70、品容量的非降次序在这种量度标准下的贪心方法就是按物品容量的非降次序来把物品放入背包。例来把物品放入背包。例3.13.1的解的解就是使用这种贪心策略得到就是使用这种贪心策略得到的，它仍是一个次优解。这种策略也只能得到次优解，其原因的，它仍是一个次优解。这种策略也只能得到次优解，其原因在于容量虽然慢慢地被消耗，但效益值没能迅速地增加。在于容量虽然慢慢地被消耗，但效益值没能迅速地增加。 以上策略也只能得到次优解，其原因在于以上策略也只能得到次优解，其原因在于容量虽然慢慢地容量虽然慢慢地被消耗，但效益值没能迅速地增加。被消耗，但效益值没能迅速地增加。这又启发我们这又启发我们应采用在效应采用在效应采用在

71、效应采用在效益值的增长速率和容量的消耗速率之间取得平衡的量度标准。益值的增长速率和容量的消耗速率之间取得平衡的量度标准。益值的增长速率和容量的消耗速率之间取得平衡的量度标准。益值的增长速率和容量的消耗速率之间取得平衡的量度标准。即每装入一件物品应使它占用的每一单位容量获得当前最大的即每装入一件物品应使它占用的每一单位容量获得当前最大的效益。效益。三、算法设计三、算法设计算法算法3.3 3.3 背包问题的贪心算法背包问题的贪心算法（3） 用效益和容量的比值作为量度标准。用效益和容量的比值作为量度标准。用效益和容量的比值作为量度标准。用效益和容量的比值作为量度标准。(即即 ) 这这就就需需使使物物

72、品品的的装装入入次次序序按按 比比值值的的非非增增次次序序来来考考虑虑，在在这这种种策策略略下下的的量量度度是是已已装装入入物物品品的的累累计计效效益益值值与与所所用用容容量量之之比比。其其量量度度标标准准是是每每次次装装入入要要使使累累计计效效益益值值与与所所用用容容量量的的比比值值有有最最多多的的增增加加或或最最少少的的减减小小（第第二二次次和和以以后后的的装装入入可可能能使使此此比比值减小）。将此贪心策略应用于例值减小）。将此贪心策略应用于例3.l的数据，得到解的数据，得到解。Knapsack(ElemtypeW Knapsack(ElemtypeW pn, pn, ElemtypeP

73、ElemtypeP wn, wn, float float yn, yn, ElemtypeW C, int n) ElemtypeW C, int n) /pnpn和和和和wnwn分分分分别别别别含含含含有有有有按按按按pipiwiwi，pipi11wi+1wi+1排排排排序序序序的的的的n n件件件件物物物物品品品品的效益值和容量。的效益值和容量。的效益值和容量。的效益值和容量。MM是背包的容量大小，而是背包的容量大小，而是背包的容量大小，而是背包的容量大小，而ynyn是解向量是解向量是解向量是解向量/ /1 for i1 to n for i1 to n 2 do yi0;2 do yi

74、0;/将解向量初始化为将解向量初始化为0 0；3 cu C;3 cu C;/cu/cu是背包中剩余的空间；是背包中剩余的空间；4 for i1 to n 4 for i1 to n 5 do5 do/依次考察下一个物品是否可以放入背包；依次考察下一个物品是否可以放入背包；6 if wi cu break;/6 if wi cu break;/物品物品i i无法全部放入背包无法全部放入背包, , 退出退出forfor循环；循环；7 then yi1; 7 then yi1; 8 cu cu - wi;8 cu cu - wi;9 9 10 if in 10 if in 11 then yi cu

75、/wi; /11 then yi cu/wi; /不能完全装入的物品的部分装入量不能完全装入的物品的部分装入量量度标准量度标准 值值得得指指出出的的是是：（a）如如果果把把物物品品事事先先按按效效益益值值的的非非增增次次序序或或容容量量的的非非降降次次序序分分好好类类，再再使使用用以以上上算算法法就就可可分分别别得得到到量量度度标标准准为为（2）或或（3）（使使每每次次效效益益增增量量最最大大或或使使容容量量消消耗耗最最慢慢）的解。的解。(b)该算法的解的形式为（该算法的解的形式为（1，.1,x，0，0）,其中其中x在在0，1。由背包问题量度选取的研究可知，由背包问题量度选取的研究可知，选取最

76、优的量度标准实为用选取最优的量度标准实为用贪心方法求解问题的核心。贪心方法求解问题的核心。小结：贪心方法设计步骤：小结：贪心方法设计步骤：找出问题的约束条件和目标函数。找出问题的约束条件和目标函数。选取合适的量度标准。选取合适的量度标准。按照按照“贪心方法的算法设计模式贪心方法的算法设计模式”的步骤进行算法设计的步骤进行算法设计.四、算法分析四、算法分析 如果将物体事先按如果将物体事先按Pi/wi的非增次序分好类，则过程的非增次序分好类，则过程Knapsack就得出这一策略下背包问题的解。如果将物品分就得出这一策略下背包问题的解。如果将物品分类的时间不算在内，则此算法所用时间为类的时间不算在内

77、，则此算法所用时间为O（n）。）。五、算法的证明五、算法的证明 证明的基本思想是证明的基本思想是：把这贪心解与任一最优解相比较，如果：把这贪心解与任一最优解相比较，如果这两个解不同，就去找开始不同的第一个这两个解不同，就去找开始不同的第一个xi，然后设法用贪心解，然后设法用贪心解的这个的这个xi去代换最优解的那个去代换最优解的那个xi，并证明最优解在分量代换前后，并证明最优解在分量代换前后的总效益无任何变化。反复进行这种代换，直到新产生的最优的总效益无任何变化。反复进行这种代换，直到新产生的最优解与贪心解完全一样，从而证明了贪心解是最优解。解与贪心解完全一样，从而证明了贪心解是最优解。 掌握掌

78、握定理31 如果p1/wl p2/w2 pn/wn。则算法GREEDYKNAPSACK对于给定的背包问题实例生成一个最优解。证明：设X=（x1，xn）是GREEDYKNAPSACK所生成的解。如果所有的xi等于1，显然这个解就是最优解。于是，设j是使xj 1的最小下标。由算法可知，对于1ij，xi=1；对于jin，xi=0。对于j，0xj1。 如如 果果 X不不 是是 一一 个个 最最 优优 解解 ， 则则 必必 定定 存存 在在 一一 个个 可可 行行 解解Y=(y1,y2,yn),使使得得 ；不不失失一一般般性性，可可以以假假定定wiyi=M。设设k是是使使得得yk xk的的最最小小下下标

79、标。显显然然，这这样样的的k必必定定存存在在。由由上上面面的的假假设设，可可以以推推得得ykxk。这这可可从从三三种种可可能能发发生生的的情情况况，即即kj分别得证明：分别得证明：若若kj，则则xk=1。因。因yk xk。从而。从而ykxk。若若k=j,由由于于wixi =M，且且对对于于1i xk，显显然然有有wiyiM,与与Y是是可可行行解解矛矛盾盾。若若yk=xk,与假设与假设yk xk矛盾，故矛盾，故ykj，则，则wiyiM,这是不可能的。这是不可能的。 现现在在，假假定定把把yk增增加加到到xk，那那末末必必须须从从（yk1，yn）中中减减去同样多的量，使得所用的总容量仍是去同样多的

80、量，使得所用的总容量仍是M。这这 导导 致致 一一 个个 新新 的的 解解 Z= =（ z z1 1， z z2 2， , ,z zn n） ， 其其 中中 z zi i=x=xi i,1,1ik, ,且且 ，因此，对于，因此，对于Z Z有：有：关键关键若若 0时，时，则则Y不是最优解，此与假设矛盾，所以不可能，不是最优解，此与假设矛盾，所以不可能，即即 =0。当当=0时时，则，则Z=XZ=X或或Z ZX X，则，则若若Z=XZ=X，则，则p pi iz zi i= = p pi iy yi i，由于，由于Y Y是最优解，因此是最优解，因此Z Z也是最优也是最优解，解，X X也是最优解。也是最

81、优解。若若ZXZX，重复上面的讨论，用，重复上面的讨论，用Z Z代替代替Y Y，则又可求得相应的，则又可求得相应的 0 0，重复以上过程，直到，重复以上过程，直到X=ZX=Z为止，可得为止，可得X X为最优解。为最优解。讨论：讨论：3.33.3带有限期的作业排序带有限期的作业排序 一、问题的描述一、问题的描述 假定只能在一台机器上处理假定只能在一台机器上处理n n个作业，每个作业均可在单位个作业，每个作业均可在单位时间内完成；又假定每个作业时间内完成；又假定每个作业i i都有一个截止期限都有一个截止期限d di i0 0（它是（它是整数），当且仅当作业整数），当且仅当作业i i在它的期限截止以

82、前被完成时，则获得在它的期限截止以前被完成时，则获得p pi i0 0的效益的效益 ，求具有最大效益值的可行解，求具有最大效益值的可行解, ,也就是最优解。也就是最优解。分析：分析：约束条件：约束条件：每个作业均要在截止期限前完成。每个作业均要在截止期限前完成。 目标函数目标函数：例子：例子：n=4,(p1,p2,p3,p4)=(100,10,15,20)n=4,(p1,p2,p3,p4)=(100,10,15,20)和和(d1,d2,d3,d4)=(2,1,2,1)(d1,d2,d3,d4)=(2,1,2,1)。可行解可行解可行解可行解 处理顺序处理顺序处理顺序处理顺序 效益值效益值效益值效

83、益值 （1 1） 1 1001 100 （2 2） 2 102 10 （3 3） 3 153 15 （4 4） 4 204 20 （1 1，2 2） 2 2，1 1101 110 （1 1，3 3） 1 1，3 3或或3 3，1 1 115 115（1 1，4 4） 4 4，1 1201 120（2 2，3 3） 2 2，3 253 25（3 3，4 4） 4 4，3 353 35二、问题的分析二、问题的分析 最优量度标准：目标函数最优量度标准：目标函数p pi i作为量度，即按照作为量度，即按照p pi i的非增的非增次序来考虑这些作业。次序来考虑这些作业。 使用这一量度，下一个要计入的作业

84、将是使得在满足所产使用这一量度，下一个要计入的作业将是使得在满足所产生的生的J J是一个可行解的限制条件下让是一个可行解的限制条件下让p pi i得到最大增加的作得到最大增加的作业。业。 应用以上的量度标准：开始时应用以上的量度标准：开始时J=0J=0， 由于作业由于作业1 1有最有最大效益且大效益且J=J=1 1是一个可行解，于是把作业是一个可行解，于是把作业1 1计入计入J J。下一步。下一步考虑作业考虑作业4 4，J=J=1 1，4 4也是可行解。然后考虑作业也是可行解。然后考虑作业3 3，因为，因为1 1，3 3，4 4不是可行解，故作业不是可行解，故作业3 3被舍弃。最后考虑作业被舍

85、弃。最后考虑作业2 2，由于由于1 1，2 2，4 4也不可行，作业也不可行，作业2 2被舍弃。最终所留下的是效被舍弃。最终所留下的是效益值为益值为120120的解的解J=J=1 1，4 4。它是这个问题的最优解。它是这个问题的最优解。三、算法的粗略描述三、算法的粗略描述 GREEDY-GREEDY-JOB(D,J,nJOB(D,J,n) )/作作作作业业业业按按按按p p p p1 1 1 1pppp2 2 2 2p p p pn n n n的的的的次次次次序序序序输输输输入入入入，它它们们的的期期限限值值Di1,1in,n1.JDi1,1in,n1.J是是在在它们的截止期限前完成的作业的集

86、合它们的截止期限前完成的作业的集合/1 J1 J1 12 for i2 to n do2 for i2 to n do3 if J3 if Ji i的所有作业都有能在它们的截止期限前完成的所有作业都有能在它们的截止期限前完成 then JJthen JJi i4 4 endifendif5 5 由前面贪心方法的算法设计模式得到由前面贪心方法的算法设计模式得到J J是一个作业的集合，是一个作业的集合，而不是调度表而不是调度表四、算法的证明四、算法的证明定理定理3.23.2 以上算法所描述的贪心方法对于作业排序问题总是以上算法所描述的贪心方法对于作业排序问题总是得到一个最优解。得到一个最优解。 思

87、路思路：J J是由贪心方法所选择的作业的集合；是由贪心方法所选择的作业的集合；I I是一个最优解是一个最优解的作业集合。可证明的作业集合。可证明J J和和I I具有相同的效益值，从而具有相同的效益值，从而J J也是最优也是最优的。的。（I,JI,J是作业的集合是作业的集合，而不是作业的调度表），而不是作业的调度表）证明：证明：假定（假定（1 1）IJIJ，因为若，因为若I=JI=J，则，则J J即为最优解。即为最优解。（2 2）如果）如果I JI J，则，则I I就不可能是最优的。就不可能是最优的。（3 3）由贪心法的工作方式也排斥了）由贪心法的工作方式也排斥了J IJ I。因此，至少存在这样

88、的两个作业因此，至少存在这样的两个作业a a和和b b，使得，使得aJaJ且且a Ia I，bIbI且且b Jb J。设。设a a是使得是使得aJaJ且且a Ia I的一个具有最高效益值的作业。由的一个具有最高效益值的作业。由贪心方法可以得出，对于在贪心方法可以得出，对于在I I中又不在中又不在J J中的所有作业中的所有作业b b，都有，都有p pa appb b。这是因为若。这是因为若p pb b p pa a，则贪心方法会先于作业，则贪心方法会先于作业a a考虑作业考虑作业b b并且把并且把b b计入到计入到J J中去。中去。 设设S SI I和和S SJ J分别是分别是I I和和J J的

89、可行调度表。的可行调度表。（调度表与作业集的区别）（调度表与作业集的区别）(1)(1)设设i i是既属于是既属于J J又属于又属于I I的一个作业的一个作业, ,把他们调换到相同的时把他们调换到相同的时刻去调度，且刻去调度，且尽量将调度时间往后移。尽量将调度时间往后移。设设i i在在S SI I中在中在t t到到t+1t+1时刻被调度，而在时刻被调度，而在S SJ J中则在中则在t t到到t t+1+1时刻被时刻被调度。如果调度。如果t tt t，则可以将，则可以将S SI I中中tt，t t+1+1时刻所调度的那个时刻所调度的那个作业（如果有的话）与作业（如果有的话）与i i相交换。如果相交

90、换。如果J J中在中在tt，t t+1+1时刻没有时刻没有作业被调度，则将作业被调度，则将i i移到移到tt，t t+1+1调度。所形成的这个调度表调度。所形成的这个调度表也是可行的。如果也是可行的。如果t tt t，则可在和，则可在和S SI I中作类似的调换。中作类似的调换。 （2 2）对于对于I,JI,J中不同的作业，则以中不同的作业，则以J J为标准，为标准，将其中不属于将其中不属于I I的那些作的那些作业找出，设业找出，设a a是这样的作业，它在是这样的作业，它在S SJ J 中中 时刻被调度。设作业时刻被调度。设作业b b在在I I中的这一时刻被调度。根据对中的这一时刻被调度。根据

91、对a a的选择的选择 在在S SI I 的的 时刻去掉作业时刻去掉作业b b而去调度作业而去调度作业a a，这就给出了一张关于作业集合，这就给出了一张关于作业集合I I=I-=I-baba 可行的调度表。可行的调度表。 显然显然I I的效益值不小于的效益值不小于I I的效益值，并且的效益值，并且I I比比I I少一个少一个与与J J不同的作业。不同的作业。重复使用上述的转换，将使重复使用上述的转换，将使I I能在不减效益能在不减效益值的情况下转换成值的情况下转换成J J，因此，因此J J也必定是最优解，证毕。也必定是最优解，证毕。 五、算法的实现五、算法的实现 考考虑虑对对于于一一个个给给定定

92、的的J，如如何何确确定定它它是是否否为为可可行行解解的的问问题题，一一个个明明显显的的方方法法是是检检验验J中中作作业业的的所所有有可可能能的的排排列列。对对于于任任一一种种次序排列的作业序列，判断这些作业是否能在其限期前完成。次序排列的作业序列，判断这些作业是否能在其限期前完成。J J是作业集，是作业集，不是调度表不是调度表假假定定J中中有有k个个作作业业，这这就就需需要要检检查查k！个个排排列列。对对于于所所给给出出的的一一个个排排列列=i1i2i3ik，由由于于完完成成作作业业ij（1jk）的的最最早早时时间间是是j，因因此此，只只要要判判断断出出排排列列中中的的每每个个作作业业的的di

93、jj，就就可可得得知知是是一一个个允允许许的的调调度度序序列列，从从而而J就就是是一一个个可可行行解解。反反之之，如如果果排排列列中中有有一一个个dijj，则则是是一一个个行行不不通通的的调调度度序序列列，因因为为至至少少作作业业ij不不会会在在它它的的限限期期前前完完成成，故故必必须须去去检检查查J的的另另外外形形式式的的排排列列。事事实实上上，对对于于J的的可可行行性性可可以以通通过过只只检检验验J中中作作业业的的一一种种特特殊殊的的排列来确定，这个排列是按期限的非降次序来完成的。排列来确定，这个排列是按期限的非降次序来完成的。定理定理3.3 设设J是是k个作业的集合，个作业的集合， =i

94、1i2i3ik是是J中作业的一中作业的一种排列，它使得种排列，它使得di1di2dik。J是一个可行解，当且仅当是一个可行解，当且仅当J中的作业可以按照中的作业可以按照的次序而又不违反任何一个期限的情况的次序而又不违反任何一个期限的情况下来处理。下来处理。( (说明了什么说明了什么说明了什么说明了什么) )证明：现证，若证明：现证，若J J是可行解，则是可行解，则表示可以处理这些作业的表示可以处理这些作业的一种允许的调度序列。由于一种允许的调度序列。由于J J可行，则必存在，可行，则必存在， 使得使得 假设假设，那末，令，那末，令a a是使得是使得 的的最小下标。设最小下标。设 ，显然，显然b

95、 ba a。在。在中将中将 与与 相交相交换，因为换，因为 ，故作业可依新产生的排列，故作业可依新产生的排列 的次序处理而不违反任何一个期限。连续使用这一方法，的次序处理而不违反任何一个期限。连续使用这一方法，就可将就可将转换成转换成且不违反任何一个期限。定理得证。且不违反任何一个期限。定理得证。 算法设计思路：算法设计思路：首先将作业按照效益值的非增次序排列，首先将作业按照效益值的非增次序排列，然后试着将作业逐个与当前的部分可行解合并，检查是否可产然后试着将作业逐个与当前的部分可行解合并，检查是否可产生新的可行解生新的可行解，（注意当前的部分可行解已经按期限值的非降，（注意当前的部分可行解已

96、经按期限值的非降次序排列），次序排列），其方法是在部分可行解中，看能否找到新作业的其方法是在部分可行解中，看能否找到新作业的合适的位置，使加入了新的作业后，其期限值仍按非降次序排合适的位置，使加入了新的作业后，其期限值仍按非降次序排列，且每个作业均在其截止期限前完成。列，且每个作业均在其截止期限前完成。算法算法3.4 3.4 带有限期和效益的单位时间的作业排序贪心算法带有限期和效益的单位时间的作业排序贪心算法GreedyJob(intGreedyJob(int n , n , intint d , d , intint &J) &J)/d1,d1, ,dndn 是期限值。是期限值。n1n1。作

97、业已按作业已按p1p2p1p2p pn n被排序。被排序。JiJi 是是最优解中的第最优解中的第i i个作业，个作业，1ik1ik。终止时，。终止时，dJidJi dJi+1 dJi+1，1i1ik/k/1 1k1;k1;2 2d0 0;d0 0;3 3J0 0;J0 0;4 4J1 1;J1 1;/首先将作业首先将作业1 1插入第一个位置；插入第一个位置；5 5for i2 to nfor i2 to n/按按p p的非增次序依次考虑剩下的作业；的非增次序依次考虑剩下的作业；6 6 do do7 7 rkrk; ;8 8 while while dJrdJr didi and and dJr

98、dJr r r9 9 do do/while/while循环用来确定正在考虑的作业可能要插入的位置；循环用来确定正在考虑的作业可能要插入的位置；1010rrrr - 1; - 1; 体现了量度体现了量度标准标准11 11 1212if if dJrdidJrdi and and didi r r/判断此作业是否可以插入判断此作业是否可以插入J J；1313thenthen1414 for j k to r+1 /j for j k to r+1 /j是递减的是递减的1515 do do/将第将第k k到第到第r+1r+1个作业依次后移一位以插入新的作业；个作业依次后移一位以插入新的作业；161

99、6 JjJj + 1 + 1 JjJj;1717 1818JrJr + 1 i; + 1 i;/将作业插入位置将作业插入位置r+1r+1；1919k k + 1;k k + 1;/记入记入J J的作业数加的作业数加1;1;2020 2121 2222return k;return k;/返回记入返回记入J J中的作业数。中的作业数。？七、一种更快的实现七、一种更快的实现 通过使用不相交集合的通过使用不相交集合的UNIONUNION与与FINDFIND算法以及使用一个不同算法以及使用一个不同的方法来确定部分解的可行性，可以把的方法来确定部分解的可行性，可以把JSJS的计算时间由的计算时间由O O

100、（n n2 2）降低到数量级相当接近于降低到数量级相当接近于O(nO(n) )。 六、时间复杂性分析六、时间复杂性分析 经过分析知道，算法经过分析知道，算法JS所需要的总时间是所需要的总时间是O（sn）。由于）。由于sn (s为包含在解中的作业数为包含在解中的作业数)，因此因此JS的最坏计算时间为的最坏计算时间为O（n2）。 分析：该方法较前方法的不同之处在于如何确定部分解的可行性方面，两者的量度标准是一样的。其方法是：如果J是作业的可行子集，那么可以使用下述规则来确定这些作业中的每一个作业的处理时间：若还没给作业i分配处理时间，则分配给它时间片1, ，其中应尽量取大且时间片1, 是空的。此规

101、则就是尽可能推迟对作业的处理。于是，在将作业一个一个地装配到J中时，就不必为接纳新作业而去移动J中那些已分配了时间片的作业。如果正被考虑的新作业不存在像上面那样定义的 ，这个作业就不能计入J。例例33 设设n=5,(p1,p5)=(20,15,10,5,1)和和(d1, ,d5)=(2,2,1,3,3) 。使。使用上述可行性规则，得用上述可行性规则，得J 已分配的时间片已分配的时间片 正被考虑的作业正被考虑的作业 动作动作 无无 1 分配分配1,21 1,2 2 分配分配0,11,2 0,1,1,2 3 不适合不适合,舍弃舍弃1,2 0,1,1,2 4 分配分配2,3 1,2,4 0,1,1,

102、2,2,3 5 舍弃舍弃最优解是最优解是J=1,2,4。设计思想：设计思想：（1）只考虑时间片）只考虑时间片1，b，其中，其中b=minn,maxdj（2）作出一些以期限值为元素的集合，作出一些以期限值为元素的集合，且使得同一集合中的元且使得同一集合中的元素都有一个当前共同可用的最接近的空时间片。素都有一个当前共同可用的最接近的空时间片。（3）用用F(i)表示期限为表示期限为i的作业当前最接近的空时间片的作业当前最接近的空时间片ni，初始时，初始时， F(i)=i 且有且有b+1个集合与个集合与b+1个期限值相对应。个期限值相对应。（4）p(i) :i为根时，表示树中结点数的负值，为根时，表示

103、树中结点数的负值， i不为根时，表示不为根时，表示i 的父结点。的父结点。 初始时：初始时： p(i)= -1（5）若要调度具有期限值是）若要调度具有期限值是d的作业，则去找包含期限值的作业，则去找包含期限值min(n,d)的那个根，若根为的那个根，若根为j且只要且只要F(j) 0,则则F(j) 是最接近是最接近的空时间片，在使用完此时间片后，其根为的空时间片，在使用完此时间片后，其根为 j的集合与包含的集合与包含期限值期限值F(j) 1的集合合并。的集合合并。核心核心 在算法在算法FasterJobFasterJob中调用了过程中调用了过程UnionUnion和和FindFind，其算法分别

104、描，其算法分别描述如下描述如下：述如下描述如下：算法算法Union(i,jUnion(i,j) )的概略描述：的概略描述：Union(intUnion(int i,inti,int j) j)1 x 1 x Parent(iParent(i) + ) + Parent(jParent(j);/);/计算两棵树的总结点数；计算两棵树的总结点数；4 if 4 if Parent(iParent(i) ) Parent(jParent(j) /) /注意这里比较的是两个负数；注意这里比较的是两个负数；5 5thenthen /树树i i的结点数比的结点数比j j的少的少, ,则把则把i i连到以连到

105、以j j为根的树上；为根的树上；6 6 Parent(iParent(i) j) j7 7 Parent(jParent(j) x;) x;8 8 9 9elseelse /树树j j的结点数比的结点数比i i的少；的少；1111 Parent(jParent(j) i) i1212 Parent(iParent(i) x;) x;1313 此算法的功能是合并根为此算法的功能是合并根为i,ji,j的两个集合的两个集合. .函数函数Find(i)Find(i)算法描述如下：算法描述如下：Find(i)Find(i)1 1ji;ji;2 2while Parent(j)0while Parent(

106、j)0/寻找根结点寻找根结点j j；3 3do jParent(j);do jParent(j);4 4ki;ki;5 5while kj while kj 6 6 do do /使用压缩规则，压缩结点使用压缩规则，压缩结点i i到其根结点之间的到其根结点之间的路径上的结点；路径上的结点；7 7 tParent(k);tParent(k);8 8 Parent(k)j;Parent(k)j;9 9 kt;kt;10 10 1111return j;return j;/返回根结点。返回根结点。一、适用条件一、适用条件 多阶段决策过程多阶段决策过程 实际问题中实际问题中, ,常有这样一类活动常有这

107、样一类活动, ,它们的活动过程可以分为若干个阶段，它们的活动过程可以分为若干个阶段，而且在任一阶段而且在任一阶段i i后的行为都依赖于后的行为都依赖于i i阶段的过程状态，而与阶段的过程状态，而与i i阶段之前的阶段之前的过程如何达到这种状态的方式无关。当各个阶段决策确定后，就组成了一过程如何达到这种状态的方式无关。当各个阶段决策确定后，就组成了一个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题看作是一个前后关联的具有链状结构的多阶段过程被称为多阶段决策过程看作是一个前后关联的具有链状结构的多阶段过程被称为多阶段决

108、策过程. 满足最优性原理满足最优性原理 第四章第四章 动态规划动态规划 4 41 1 方法概述方法概述状态0 决策1 决策2 决策n 状态n状态1状态n-1状态2 最优性原理：最优性原理：最优性原理：最优性原理：过程的最优决策序列具有如下性质：过程的最优决策序列具有如下性质：无论过无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。始决策所产生的状态构成一个最优决策序列。 如果所求解问题的最优性原理成立，则说明用动态规划方如果所求解问题的最优性原理成立，则说明用动态规划方法有可能解决该问题。法

109、有可能解决该问题。因为只有满足最优性原理，才能使用各因为只有满足最优性原理，才能使用各阶段的递推公式求解。阶段的递推公式求解。二、最优性原理二、最优性原理 在多阶段决策过程的每一阶段，都可能有在多阶段决策过程的每一阶段，都可能有多种可供选择多种可供选择的决策，的决策，但必须从中选取一种决策。一旦各个阶段的决策选定之后，就构成但必须从中选取一种决策。一旦各个阶段的决策选定之后，就构成了解决这一问题的了解决这一问题的一个决策序列，一个决策序列，决策序列不同，所导致的问题的决策序列不同，所导致的问题的结果也不同。动态规划的结果也不同。动态规划的目标就是要在所有容许选择的决策序列中目标就是要在所有容许

110、选择的决策序列中选取一个会获得问题最优解的决策序列，即最优决策序列。选取一个会获得问题最优解的决策序列，即最优决策序列。 三、动态规划方法的关键三、动态规划方法的关键 关键在于获取各阶段间的递推关系式。关键在于获取各阶段间的递推关系式。 四、可解决的问题四、可解决的问题 最短路径问题、设备更新问题、资源分配问题、货物装最短路径问题、设备更新问题、资源分配问题、货物装 运排序、生产计划等。运排序、生产计划等。五、应用实例分析五、应用实例分析例例4.1 多段图问题多段图问题多段图多段图G=（V，E）是一个有向图。它具有）是一个有向图。它具有如下特性：如下特性：图中的结点被划分成图中的结点被划分成k

111、2个不相交的集合个不相交的集合Vi,1ik，其中其中V1和和Vk分别有一个结点分别有一个结点s（源点）和（源点）和t（汇点）。（汇点）。图中所有图中所有的边的边(u,v)均具有如下性质：均具有如下性质：若若uVi，则，则vVi+1，1ik-1,且且每条边每条边(u,v)均附有成本均附有成本c(u,v)。从从s到到t的一条路径成本是这条路的一条路径成本是这条路径上边的成本和。多段图问题是求由径上边的成本和。多段图问题是求由s到到t的最小成本路径。每的最小成本路径。每个集合个集合Vi定义图中的一段。由于定义图中的一段。由于E的约束，每条从的约束，每条从s到到t的路径的路径都是从第都是从第1段开始，

112、在第段开始，在第k段终止。图段终止。图4.1所示的就是一个所示的就是一个5段图。段图。123456789101112ts97322271111815435642546 对于每一条由对于每一条由s到到t的路径，可以把它看成在的路径，可以把它看成在k-2个阶段中作出个阶段中作出的某个决策序列的相应结果。第的某个决策序列的相应结果。第i次决策就是确定次决策就是确定Vi+1中的哪个中的哪个结点在这条路径上，结点在这条路径上，1ik-2。下面证明最优性原理对多段图成立。下面证明最优性原理对多段图成立。假设假设s,v2,v3,vk-1,t是一条是一条由由s到到t的最短路径，还假定从源点的最短路径，还假定从

113、源点s（初始状态）开始，已作出（初始状态）开始，已作出了到结点了到结点v2的决策（初始决策），因此的决策（初始决策），因此v2就是初始决策所产生的就是初始决策所产生的状态。如果把状态。如果把v2看成是原问题的一个子问题的初始状态，解这看成是原问题的一个子问题的初始状态，解这个子问题就是找出一条由个子问题就是找出一条由v2到到t的最短路径。这条最短路径显然的最短路径。这条最短路径显然是是v2,v3,vk-1,t，如若不，如若不 然，然，设设v2,q3,qk-1,t是一条由是一条由v2到到t的更的更短路径，则短路径，则s,v2,q3,qk-1,t是一条比路径是一条比路径s,v2,v3,vk-1,t

114、更短的由更短的由s到到t的路径。与假设矛盾，故最优性原理成立。的路径。与假设矛盾，故最优性原理成立。因此它为使用动因此它为使用动态规划方法来解决多段图问题提供了可能。态规划方法来解决多段图问题提供了可能。六、动态规划方法的形式化描述六、动态规划方法的形式化描述 能能用用动动态态规规划划求求解解的的问问题题的的最最优优化化决决策策序序列列可可表表示示如如下下。设设S0是是问问题题的的初初始始状状态态。假假定定需需要要作作n次次决决策策xi, 1in。设设X1=r1,1,r1,2,r1,p1是是X1的的可可能能决决策策值值的的集集合合，而而S1, 1是是在在选选取取决决策策值值r1,j1以以后后所

115、所产产生生的的状状态态, 1j1p1。又又设设 是是相相应应于于状状态态S1,j1的的最最优优决决策策序序列列。那那末末，相相应应于于S0的的最最优优决决策策序序列列就就是是 |1j1p1中中最最优优的的序序列列，记记为为OPT = 。如如果果已已作作了了k-1次次决决策策，1k-1n。设设x1,xk-1的的最最优优决决策策值值是是r1,rk-1，它们所产生的状态为，它们所产生的状态为S1,Sk-1。又设。又设 是是xk的可能值的集合。的可能值的集合。 是选取决策值是选取决策值 后所产生的状态，后所产生的状态，1jkpk。 是相应于是相应于 的最优决策序的最优决策序列。因此，相应于列。因此，相

116、应于Sk-1的最优决策序列是的最优决策序列是 。于是相应于。于是相应于S0的最优决策序列为的最优决策序列为r1,rk-1，rk， 。七、两种求解方法七、两种求解方法（1 1）向前处理法：向前处理法：从最后阶段开始，以逐步向前递推的方式列从最后阶段开始，以逐步向前递推的方式列出求前一阶段决策值的递推关系式，即出求前一阶段决策值的递推关系式，即根据根据x xi+1i+1, ,x,xn n的那些最的那些最优决策序列来列出求取优决策序列来列出求取x xi i决策值的关系式，即：决策值的关系式，即：x xi i=f(x=f(xi+1i+1,x,xi+2i+2, ,x,xn n) ) 例子：在例子：在k

117、k段图问题中，设段图问题中，设 又设又设 是由是由 到到t t的最短路径，则的最短路径，则s s到到t t的最短路径是的最短路径是 中最短的那条路径。若设中最短的那条路径。若设 是是s s 到到t t的一条最短路径，的一条最短路径， 是路径上的中是路径上的中间结点，则间结点，则 就应分别是由就应分别是由s s到到v vi i和由和由v vi i到到t t的的最短路径。最短路径。 （2 2）向后处理法：向后处理法：根据根据x x1 1, ,x,xi-1i-1的那些最优决策序列列出的那些最优决策序列列出求求xixi的递推关系式。即：的递推关系式。即：xi=f(xxi=f(x1 1,x,x2 2,

118、,x,xi-1i-1) .) .下例是说明向前处理法在多段图中的使用下例是说明向前处理法在多段图中的使用见黑板见黑板 小结：无论是使用向前处理法还是使用向后处理法，都将小结：无论是使用向前处理法还是使用向后处理法，都将所有子问题的最优解保存下来。这样做的目的是为了便于逐步所有子问题的最优解保存下来。这样做的目的是为了便于逐步递推得到原问题的最优解并避免对它们的重复计算。由枚举法递推得到原问题的最优解并避免对它们的重复计算。由枚举法可知，不同决策序列的总数就其所取决策值而言是指数级的可知，不同决策序列的总数就其所取决策值而言是指数级的（如果决策序列由（如果决策序列由n n次决策构成，而每次决策有

119、次决策构成，而每次决策有p p种选择，那末种选择，那末可能的决策序列就有可能的决策序列就有p pn n个），个），而动态规划算法则可能有多项式而动态规划算法则可能有多项式的复杂度。的复杂度。 八、动态规划算法的求解步骤八、动态规划算法的求解步骤(1)(1)段化；段化；(2)(2)自顶向下的分析，测试问题本身是否满足最优化原理；自顶向下的分析，测试问题本身是否满足最优化原理；(3)(3)从底向上的计算，实现动态规划过程。从底向上的计算，实现动态规划过程。一、问题的描述一、问题的描述 例例4.1给出了多段图的定义，并且指出一个给出了多段图的定义，并且指出一个k段图的每一条由段图的每一条由源点源点s

120、到汇点到汇点t的路径可以看成是在的路径可以看成是在k-2个阶段中作出的某个决策个阶段中作出的某个决策序列的相应结果。第序列的相应结果。第i次决策就是确定次决策就是确定Vi+1中的哪个结点在这条中的哪个结点在这条路径上，路径上，1ik-2。进而还证明了最优性原理对多段图成立进而还证明了最优性原理对多段图成立，因，因此用动态规划方法有可能找到由此用动态规划方法有可能找到由s到到t的最小成本路径。的最小成本路径。 4.2 多段图多段图 二、问题分析：使用向前处理法二、问题分析：使用向前处理法求各阶段的递推关系式：求各阶段的递推关系式：（1）（2）若）若E，有，有COST(k-1,j)=c(j,t)，

121、若，若 E， 有有COST(k-1,j)=， 设：设： P(i,j) 是一条从是一条从Vi中的结点中的结点j到汇点到汇点t的最小成本路径，的最小成本路径， COST(i,j)是这条路的成本。是这条路的成本。 关键关键例子：对图例子：对图4.1的的5段图给出具体实现这一系列计算的步骤：段图给出具体实现这一系列计算的步骤： COST(3,6)=min6+COST(4,9),5+COST(4,10)=7 COST(3,7)=min4+COST(4,9),3+COST(4,10)=5 COST(3,8)=7 COST(2,2)=min4+COST(3,6),2+COST(3,7),1+COST(3,8

122、)=7 COST(2,3)=9， COST(2,4)=18， COST(2,5)=15 COST(1,1)=min9+COST(2,2),7+COST(2,3),3+COST(2,4), 2+COST(2,5)=16 于于是是由由s到到t的的最最小小成成本本路路径径的的成成本本为为16。如如果果在在计计算算每每一一个个COST(i,j)的的同同时时，记记下下每每个个状状态态（结结点点j）所所作作的的决决策策（即即，使使c(j,l)+COST(i+1,l)取取最最小小值值的的l值值），设设它它为为D(i,j)，则则可可容容易地求出这条最小成本路径。对于图易地求出这条最小成本路径。对于图4.1所示

123、的，可得到所示的，可得到 D(3,6)=10 D(3,7)=10 D(3,8)=10 D(2,2)=7 D(2,3)=6 D(2,4)=8 D(2,5)=8 D(1,1)=2 设这条最小成本路径是设这条最小成本路径是s=1,v2,v3,vk-1,t=12。立即可知，。立即可知，v2=D(1,1)=2,v3=D(2,D(1,1)=7和和v4=D(3,D(2,D(1,1)=D(3,7)=10。 三、算法设计三、算法设计 对对结结点点集集V的的结结点点按按下下述述方方式式排排序序：首首先先将将s结结点点编编成成1号号，然然后后对对V2中中的的结结点点编编号号，V3的的结结点点接接着着V2中中的的最最

124、后后一一个个编编号号继继续续往往下下编编最最后后将将t编编成成n号号。经经过过这这样样编编号号，Vi+1中中结结点点的的编编号号均均大大于于Vi中中结结点点的的编编号号（见见图图4.1）。于于是是，COST和和D都都可可按按n-1,n-2,1的的次次序序计计算算，而而无无需需考考虑虑COST，P和和D中中标标识识结结点点所所在在段段数数的的第第一一个个下下标标，因因此此它它们们的的第第一一个个下下标标可可在在算算法法中略去。所导出的算法是过程中略去。所导出的算法是过程FGRAPH。算法算法4.1 多段图的向前处理算法多段图的向前处理算法 FGRAPH(Elemtype E,int k, int

125、 n, Elemtype Pk) /输入是按段的顺序给结点编号的，有输入是按段的顺序给结点编号的，有n个结点的个结点的k段图。段图。E是是边集，边集，cij是边是边的成本。的成本。Pk是最小成本路径是最小成本路径/输入：多段图的顶点编号表，各顶点的边表和各边的成本函数输入：多段图的顶点编号表，各顶点的边表和各边的成本函数c(i，j)的表。的表。输出：从输出：从s到到t的一条最小成本路径上的各顶点以及成本的一条最小成本路径上的各顶点以及成本COST(l，s)。 1 COST n1 COST n0;0;2 for j2 for jn-1 to 1 by -1 /n-1 to 1 by -1 /计算

126、计算COST jCOST j；3 do 3 do 设设r r是这样一个结点，是这样一个结点， 且使且使cjr+ COSTr cjr+ COSTr 取最小值；取最小值；4 COSTj 4 COSTj cjr+ COSTr;cjr+ COSTr;5 Dj5 Djr;r;6 /6 /找一条最小成本路径；找一条最小成本路径；7 P 17 P 11 1；P kP kn;n;8 for j8 for j2 to k-1 /2 to k-1 /找路径上的第找路径上的第j j个结点。个结点。9 do 9 do 10 P j10 P jDP j-1;DP j-1;11 11 问题：问题：Dj,PjDj,Pj分别

127、存的是什么数据分别存的是什么数据？四、算法分析四、算法分析 过程过程FGRAPHFGRAPH的复杂分析相当简单。如果的复杂分析相当简单。如果G G用邻接表表示，那末用邻接表表示，那末第第4 4行的行的r r可以在与结点可以在与结点j j的度成正比的时间内算出。因此，如果的度成正比的时间内算出。因此，如果G G有有e e条边，则第条边，则第3-63-6行的行的forfor循环的时间是循环的时间是(n+e)(n+e)，第，第9-119-11行的行的forfor循环时间是循环时间是 。总的计算时间在。总的计算时间在 以内。除了输入所需要以内。除了输入所需要的空间外，还需要给的空间外，还需要给COST

128、COST，D D和和P P的空间。也可以使用向后处理法，的空间。也可以使用向后处理法，请自学请自学。五、多段图的应用五、多段图的应用资源分配问题资源分配问题 把把n个资源分配给个资源分配给r个项目的问题。个项目的问题。如果把如果把j个资源，个资源，0jn,分配分配给项目给项目i，所获得的净利是，所获得的净利是N(i,j)。要求按使得总净利达到最大值。要求按使得总净利达到最大值的方法把资源分配给这的方法把资源分配给这r个项目。这个问题可用一个个项目。这个问题可用一个r+1段图来段图来表示。其中表示。其中 1到到r之间的段之间的段i代表项目代表项目i。源点。源点s=V(1,0)，汇点，汇点t=V(

129、r+1,n)。段。段i为为2到到r时，每段都有时，每段都有n+1个结点个结点V(i,j), 0jn。 N(i,j)表示把表示把j个资源（个资源（0jn）,分配给项目分配给项目i，所获得的净利。，所获得的净利。 每个结点每个结点V(i,j)表示共把表示共把j个资源分配给了项目个资源分配给了项目1，2，,i-1。 当当j1且且1ir时，边时，边赋予赋予N(i,1-j)的成本值的成本值. 当当jn且且i=r即即边边具具有有的的形形式式时时，每每一一条条这这样的边被赋予样的边被赋予maxN(r,p)的成本值。的成本值。见黑板见黑板一、问题的描述一、问题的描述 某货郎要到若个城市去推销物品，各城市之间的

130、路程是已知某货郎要到若个城市去推销物品，各城市之间的路程是已知的，货郎从其所在城市出发，到其他的城市一次且仅一次，然的，货郎从其所在城市出发，到其他的城市一次且仅一次，然后返回其所在城市，问他应选择怎样的路线才能使所走的总路后返回其所在城市，问他应选择怎样的路线才能使所走的总路程最短？可以程最短？可以用一个有向图用一个有向图G=描述，该图是具有边成本描述，该图是具有边成本Cij的有向图，的有向图，Cij的定义为：对于所有的的定义为：对于所有的i,j,有有Cij0,若若 E，则，则Cij= .设设|V|=n，并假定，并假定n1，G的一条周游路的一条周游路线是包含线是包含V中每个结点的一个有向环中

131、每个结点的一个有向环。货郎担问题就是求取具。货郎担问题就是求取具有最小成本的周游路线。有最小成本的周游路线。4.3 货郎担问题货郎担问题二、问题的分析二、问题的分析1.是否是多阶段决策问题是否是多阶段决策问题;2.其最优决策序列是否满足最优性原理。其最优决策序列是否满足最优性原理。三、各阶段之间的递推关系式三、各阶段之间的递推关系式其中其中g(i,S)由结点由结点i出发，通过出发，通过S中的所有结点，在结点中的所有结点，在结点1终止的终止的一条最短路径长度。一条最短路径长度。 四、例子四、例子 例例子子：考考虑虑图图4.13(a)4.13(a)的的那那个个有有向向图图，其其边边长长由由图图4.

132、13(b)4.13(b)给出。给出。图图4.13(b)4.13(b)则当则当|S|=0，由上述递推公式（，由上述递推公式（1）可知：）可知： g(2, )=c21=5, g(3, )=c31=6; g(4, )=c41=8接着由公式（接着由公式（2）可得：）可得：当当|S|=1，g(2，3)=c23+g(3, )=15, g(2,4)=18; g(3,2)=18; g(3,4)=20,g(4,2)=13, g(4,3)=15当当|S|=2,g(2,3,4)=minc23+g(3,4),c24+g(4,3)=25;g(3,2,4)=minc32+g(2,4),c34+g(4,2)=25g(4,2

133、,3)=minc42+g(2,3),c43+g(3,2)=23见黑板见黑板 设设N N是用（是用（1 1）式计算）式计算g(1,V-1)g(1,V-1)以前需要计算以前需要计算g(i, S)g(i, S)数数目，目，又又因因为为在在|S|=k|S|=k时时，有有（2 2）求求g(i, g(i, S)S)的的值值要要进进行行k-1 k-1 次次比比较，所以总的计算时间为：较，所以总的计算时间为： . . 最后由公式（最后由公式（3）可得：）可得： g(1,2,3,4)=minc12+g(2,3,4),c13+g(3,2,4),c14+g(4,2,3)=min35,40,43=35五、时间复杂性分

134、析时间复杂性分析第五章第五章 回溯法回溯法 第第1 1节节 一般方法一般方法一、基本思想一、基本思想1 1 1 1、适用范围、适用范围、适用范围、适用范围（1 1）解空间很大）解空间很大（2 2）所要求的解必须能表示成）所要求的解必须能表示成一个一个n n元组（元组（x x1 1,x,x2 2,x,x3 3, ,x xn n) )，其，其中中x xi i取自某个有穷集取自某个有穷集S Si i。（3 3）要求的是答案解，而不是最优解。要求的是答案解，而不是最优解。要求的是答案解，而不是最优解。要求的是答案解，而不是最优解。（4 4）答案解需要满足一组约束条件。）答案解需要满足一组约束条件。2

135、2、基本思想、基本思想 假设集合假设集合S Si i的大小是的大小是m mi i，于是就有，于是就有m=mm=m1 1m m2 2m mn n个个n-n-元组可元组可能满足函数能满足函数P P 。所谓枚举方法是构造出这。所谓枚举方法是构造出这m m个个n-n-元组并逐一测元组并逐一测试它们是否满足试它们是否满足P P，从而找出该问题的解。而回溯法的基本思，从而找出该问题的解。而回溯法的基本思想是不断地用修改过的规范函数想是不断地用修改过的规范函数PiPi（x x1 1x xi i）（有时称为限界）（有时称为限界函数）去测试正在构造中的函数）去测试正在构造中的n-n-元组的部分向量（元组的部分向

136、量（x x1 1, , x xi i），），看其是否可能导致答案解。如果判定（看其是否可能导致答案解。如果判定（x x1 1, , x xi i）不可能导致）不可能导致答案解，那么就将可能要测试的答案解，那么就将可能要测试的m mi+1i+1m mn n个向量一概略去。因个向量一概略去。因此回溯算法作的测试次数比枚举方法作的次数（此回溯算法作的测试次数比枚举方法作的次数（m m次）要少得次）要少得多。（用树结构表示更形象）多。（用树结构表示更形象） 关键关键3 3、回溯法与贪心方法、动态规划方法的区别、回溯法与贪心方法、动态规划方法的区别 前者不是求问题的最优解，而是求答案解或最终解，因为前者

137、不是求问题的最优解，而是求答案解或最终解，因为它的解空间很大，一般能找到答案解就很不容易了。它的解空间很大，一般能找到答案解就很不容易了。4 4、显式约束与隐式约束、显式约束与隐式约束 用回溯法求解，它的解一般要求满足一组综合约束条件，用回溯法求解，它的解一般要求满足一组综合约束条件，这些约束条件分为以下两类：这些约束条件分为以下两类： 显式约束：显式约束：限定每个限定每个x xi i只从一个给定的集合只从一个给定的集合S Si i上取值。上取值。 显式约束条件常见的例子是显式约束条件常见的例子是： 当当 x xi i0 0 即即 S Si i=所有非负实数所有非负实数 当当 x xi i=0

138、=0或或x xi i=1 =1 即即 S Si i=0=0，11 当当 即即 这些显式约束条件可以与求解的问题的实例这些显式约束条件可以与求解的问题的实例I有关，也可以有关，也可以无关。满足显式约束的所有元组确定无关。满足显式约束的所有元组确定I的一个可能的解空间。的一个可能的解空间。注意：注意：这里的这里的“解空间解空间”是指满足显式约束条件的元组，并非是指满足显式约束条件的元组，并非一般意义上的解。一般意义上的解。 隐隐式式约约束束：规规定定I的的解解空空间间中中那那些些实实际际上上满满足足规规范范函函数数的的元元组组。因因此此，隐隐式式约约束束描描述述了了xi必必须须彼彼此此相相关关的的

139、情情况况。该该约约束束一一般可以进一步提炼出规范函数。般可以进一步提炼出规范函数。5 5、使用回溯法的关键、使用回溯法的关键 隐式约束隐式约束 规范函数规范函数提炼提炼二、例子二、例子例例1 1（8-8-皇后问题）一个经典的组合问题是在一个皇后问题）一个经典的组合问题是在一个8x88x8棋盘上棋盘上放置八个皇后，且使得每两个之间都不能互相放置八个皇后，且使得每两个之间都不能互相“攻击攻击”，也，也就是使得每两个都不在同一行、同一列及同一条斜角线上。就是使得每两个都不在同一行、同一列及同一条斜角线上。给棋盘的行和列都编上给棋盘的行和列都编上1 1到到8 8的号码（见图）。这些皇后也可的号码（见图

140、）。这些皇后也可给以给以1 1到到8 8的编号。由于一个皇后应在不同的行上，为不失一的编号。由于一个皇后应在不同的行上，为不失一般性，故可以假定皇后般性，故可以假定皇后i i将放在行将放在行i i上。因此，上。因此，8 8皇后问题可以皇后问题可以表示成表示成8-8-元组元组 , ,其中其中x xi i是放置皇后是放置皇后i i所在的列号。所在的列号。使用这种表示的使用这种表示的显式约束条件显式约束条件是是S Si i=1=1，2 2，3 3，4 4，5 5，6 6，7 7，88，1i81i8。于是，解空间由于是，解空间由 个个8-8-元组所组成。元组所组成。这个问题的隐式约束条件是，这个问题的

141、隐式约束条件是，没有两个没有两个 可以相同（即，所有可以相同（即，所有皇后都必须在不同的列上）而且没有两皇后可以在同一条斜角皇后都必须在不同的列上）而且没有两皇后可以在同一条斜角线上。线上。这两个约束条件的前者意味着所有的解都是这两个约束条件的前者意味着所有的解都是8-8-元组（元组（1 1，2 2，3 3，4 4，5 5，6 6，7 7，8 8）的置换。）的置换。于是解空间的大小由于是解空间的大小由8 88 8个元组减少到个元组减少到8 8！个元组。至于如何根据！个元组。至于如何根据x xi i来列出第二个约束条件将在来列出第二个约束条件将在6.26.2节介绍。把图节介绍。把图6.16.1中

142、的解表示中的解表示为一个为一个8-8-元组就是（元组就是（4 4，6 6，8 8，2 2，7 7，1 1，3 3，5 5）。）。例例2（子子集集和和数数问问题题） 已已知知n+1个个正正数数：wi,1in,和和M。要要求求找找 出出 wi的的 和和 数数 是是 M的的 所所 有有 子子 集集 。 例例 如如 ， 若若 n=4，（w1,w2,w3,w4）=(11,13,24,7),M=31，则则满满足足要要求求的的子子集集是是（11，13，7）和和（24，7）。值值得得指指出出的的是是，通通过过给给出出其其和和数数为为M的的那那些些wi的的下下标标来来表表示示解解向向量量比比直直接接用用这这些些

143、wi表表示示解解向向量量更更为为方方便便。因因此此，这这两两个个解解就就是是由由向向量量（1，2，4）和和（3，4）所描述。）所描述。 第第 一一 种种 表表 示示 法法 （ 变变 长长 表表 示示 法法 ） ： 所所 有有 的的 解解 都都 是是 k-元元 组组 , 1kn，并且不同的解可以是大小不同的元组。，并且不同的解可以是大小不同的元组。 显式约束条件：显式约束条件：要求要求x xi ij|jj|j是一个整数且是一个整数且1jn1jn。 隐隐式式约约束束条条件件：要要求求没没有有两两个个x xi i是是相相同同的的且且相相应应的的w wi i的的和和数数是是M M。为为了了避避免免产产

144、生生同同一一个个子子集集的的重重复复情情况况（例例如如，（1 1，2 2，4 4）和和（1 1，4 4，2 2）表表示示同同一一个个子子集集），附附加加另另一一个个隐隐式式约约束束条条件件：x xi ix0 do 3 4 if 还剩有没检验过的还剩有没检验过的Xk使得使得 5 XkR(X1,Xk-1) and C(X1,Xk)=true6 then if (X1,Xk) 是一条抵达一答案结点的路径是一条抵达一答案结点的路径7 then print (X1,Xk);8 kk+1;9 10 else kk-1;/说明不剩没有检验的说明不剩没有检验的X(k)或或Ck(X(1).X(k)=false1

145、1 非递归形式非递归形式算法算法6.2 递归递归回溯算法回溯算法 RBackTrack(k) /此此算算法法是是对对回回溯溯算算法法的的抽抽象象递递归归描描述述。进进入入算算法法时时，解向量解向量Xn的前的前k-1个分量个分量X1,Xk-1已赋值已赋值/while 满足下式的每个满足下式的每个X(k) XkR(X1,Xk-1) and C(X1,Xk)=true do if(X1,Xk)是一条已抵达一答案结点的路径是一条已抵达一答案结点的路径 then print(X1,Xk) ; RBackTrack(k+1) 递归递归可求可求出所出所有的有的解且解且解的解的元组元组大小大小可变可变 注意注

146、意 （1 1）在算法中，满足限界函数的）在算法中，满足限界函数的xkxk 被逐一生成，同时还要检被逐一生成，同时还要检测在生成测在生成xkxk 时，是否已经找到一个解。当时，是否已经找到一个解。当whilewhile循环结束循环结束的时候，所有可以生成的的时候，所有可以生成的xkxk 都已经被生成。所以，用递都已经被生成。所以，用递归方法实现的回溯算法可以得到问题的全部解，而且得到归方法实现的回溯算法可以得到问题的全部解，而且得到的解向量的大小不是固定的。的解向量的大小不是固定的。 （2 2）当）当XkR(X1,XkR(X1,Xk-1) and C(X1,Xk-1) and C(X1,Xk-1

147、) ,Xk-1) =true =true 时，执行时，执行ifif和函数调用两个语句。和函数调用两个语句。（3 3）可以求出所有的解且解的元组大小可变。）可以求出所有的解且解的元组大小可变。（4 4）执行过程见层次分析图，以书上图）执行过程见层次分析图，以书上图4-104-10为例。为例。见黑板调用过程见黑板调用过程二、问题分析二、问题分析( (找限界函数找限界函数) )找限界函数或称规范函数找限界函数或称规范函数place(kplace(k),),它使得它使得X(iX(i) ) X(kX(k) )且且X(i)-X(kX(i)-X(k) ) ABS(i-kABS(i-k)()( i=1,2,.

148、k-1) i=1,2,.k-1)以一个以一个4*44*4棋盘为例子棋盘为例子算法算法6.4 可以放置一个新皇后吗？可以放置一个新皇后吗？ 6.2 8-6.2 8-皇后问题皇后问题一、问题的描述一、问题的描述 8-8-皇后问题实际上很容易一般化为皇后问题实际上很容易一般化为n-n-皇后问题，即要求皇后问题，即要求找出一个找出一个n nn n棋盘上放置棋盘上放置n n个皇后并使其不能互相攻击的所有个皇后并使其不能互相攻击的所有方案方案。关键关键以以下下函函数数Place(kPlace(k) )，用用来来判判定定将将皇皇后后k k放放在在棋棋盘盘的的第第x xk k 列列是是否否可可行行，如如果果皇

149、皇后后k k可可以以放放在在第第x xk k 列列，那那么么Place(kPlace(k) )的的返返回回值值为为真真，否否则则返返回回值值为为假假，显显然然，在在进进入入该该函函数数前前，前前k-1k-1皇皇后后已已经经放放置置好好，即即xnxn 已已确确定定k-1k-1个个值值。Place()Place()函函数的描述如下：数的描述如下： Place(intPlace(int k) k)1 i 1;1 i 1;/设置设置i i值；值；2 while i k2 while i 03 while k 04 do4 do5 5 xkxk xkxk + 1; + 1;/将第将第k k行的皇后行的皇

150、后k k后移一列；后移一列；6 6 while while xknxkn and and Place(kPlace(k)=)=FALSEFALSE / /确定皇后确定皇后k k的列数的列数xkxk ；7 7 do do xkxkxkxk + 1; + 1;8 8 if if xknxkn9 9 then then10 10 if k = n if k = n/n/n个皇后的位置都已经确定，输出；个皇后的位置都已经确定，输出；1111 then for i 1 to n then for i 1 to n1212 do print do print（xixi ）; ;13 13 else/n e

151、lse/n个皇后的位置还没全确定，考虑下一个皇后的位置；个皇后的位置还没全确定，考虑下一个皇后的位置；14 14 k k + 1; k k + 1;15 15 xkxk 0; 0;1616/xkn17 17 else else /当前行皇后无位置放，将上一行的皇后的位置重新安排；当前行皇后无位置放，将上一行的皇后的位置重新安排；1818 k k k k 1; 1; / /回溯回溯/1919/while/while一、问题的描述一、问题的描述 假假定定有有n个个不不同同的的正正数数（通通常常称称为为权权），要要求求找找出出这这些些数数中中所所有有使使得得其其和和数数为为M的的组组合合。例例6.2

152、和和6.4说说明明了了如如何何用用大大小小固固定定或或变变化化的的元元组组来来表表示示这这个个问问题题。本本节节将将利利用用大大小小固固定定的的元元组组来来研研究究一一种种回回溯溯法法，在在此此情情况况下下，解解向向量量的的元元素素X（i）取取1或或0值，它表示是否包含权数值，它表示是否包含权数W（i）。）。 6.3 6.3 子集和数问题子集和数问题二、问题分析二、问题分析对于图对于图6.46.4，其左儿子对应于，其左儿子对应于X X（i i）=1=1，右儿子对应于，右儿子对应于X X（i i）=0=0。限界函数的一种简单选择是，当且仅当。限界函数的一种简单选择是，当且仅当 时，时， 找规范函

153、数找规范函数显显然然，如如果果这这个个条条件件不不满满足足，X（1），X(k)就就不不能能导导致致一一个个答答案案结结点点。如如果果假假定定这这些些W（i）一一开开始始就就是是按按非非降降次次序序排排列的，列的，那么这些限界函数可以被强化。那么这些限界函数可以被强化。在这种情况下，如果在这种情况下，如果 则则X（1）,X(k)就就不不能能导导致致一一个个答答案案结结点点。因因此此将将要要使使用用的的限界函数是限界函数是 Bk(X(1),X(k)=ture 当且仅当当且仅当 且且 关键关键三、算法设计三、算法设计算法算法6.6 子集和数问题的递归回溯算法子集和数问题的递归回溯算法SumOfSub

154、(intSumOfSub(int s , s , intint k , k , intint r) r) /找找W(1:n)中中和和数数为为M的的所所有有子子集集。进进入入此此过过程程时时X(1),X(k-1)的的值值已已确确定定。 且且 。这这些些W(j)按按非非降次序排列。假定降次序排列。假定W(1)M， / /生成左儿子。注意，由于生成左儿子。注意，由于B Bk-1k-1=true,=true,因此因此s+W(ks+W(k) M/) M/1 1 xkxk 1; 1;/将第将第k k个正数计入解向量；个正数计入解向量；2 2if (s + if (s + wkwk) = M) = M/将第

155、将第k k个正数计入解向量后，得到一个可行解；个正数计入解向量后，得到一个可行解；3 3then for i1 to k then for i1 to k 4 4 do do print(xiprint(xi););/输出这个可行解；输出这个可行解；5 5elseelse/第第k k个正数可以计入解向量，递归调用个正数可以计入解向量，递归调用SumOfSubSumOfSub()()算法；算法；6 6 if (s + if (s + wkwk + + wkwk + 1)M + 1)M7 7 then then SumOfSub(sSumOfSub(s + + wkwk , k + 1 , r ,

156、 k + 1 , r wkwk); ); /以下生成右儿子和计算以下生成右儿子和计算BkBk的值的值8 8if (s + r if (s + r wk)Mwk)M and (s + wk+1)M) and (s + wk+1)M)9 9 then then /第第k k个正数不可以计入解向量，递归调用个正数不可以计入解向量，递归调用SumOfSubSumOfSub()()算法。算法。1010 xkxk 0; 0;1111 SumOfSub(sSumOfSub(s , k + 1 , r - , k + 1 , r - wkwk););1212 问题：问题： (1)为什么在为什么在X（k)=1时

157、，没有测试时，没有测试 (2)第第8语句的分支何时执行语句的分支何时执行? 用层次分析法可以得到该过程生成的一个状态空间树，用层次分析法可以得到该过程生成的一个状态空间树，见下图。见下图。一、基本思想一、基本思想1.1. 适用范围适用范围（1）解空间很大。）解空间很大。（2）希望以）希望以最小的成本或代价最小的成本或代价寻找答案解。寻找答案解。第六章第六章 分枝限界法分枝限界法第一节第一节 方法概述方法概述2.2.基本思想基本思想 相对于回溯法而言，若能使用更有效的约束函数来控制相对于回溯法而言，若能使用更有效的约束函数来控制搜索进程，使之能以最小的代价朝着状态空间树上具有答案搜索进程，使之能

158、以最小的代价朝着状态空间树上具有答案解（即找这个解将花费的代价最小）的分枝推进，以便尽快解（即找这个解将花费的代价最小）的分枝推进，以便尽快地找到一个答案解地找到一个答案解, ,这就是分枝限界法。它是使用约束函数的这就是分枝限界法。它是使用约束函数的广度优先生成方法。广度优先生成方法。估值函数估值函数-关键关键3.与回溯法的区别与回溯法的区别( (思考：两者的共同点思考：两者的共同点) )（1）回溯法是结合规范函数的深度优先节点生成方法，而分）回溯法是结合规范函数的深度优先节点生成方法，而分枝限界法是结合了估值函数的广度优先生成方法。枝限界法是结合了估值函数的广度优先生成方法。（2）回溯法是找

159、一个或全部解，但是分枝限界法是希望用最）回溯法是找一个或全部解，但是分枝限界法是希望用最小的成本或代价找答案解。小的成本或代价找答案解。问题：规范函数和估值函数的作用有什么不同？问题：规范函数和估值函数的作用有什么不同？问题：规范函数和估值函数的作用有什么不同？问题：规范函数和估值函数的作用有什么不同？4.4.应用范围应用范围 货郎担问题，货郎担问题，0/10/1背包问题，工作分配问题。背包问题，工作分配问题。5.5.两种基本搜索两种基本搜索 分枝限界法是限界函数的分枝限界法是限界函数的广度优先生成方法广度优先生成方法，其中对于儿子，其中对于儿子结点的存放，可以是队列也可以是堆栈，即宽度优先生

160、成和结点的存放，可以是队列也可以是堆栈，即宽度优先生成和D-D-检索或称检索或称FIFOFIFO和和FILOFILO。（1 1）FIFOFIFO搜索法：它对于状态空间树的搜索是这样的：对于当搜索法：它对于状态空间树的搜索是这样的：对于当前扩展节点，先从左到右地产生它的所有儿子，然后按约束函前扩展节点，先从左到右地产生它的所有儿子，然后按约束函数检查，只要儿子不是死结点，就将它加入活节点表中（按队数检查，只要儿子不是死结点，就将它加入活节点表中（按队列的顺序）。然后从活结点表中依次取出一个结点作为当前扩列的顺序）。然后从活结点表中依次取出一个结点作为当前扩展结点，并产生它的所有儿子加入活结点表的

161、末尾，产生顺序展结点，并产生它的所有儿子加入活结点表的末尾，产生顺序仍是从左到右的。只要当前扩展结点的所有可以产生的儿子还仍是从左到右的。只要当前扩展结点的所有可以产生的儿子还没有产生完，就不考虑下一个结点。如果只要求出一个解，搜没有产生完，就不考虑下一个结点。如果只要求出一个解，搜索进行到产生一个解为止，如果要求出所有的解，搜索一直进索进行到产生一个解为止，如果要求出所有的解，搜索一直进行到活节点表空为止。行到活节点表空为止。（2 2）FILOFILO搜索法：与搜索法：与FIFOFIFO不同的是：活节点表是堆栈，开始不同的是：活节点表是堆栈，开始时，堆栈只有一个节点，它是根节点，即是当前扩展

162、节点，先时，堆栈只有一个节点，它是根节点，即是当前扩展节点，先产生它的所有儿子，并依次加入到栈中，然后删除这个节点，产生它的所有儿子，并依次加入到栈中，然后删除这个节点，并将栈顶的那个活节点变成当前扩展节点，搜索一直进行到找并将栈顶的那个活节点变成当前扩展节点，搜索一直进行到找到一个答案节点或栈为空才终止。到一个答案节点或栈为空才终止。见图例。见图例。注意：以上两种基本的搜索都必须结合注意：以上两种基本的搜索都必须结合约束函数约束函数来控制搜索进来控制搜索进程，否则就不能为更快找到或逼近一个解而有效地选择下一个程，否则就不能为更快找到或逼近一个解而有效地选择下一个扩展节点。扩展节点。二、二、估

163、值函数估值函数1 1、最小代价搜索法（、最小代价搜索法（LC-LC-搜索）：这种搜索对一棵状态空间树搜索）：这种搜索对一棵状态空间树定义一个判定函数，在搜索此树时，对每一个活节点产生一个定义一个判定函数，在搜索此树时，对每一个活节点产生一个函数值，函数值，通过对这些函数值的分析，在活节点表中选择一个最通过对这些函数值的分析，在活节点表中选择一个最有利的节点作为当前扩展节点，有利的节点作为当前扩展节点，从而在一定程度上可以克服搜从而在一定程度上可以克服搜索的盲目性，以期尽快找到答案解。索的盲目性，以期尽快找到答案解。根据估值函数根据估值函数2.2.估值函数：估值函数：以上的判定函数可以根据从一个

164、活节点直到到达以上的判定函数可以根据从一个活节点直到到达一个答案节点所需的计算量来给定。但是这往往是很困难的，一个答案节点所需的计算量来给定。但是这往往是很困难的，因此只能考虑给出一个估值函数来代替。因此只能考虑给出一个估值函数来代替。找适当的估值函数是分支限界法的关键找适当的估值函数是分支限界法的关键3 3.估值函数的作用：估值函数的作用： 是为了找到一个更有利的是为了找到一个更有利的E节点，从而花费最小的代价找到节点，从而花费最小的代价找到答案解，这是答案解，这是因为分枝限界法是广度优先生成。（因为分枝限界法是广度优先生成。（与回溯法中与回溯法中的规范函数的作用相比较）的规范函数的作用相比

165、较）4 4.估值函数的选取：常用问题的目标函数做估值函数。估值函数的选取：常用问题的目标函数做估值函数。关键关键5. 15-5. 15-迷问题：迷问题： 它是在一个它是在一个4*44*4的方格棋盘上，将数字的方格棋盘上，将数字1 1，2 2，3 3，1414，1515以以任意顺序置入棋盘的各个方格中，空出一格。问题是希望通过任意顺序置入棋盘的各个方格中，空出一格。问题是希望通过有限次的移动，把一个给定的初始状态变成如下（有限次的移动，把一个给定的初始状态变成如下（b)b)的目标状的目标状态。移动的规则是：每次只能在空格周围的四个数字中任选一态。移动的规则是：每次只能在空格周围的四个数字中任选一

166、个移入空格。个移入空格。定义：定义：l(i)是棋盘上第是棋盘上第i+1格到第格到第16格中，较格中，较 i 中的棋子号码小中的棋子号码小的棋子个数。的棋子个数。定理定理8.1 对于一个给定的初态，如果和对于一个给定的初态，如果和 +j+k 是偶数，是偶数，那么这个初态就可以变成目标状态，其他的任何初态都不可能那么这个初态就可以变成目标状态，其他的任何初态都不可能变成目标状态。变成目标状态。两个判定函数：两个判定函数：C1(X)和和C2(X)C1(X)：在节点：在节点X的状态下，没有达到目标状态下正确位置的的状态下，没有达到目标状态下正确位置的数字个数，数字个数，C2(X): ，这里，这里j表示

167、空格的位置。表示空格的位置。例如：例如：C C1(1)=C(1)=C1(5)=6(5)=6估值函数的一般形式：估值函数的一般形式： =f(X)+ =f(X)+ 其中：其中： f(X)f(X)是从状态空间树的根节点到是从状态空间树的根节点到X X的路径的长，的路径的长， 是在以是在以X X为根的子树上到达一个答案节点的最短路径长的估计为根的子树上到达一个答案节点的最短路径长的估计值。值。三、三、LC-LC-搜索的形式化描述搜索的形式化描述 设设T T是一棵状态空间树，是一棵状态空间树， c(c(. .) ) 是是T T中结点的成本函数。如中结点的成本函数。如果果X X是是T T中的一个结点，则中

168、的一个结点，则 c(X)c(X)是其根为是其根为X X的子树中任一答案结的子树中任一答案结点的最小成本。从而，点的最小成本。从而，c(T)c(T)是是T T中最小成本答案结点的成本。中最小成本答案结点的成本。如前所述，要找到一个如上定义且易于计算的函数如前所述，要找到一个如上定义且易于计算的函数c(. .) 通常是通常是很困难的，为此使用一个对很困难的，为此使用一个对c(. .) 估值的启发性函数估值的启发性函数 c c(. .)来代来代替。这个启发函数应是易于计算的并且一般有如下性质，如果替。这个启发函数应是易于计算的并且一般有如下性质，如果X X是一个答案结点或者是一个叶结点，则是一个答案

169、结点或者是一个叶结点，则 c c（X X）= c= c(X) (X) 。过程过程LCLC（算法（算法6.16.1）用）用c (X )去寻找一个答案结点。去寻找一个答案结点。这个算法用了这个算法用了两个子算法两个子算法LEASTLEAST（X X）和）和ADDADD（X X），它们分别将一个活结点从），它们分别将一个活结点从活结点表中删去或加入。活结点表中删去或加入。 LEASTLEAST（X X）找找一一个个具具有有最最小小的的 C C 值值的的活活结结点点，从从活活结结点点表表中中删去这个结点，并将此结点放在变量删去这个结点，并将此结点放在变量X X中返回。中返回。 ADDADD（X X）将

170、新的活结点）将新的活结点X X加到活结点表。加到活结点表。 通通常常把把这这个个活活结结点点表表作作成成一一个个min-min-堆堆来来使使用用。过过程程LCLC输输出出找找到到的的答答案案结结点点到到根根结结点点T T的的那那条条路路径径。如如果果使使用用PARENTPARENT信信息息段段将将活活结点结点X X与它的父亲相连接，这条路径就很容易输出了与它的父亲相连接，这条路径就很容易输出了。以下是以下是LC-LC-检索算法检索算法LC(Elemtype TLC(Elemtype T，Elemtype cElemtype c )的描述的描述LC(Elemtype TLC(Elemtype T

171、，Elemtype cElemtype c )/)/为找一个答案结点检索为找一个答案结点检索T T；/书上的算法有错，请修改书上的算法有错，请修改1 1if( Tif( T是答案结点是答案结点) )2 2then then 输出输出T T；return;return;3 3E ET T； /扩展结点；扩展结点；4 4 将活结点表初始化为空将活结点表初始化为空; ;5 while (1) do5 while (1) do6 6 7 7 for (E for (E的每个儿子的每个儿子X) X) 8 8 do if (X do if (X是答案结点是答案结点) ) 9 then 9 then 输出从

172、输出从X X到到T T的那条路径的那条路径; ;10 return;10 return;11 ADD(X); /X11 ADD(X); /X是新的活结点；是新的活结点；12 PARENT(X) 12 PARENT(X) E; /E; /指示到根的路径。指示到根的路径。1313 if ( if (不再有活结点不再有活结点) )14 then 14 then 输出输出“no answer nodeno answer node”;stop;stop;15 LEAST(E);15 LEAST(E);16 16 关键关键说说明明是是宽宽度度优优先先搜搜索索算法的正确性证明见书上，自学。算法的正确性证明见

173、书上，自学。注意注意: :此算法对于没有答案结点的无限状态空间树时此算法对于没有答案结点的无限状态空间树时, ,不会终止不会终止. .四四.LC.LC搜索的特性搜索的特性 在许多应用中，我们希望在所有的答案节点中找到一个最小在许多应用中，我们希望在所有的答案节点中找到一个最小成本的答案节点，成本的答案节点，但是但是LCLC搜索不一定能找到成本最小的答案节搜索不一定能找到成本最小的答案节点。如下：点。如下：1002021010 2020104其中上面的数是其中上面的数是C C的值，下面的数是的值，下面的数是C C的估计值。的估计值。定理定理7.2 7.2 在有限状态空间在有限状态空间T T中，对

174、于每一个节点中，对于每一个节点X X，令，令c c(X(X) )是是c(Xc(X) )的估计值且具有以下性质：对于每一对节点的估计值且具有以下性质：对于每一对节点Y Y，Z Z，当且仅，当且仅当当c(Yc(Y)c(Zc(Z) )时有时有c c(Y(Y)c c(Z(Z),),那么在使那么在使c c()()作为作为c()c()的估计的估计值时，算法值时，算法LCLC达到一个最小的成本答案节点而终止。达到一个最小的成本答案节点而终止。证明略证明略 一般情况下，只可能找到一个易于计算且具有如下性质的一般情况下，只可能找到一个易于计算且具有如下性质的c c(),(),对于每一个节点对于每一个节点X X， , ,在这种情况下，算法在这种情况下，算法LCLC不一定能找到最小成本的答案节点，但是如果对于每一个节点不一定能找到最小成本的答案节点，但是如果对于每一个节点X X有有 且对于答案节点且对于答案节点X X有有 c c(X(X)=)=c(Xc(X) )，则只要对，则只要对LCLC稍作稍作改动就可以得到一个在达到某个最小成本时终止的搜索算法。改动就可以得到一个在达到某个最小成本时终止的搜索算法。