算法分析与设计复习提纲课件

《算法分析与设计复习提纲课件》由会员分享，可在线阅读，更多相关《算法分析与设计复习提纲课件（79页珍藏版）》请在装配图网上搜索。

1、算法分析与设计算法分析与设计常熟理工学院计算机学院刘在德第第1章章 绪论绪论l掌握三种渐近符号（O、）的含义；l会用三种渐近符号表示算法的时间复杂度；l会用扩展递归技术分析算法时间的复杂性；对于表示算法时间的简单递推式，能够用扩展递归技术求出最终结果。lP15：例1.6lP18：实验1lP22：习题1.7三种渐近符号的含义三种渐近符号的含义l大大O符号符号：若存在两个正的常数c和n0，对于任意nn0，都有T(n)cf(n)，则称T(n)=O(f(n)l大大符号符号：若存在两个正的常数c和n0，对于任意nn0，都有T(n)cg(n)，则称T(n)=(g(n)l符号符号：若存在三个正的常数c1、c

2、2和n0，对于任意nn0都有c1f(n)T(n)c2f(n)，则称T(n)=(f(n)渐近符号表示算法时间复杂度渐近符号表示算法时间复杂度l定理定理1.1 若T(n)=amnm+am-1nm-1+a1n+a0(am0)，则有T(n)=O(nm)，且T(n)=(nm)，从而T(n)=(nm)l例例 T(n)5n28n1当n1时，5n28n15n28nn5n29n5n29n214n2O(n2)当n1时，5n28n15n2(n2)当n1时，14n25n28n15n2则：5n28n1(n2)用扩展递归技术分析算法时间的用扩展递归技术分析算法时间的复杂性复杂性l扩展递归技术扩展递归技术：将递推关系式中右

3、边项根据递推式进行逐次替换，得到求和表达式l例例 第第2章章 NP完全理论完全理论 l对于简单的判定问题，会画判定树。l判定判定树树（Decision Trees）是一棵二叉树：它的每一个内部结点对应一个形如xy的比较，如果关系成立，则控制转移到该结点的左子树，否则，控制转移到该结点的右子树，它的每一个叶子结点表示问题的一个结果。例例 对三个数进行排序的判定树对三个数进行排序的判定树 第第3章章 蛮力法蛮力法 l掌握改进的串匹配算法KMP算法l理解n个元素的生成排列对象l理解n个元素组成的集合的生成子集l理解0/1背包问题l理解TSP问题KMP算法算法lKMP算法思路：l如果某趟在Si和Tj匹

4、配失败后，指针i不回溯；模式T向右滑动至某个位置k，使得tk对准si继续进行匹配。l怎么求k？l模式T=“t1t2tm”中的每一个字符tj都对应一个k，显然k与S无关。用nextj表示tj对应的k值，则t1tk-1既是t1tj-1的真前缀，又是t1tj-1的真后缀的最长子串，称k是tj的前缀函数值，它等于最长子串长度加1。next数组的定义数组的定义lnext数组定义如下：t1t2t3t4t5t6a b a b a c真前缀 真后缀t1=t5,t1t2t3=t3t4t5a和aba都是ababa的真前缀和真后缀，但aba的长度最大next6=3+1=4，即当t6和si匹配失败后，将t4和si比较

5、l一个求k的例子：next数组的求法：数组的求法：l已求出next1,nextj，咋求nextj+1?l设k是tj的前缀函数值，从而有t1t2tk-1=tj-k+1tj-k+2tj-1l比较tk和tj，得2种情况：l(1)tk=tj：说明t1tk-1tk=tj-k+1tj-1tj，则nextj+1=k+1；l(2)tktj：此时要找出t1tj-1的后缀中第2大真前缀nextnextj=nextk,t1tnextk-1=tj-nextk+1tj-1，再比较tnextk和tj，又会出现2种情况：next数组的求法：数组的求法：l当tnextk=tj时，与(1)类似，nextj+1=nextk+1；

6、当不等时，找第3大真前缀，重复(2)的过程，直至找到t1tj-1后缀中的最大真前缀，l或确定t1tj-1的后缀中没有最大真前缀，此时nextj+1=1。算法算法3.4 KMP算法中求算法中求next数组数组lvoid GetNext(char T,int next)/下标从1开始lnext1=0;j=1;k=0;lwhile(j=m)lIf(k=0)|(Tj=Tk)j+;k+;nextj=k;llelse k=nextkl算法算法3.5 KMP算法算法l1.在串S和T中分别设定比较的起始下标i和j；l2.循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕l2.1 如Si=Tj，则继续

7、比较S和T的下一字符；否则l2.2 将j向右滑动到nextj位置，即j=nextj；l2.3 如果j=0，则将i和j分别加1，准备下一趟比较；l3.如果T中所有字符均比较完毕，则返回匹配的起始下标，否则返回0。生成排列对象生成排列对象l思路：假定已生成了1,2,n-1的所有(n-1)!个排列，可以把n插入到n-1个元素的每一种排列的n个位置中去，得到问题规模为n的所有排列。这时排列总数为n(n-1)!=n!。l时间复杂性：O(n!)l算法3.9 生成排列对象（伪代码）l1.生成初始排列1；l2.for(i=2;i=n;i+)lfor(j=1;j=1;k-)将i插入到第j个排列中的第k个位置；生

8、成子集生成子集l思路：n个元素组成的集合A=a1,a2,an的所有2n个子集与长度为n的所有2n个比特串之间存在一一对应关系。建立这种关系的方法是为每个子集指定一个比特串b1b2bn，如果ai属于该子集，则bi=1，否则bi=0(1in)。如3个元素组成的集合，比特串110表示a1a2，比特串000表示。算法算法3 3.10 10 生成子集生成子集l1.初始化一个长度为n的比特串s=000，并将对应的子集输出；l2.for(i=1;i1;l bm=m1;l bm=m1;l product=rmul(halfn,bm)+m;l l return product;llint rmul(int n,

9、int m)/*方法方法2：非递归法非递归法*/l int result=0;l while(n!=0)l l if(n%2=0)m=m1;l elsel l result=result+m;m=m1;l l return result;l第第6章章 动态规划法动态规划法l掌握动态规划法的设计思想l掌握动态规划法在TSP问题和0/1背包问题中的应用。l给出一个TSP或者0/1背包问题的实例，能够写出它的动态规划过程。lP134：实验6动态规划法的设计思想动态规划法的设计思想 动态规划法将待求解问题分解成若干个动态规划法将待求解问题分解成若干个相互重相互重叠叠的子问题，每个子问题对应决策过程的一

10、个的子问题，每个子问题对应决策过程的一个阶段阶段，一般来说，子问题的重叠关系表现在对给定问题求一般来说，子问题的重叠关系表现在对给定问题求解的解的递推关系递推关系（也就是动态规划函数）中，将子问（也就是动态规划函数）中，将子问题的解求解一次并题的解求解一次并填填入入表表中，当需要再次求解此子中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。次求解，从而避免了大量重复计算。原问题的解 原问题 填 表子问题1子问题2子问题n动态规划法的求解过程n=5时分治法计算斐波那契数的过程。F(5)F(4)F(3)F(

11、3)F(2)F(2)F(1)F(2)F(1)F(1)F(0)F(1)F(0)F(1)F(0)例：计算斐波那契数：01234567890112358132134动态规划法求解斐波那契数F(9)的填表过程：注意到，计算F(n)是以计算它的两个重叠子问题 F(n-1)和F(n-2)的形式来表达的，所以，可以设计一张表填入n+1个F(n)的值。TSP问题问题TSP问题问题是指旅行家要旅行是指旅行家要旅行n个城市，要求各个城个城市，要求各个城市市经历经历且且仅经历仅经历一次然后回到出一次然后回到出发发城市，并要求所城市，并要求所走的路程最短。走的路程最短。各个城市各个城市间间的距离可以用代价矩的距离可以

12、用代价矩阵阵来表示。来表示。C=367523642375带权图的代价矩阵带权图的代价矩阵假设从顶点i出发，令d(i,V)表示从顶点i出发经过V中各个顶点一次且仅一次，最后回到出发点i的最短路径长度，开始时，VVi，于是，TSP问题的动态规划函数为：d(i,V)=mincik+d(k,Vk)(kV)（式6.5）d(k,)=cki(ki)（式6.6）这是最后一个阶段的决策，而：这是最后一个阶段的决策，而：d(1,2,3)=minc12+d(2,3),c13+d(3,2)d(2,1,3)=minc21+d(1,3),c23+d(3,1)d(3,1,2)=minc31+d(1,2),c32+d(2,1

13、)这一阶段的决策又依赖于下面的计算结果：这一阶段的决策又依赖于下面的计算结果：d(1,2)=c12+d(2,)d(2,3)=c23+d(3,)d(3,2)=c32+d(2,)d(1,3)=c13+d(3,)d(2,1)=c21+d(1,)d(3,1)=c31+d(1,)从城市从城市0出发经城市出发经城市1、2、3然后回到城市然后回到城市0的最短路径长度是：的最短路径长度是：d(0,1,2,3)=minc01+d(1,2,3),c02+d(2,1,3),c03+d(3,1,2)而下式可以直接获得（括号中是该决策引起的状态转移）：而下式可以直接获得（括号中是该决策引起的状态转移）：d(1,)=c1

14、0=5(10)d(2,)=c20=6(20)d(3,)=c30=3(30)再向前倒推，有：再向前倒推，有：d(1,2)=c12+d(2,)=2+6=8(12)d(1,3)=c13+d(3,)=3+3=6(13)d(2,3)=c23+d(3,)=2+3=5(23)d(2,1)=c21+d(1,)=4+5=9(21)d(3,1)=c31+d(1,)=7+5=12(31)d(3,2)=c32+d(2,)=5+6=11(32)再向前倒退，有：再向前倒退，有：d(1,2,3)=minc12+d(2,3),c13+d(3,2)=min2+5,3+11=7(12)d(2,1,3)=minc21+d(1,3)

15、,c23+d(3,1)=min4+6,2+12=10(21)d(3,1,2)=minc31+d(1,2),c32+d(2,1)=min7+8,5+9=14(32)最后有：最后有：d(0,1,2,3)=minc01+d(1,2,3),c02+d(2,1,3),c03+d(3,1,2)=min3+7,6+10,7+14=10(01)所所以以，从从顶顶点点0出出发发的的TSP问问题题的的最最短短路路径径长长度度为为10，路路径径是是01230。算法6.1TSP问题 1for(i=1;in;i+)/初始化第0列 di0=ci0;2for(j=1;j2n-1-1;j+)for(i=1;iV(n-1,C)

16、，表明第n个物品被装入背包，前n-1个物品被装入容量为C-wn的背包中；否则，第n个物品没有被装入背包，前n-1个物品被装入容量为C的背包中。依此类推，直到确定第1个物品是否被装入背包中为止。由此，得到如下函数：（式6.13）设n个物品的重量存储在数组wn中，价值存储在数组vn中，背包容量为C，数组Vn+1C+1存放迭代结果，其中Vij表示前i个物品装入容量为j的背包中获得的最大价值，数组xn存储装入背包的物品，动态规划法求解0/1背包问题的算法如下：算法6.30/1背包问题 int KnapSack(int n,int w,int v)for(i=0;i=n;i+)/初始化第0列 Vi0=0

17、;for(j=0;j=C;j+)/初始化第0行 V0j=0;for(i=1;i=n;i+)/计算第i行，进行第i次迭代 for(j=1;j=C;j+)if(j0;i-)if(VijVi-1j)xi=1;j=j-wi;else xi=0;return VnC;/返回背包取得的最大价值第第7章章 贪心法贪心法l掌握贪心法的设计思想l掌握贪心法在TSP问题中的应用l掌握贪心法在背包问题中的应用lP155：实验7贪心法的求解过程贪心法的求解过程 用贪心法求解问题应该考虑如下几个方面：（1）候选集合C：为了构造问题的解决方案，有一个候选集合C作为问题的可能解，即问题的最终解均取自于候选集合C。例如，在付

18、款问题中，各种面值的货币构成候选集合。（2）解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。例如，在付款问题中，已付出的货币构成解集合。（3）解决函数solution：检查解集合S是否构成问题的完整解。例如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款。（4）选择函数select：即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。例如，在付款问题中，贪心策略就是在候选集合中选择面值最大的货币。（5）可行函数feasible：检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。例如，在付款问

19、题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款。贪心法的一般过程Greedy(C)/C是问题的输入集合即候选集合 S=;/初始解集合为空集 while(not solution(S)/集合S没有构成问题的一个解 x=select(C);/在候选集合C中做贪心选择 if feasible(S,x)/判断集合S中加入x后的解是否可行 S=S+x;C=C-x;return S;TSP问题问题 最近邻点最近邻点策略：从任意城市出发，每次在没策略：从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。了所有的城

20、市，最后回到出发城市。(d)城市城市3城市城市5(e)城市城市5城市城市2(f)城市城市2城市城市1最近邻点贪心策略求解最近邻点贪心策略求解TSP问题的过程问题的过程25221543225221543232522154327363215432233215432C=33263732372523236253(a)5城市的代价矩阵城市的代价矩阵(b)城市城市1城市城市4(c)城市城市4城市城市3背包问题背包问题给给定定n种种物物品品和和一一个个容容量量为为C的的背背包包，物物品品i的的重重量量是是wi，其其价价值值为为vi，背背包包问问题题是是如如何何选选择择装装入入背背包包的的物物品品，使使得得装

21、装入入背背包包中中物物品品的的总价值最大总价值最大?于于是是，背背包包问问题题归归结结为为寻寻找找一一个个满满足足约约束束条条件件式式7.1，并并使使目目标标函函数数式式7.2达达到到最最大大的的解解向向量量X=(x1,x2,xn)。设设xi表示物品表示物品i装入背包的情况，根据问题的要求，装入背包的情况，根据问题的要求，有如下约束条件和目标函数：有如下约束条件和目标函数：（式（式7.1）（式（式7.2）三种看似合理的贪心策略：（1）选择价值最大的物品，因为这可以尽可能快地增加背包的总价值。但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从

22、而不能保证目标函数达到最大。（2）选择重量最轻的物品，因为这可以装入尽可能多的物品，从而增加背包的总价值。但是，虽然每一步选择使背包的容量消耗得慢了，但背包的价值却没能保证迅速增长，从而不能保证目标函数达到最大。（3）选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者之间寻找平衡。60 120 50 背包 180 190 200(a)三个物品及背包 (b)贪心策略1 (c)贪心策略2 (d)贪心策略3 50 30 10 20 20 3020/30 20 1010/20 30 10例如，有3个物品，其重量分别是20,30,10，价值分别为60,120,50，背包的容量为50，应用三种贪

23、心策略装入背包的物品和获得的价值如图所示。第第8章章 回溯法回溯法l掌握回溯法的设计思想l针对某一特定实例，会写出动态搜索过程，并画出搜索空间树，从而找到最优解l0/1背包问题lTSP问题 对对于于任任何何一一个个问问题题，可可能能解解的的表表示示方方式式和和它它相相应应的的解解释释隐隐含了解空间及其大小。含了解空间及其大小。例例如如，对对于于有有n个个物物品品的的0/1背背包包问问题题，其其可可能能解解的的表表示示方方式可以有以下两种：式可以有以下两种：（1）可可能能解解由由一一个个不不等等长长向向量量组组成成，当当物物品品i(1in)装装入入背背包包时时，解解向向量量中中包包含含分分量量i

24、，否否则则，解解向向量量中中不不包包含含分分量量i，当当n=3时，其解空间是：时，其解空间是：(),(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3)（2）可能解由一个等长向量）可能解由一个等长向量x1,x2,xn组成，其中组成，其中xi=1(1in)表示物品表示物品i装入背包，装入背包，xi=0表示物品表示物品i没有装入背包，没有装入背包，当当n=3时，其解空间是：时，其解空间是：(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)为为了了用用回回溯溯法法求求解解一一个个具具有有n个个输输入入的

25、的问问题题，一一般般情情况况下下，将将其其可可能能解解表表示示为为满满足足某某个个约约束束条条件件的的 等等 长长 向向 量量 X=(x1,x2,xn)，其其 中中 分分 量量 xi(1in)的的取取值值范范围围是是某某个个有有限限集集合合Si=ai1,ai2,airi，所有可能的解向量构成了问题的所有可能的解向量构成了问题的解空间解空间。问题的解空间一般用问题的解空间一般用解空间树解空间树（SolutionSpaceTrees,也称状态空间树）的方式组织，树也称状态空间树）的方式组织，树的根结点位于第的根结点位于第1层，表示搜索的初始状态，层，表示搜索的初始状态，第第2层的结点表示对解向量的

26、第一个分量做出层的结点表示对解向量的第一个分量做出选择后到达的状态，第选择后到达的状态，第1层到第层到第2层的边上标出层的边上标出对第一个分量选择的结果，依此类推，从树的对第一个分量选择的结果，依此类推，从树的根结点到叶子结点的路径就构成了解空间的一根结点到叶子结点的路径就构成了解空间的一个可能解。个可能解。对对于于n=3的的0/1背背包包问问题题，其其解解空空间间树树如如图图8.2所所示示，树中的树中的8个叶子结点分别代表该问题的个叶子结点分别代表该问题的8个可能解。个可能解。对物品对物品1的选择的选择对物品对物品3的选择的选择对物品对物品2的选择的选择1111110000000112345

27、781112141531069 对于n=4的TSP问题，其解空间树如图8.3所示，树中的24个叶子结点分别代表该问题的24个可能解，例如结点5代表一个可能解，路径为12341，长度为各边代价之和。243422343413142412123312134131312321214241434322434123124134图图8.3n=4的的TSP问题的解空间树问题的解空间树5710121517212326283133 37 3942444749525457596264469111416202225273032 36 384143464851535658616338131924293540455055

28、6021834241123434解空间树的动态搜索解空间树的动态搜索 回回溯溯法法从从根根结结点点出出发发，按按照照深深度度优优先先策策略略遍遍历历解解空空间间树树，搜搜索索满满足足约约束束条条件件的的解解。在在搜搜索索至至树树中中任任一一结结点点时时，先先判判断断该该结结点点对对应应的的部部分分解解是是否否满满足足约约束束条条件件，或或者者是是否否超超出出目目标标函函数数的的界界，也也就就是是判判断断该该结结点点是是否否包包含含问问题题的的（最最优优）解解，如如果果肯肯定定不不包包含含，则则跳跳过过对对以以该该结结点点为为根根的的子子树树的的搜搜索索，即即所所谓谓剪剪枝枝（PruningPr

29、uning）；否否则则，进进入入以以该该结结点点为为根根的的子树，继续按照深度优先策略搜索。子树，继续按照深度优先策略搜索。例如，对于n=3的0/1背包问题，三个物品的重量为20,15,10，价值为20,30,25，背包容量为25，从图8.2所示的解空间树的根结点开始搜索，搜索过程如下：1不可行解不可行解价值价值=20价值价值=55 价值价值=30 价值价值=25价值价值=01111000000112811121415131069不可行解不可行解 再如，对于n=4的TSP问题，其代价矩阵如图8.5所示，C=3671228862376图图8.5TSP问题的代价矩阵问题的代价矩阵234422123

30、1341313123212142414322434123124134图图8.6TSP问题的搜索空间问题的搜索空间5475441127464851 535838132429354045505560218342412341回溯法的求解过程回溯法的求解过程由由于于问问题题的的解解向向量量X=(x1,x2,xn)中中的的每每个个分分量量xi(1in)都都属属于于一一个个有有限限集集合合Si=ai1,ai2,airi，因因此此，回回溯溯法法可可以以按按某某种种顺顺序序（例例如如字字典典序序）依依次次考考察察笛笛卡儿积卡儿积S1S2Sn中的元素。中的元素。初初始始时时，令令解解向向量量X为为空空，然然后后

31、，从从根根结结点点出出发发，选选择择S1的的第第一一个个元元素素作作为为解解向向量量X的的第第一一个个分分量量，即即x1=a11，如如果果X=(x1)是是问问题题的的部部分分解解，则则继继续续扩扩展展解解向向量量X，选选择择S2的的第第一一个个元元素素作作为为解解向向量量X的的第第2个个分分量量，否否则则，选选择择S1的的下下一一个个元元素素作作为为解解向向量量X的的第第一一个个分分量量，即即x1=a12。依依此此类类推推，一一般般情情况况下下，如如果果X=(x1,x2,xi)是是问问题题的的部部分分解解，则则选选择择Si+1的的第第一一个个元元素素作作为为解解向向量量X的的第第i+1个个分量

32、时，有下面三种情况：分量时，有下面三种情况：（1）如如果果X=(x1,x2,xi1)是是问问题题的的最最终终解解，则则输输出出这这个个解解。如如果果问问题题只只希希望望得得到到一一个个解解，则则结结束束搜搜索索，否否则则继继续续搜搜索索其他解；其他解；（2）如如果果X=(x1,x2,xi1)是是问问题题的的部部分分解解，则则继继续续构构造造解向量的下一个分量；解向量的下一个分量；（3）如如果果X=(x1,x2,xi1)既既不不是是问问题题的的部部分分解解也也不不是是问问题的最终解，则存在下面两种情况：题的最终解，则存在下面两种情况：如如果果xi+1=ai1k不不是是集集合合Si1的的最最后后一

33、一个个元元素素，则则令令xi+1=ai1k1，即选择即选择Si+1的下一个元素作为解向量的下一个元素作为解向量X的第的第i+1个分量；个分量；如如果果xi+1=ai1k是是集集合合Si1的的最最后后一一个个元元素素，就就回回溯溯到到X=(x1,x2,xi)，选选择择Si的的下下一一个个元元素素作作为为解解向向量量X的的第第i个个分分量量，假假设设xi=aik，如如果果aik不不是是集集合合Si的的最最后后一一个个元元素素，则则令令xi=aik1；否则，就继续回溯到否则，就继续回溯到X=(x1,x2,xi1)；回溯法的一般框架迭代形式1X=;2flag=false;3k=1;4while(k=1

34、)4.1 当(Sk没有被穷举)循环执行下列操作 4.1.1 xk=Sk中的下一个元素;4.1.2 将xk加入X;4.1.3 if(X为最终解)flag=true;转步骤5;4.1.4 else if(X为部分解)k=k+1;转步骤4;4.2 重置Sk，使得下一个元素排在第1位;4.3 k=k-1;/回溯5if flag 输出解X;else 输出“无解”;回溯算法的非递归迭代形式的一般框架如下：第第9章章 分支限界法分支限界法l掌握分支限界法的设计思想l针对某一特定实例，会写出动态搜索过程，并画出搜索空间树，从而找到最优解l0/1背包问题lTSP问题分分支支限限界界法法首首先先确确定定一一个个合

35、合理理的的限限界界函函数数，并并根根据据限限界界函函数数确确定定目目标标函函数数的的界界down,up。然然后后，按按照照广广度度优优先先策策略略遍遍历历问问题题的的解解空空间间树树，在在分分支支结结点点上上，依依次次搜搜索索该该结结点点的的所所有有孩孩子子结结点点，分分别别估估算算这这些些孩孩子子结结点点的的目目标标函函数数的的可可能能取取值值，如如果果某某孩孩子子结结点点的的目目标标函函数数可可能能取取得得的的值值超超出出目目标标函函数数的的界界，则则将将其其丢丢弃弃，因因为为从从这这个个结结点点生生成成的的解解不不会会比比目目前前已已经经得得到到的的解解更更好好；否否则则，将将其其加加入

36、入待待处处理理结结点点表表（以以下下简简称称表表PT）中中。依依次次从从表表PT中中选选取取使使目目标标函函数数的的值值取取得得极极值值的的结结点点成成为为当当前前扩扩展展结结点点，重重复复上上述述过过程程，直到找到最优解。直到找到最优解。解空间树的动态搜索（解空间树的动态搜索（2）随着这个遍历过程的不断深入，表随着这个遍历过程的不断深入，表PT中所估算的目标函中所估算的目标函数的界越来越接近问题的最优解。当搜索到一个叶子结点时数的界越来越接近问题的最优解。当搜索到一个叶子结点时，如果该结点的目标函数值是表如果该结点的目标函数值是表PT中的极值（对于最小化问题，中的极值（对于最小化问题，是极小

37、值；对于最大化问题，是极大值），则该叶子结点对是极小值；对于最大化问题，是极大值），则该叶子结点对应的解就是问题的最优解；否则，根据这个叶子结点调整目应的解就是问题的最优解；否则，根据这个叶子结点调整目标函数的界（对于最小化问题，调整上界；对于最大化问题，标函数的界（对于最小化问题，调整上界；对于最大化问题，调整下界），依次考察表调整下界），依次考察表PT中的结点，将超出目标函数界的中的结点，将超出目标函数界的结点丢弃，然后从表结点丢弃，然后从表PT中选取使目标函数取得极值的结点继中选取使目标函数取得极值的结点继续进行扩展。续进行扩展。例例：0/1背背包包问问题题。假假设设有有4个个物物品品，

38、其其重重量量分分别别为为(4,7,5,3)，价价值值分分别别为为(40,42,25,12)，背背包包容容量量W=10。首首先先，将将给给定物品按单位重量价值从大到小排序，结果如下：定物品按单位重量价值从大到小排序，结果如下：物品物品重量重量(w)价值价值(v)价值价值/重量重量(v/w)144010274263525543124 应用贪心法求得近似解为应用贪心法求得近似解为(1,0,0,0)，获得的价，获得的价值为值为40，这可以作为，这可以作为0/1背包问题的下界。背包问题的下界。如何求得如何求得0/1背包问题的一个合理的上界呢？考背包问题的一个合理的上界呢？考虑最好情况，背包中装入的全部是

39、第虑最好情况，背包中装入的全部是第1个物品且可以个物品且可以将背包装满，则可以得到一个非常简单的上界的计将背包装满，则可以得到一个非常简单的上界的计算方法：算方法：ub=W(v1/w1)=1010=100。于是，得到了于是，得到了目标函数的界目标函数的界40,100。限界函数为：限界函数为：w=0,v=0ub=100w=4,v=40ub=76w=0,v=0ub=60w=11无效解无效解w=4,v=40ub=70w=9,v=65ub=69w=4,v=40ub=64w=12无效解无效解w=9,v=65ub=65234567891分支限界法求解分支限界法求解0/1背包问题背包问题分分支支限限界界法法

40、求求解解0/1背背包包问问题题，其其搜搜索索空空间间如如图图9.1所所示，具体的搜索过程如下：示，具体的搜索过程如下：（1）在在根根结结点点1，没没有有将将任任何何物物品品装装入入背背包包，因因此此，背背包包的的重重量量和和获获得得的的价价值值均均为为0，根根据据限限界界函函数数计计算算结结点点1的的目目标函数值为标函数值为1010=100；（2）在在结结点点2，将将物物品品1装装入入背背包包，因因此此，背背包包的的重重量量为为4，获获得得的的价价值值为为40，目目标标函函数数值值为为40+(10-4)6=76，将将结结点点2加加入入待待处处理理结结点点表表PT中中；在在结结点点3，没没有有将

41、将物物品品1装装入入背背包包，因因此此，背背包包的的重重量量和和获获得得的的价价值值仍仍为为0，目目标标函函数值为数值为10660，将结点，将结点3加入表加入表PT中；中；（3）在在表表PT中中选选取取目目标标函函数数值值取取得得极极大大的的结结点点2优优先先进进行搜索；行搜索；（4）在在结结点点4，将将物物品品2装装入入背背包包，因因此此，背背包包的的重重量量为为11，不不满满足足约约束束条条件件，将将结结点点4丢丢弃弃；在在结结点点5，没没有有将将物物品品2装装入入背背包包，因因此此，背背包包的的重重量量和和获获得得的的价价值值与与结结点点2相相同，目标函数值为同，目标函数值为40+(10

42、-4)5=70，将结点，将结点5加入表加入表PT中；中；（5）在在表表PT中中选选取取目目标标函函数数值值取取得得极极大大的的结结点点5优优先先进进行行搜索；搜索；（6）在在结结点点6，将将物物品品3装装入入背背包包，因因此此，背背包包的的重重量量为为9，获获得得的的价价值值为为65，目目标标函函数数值值为为65+(10-9)4=69，将将结结点点6加加入入表表PT中中；在在结结点点7，没没有有将将物物品品3装装入入背背包包，因因此此，背背包包的的重重量量和和获获得得的的价价值值与与结结点点5相相同同，目目标标函函数数值值为为40+(10-4)464，将结点，将结点6加入表加入表PT中；中；（

43、7）在表）在表PT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点6优先进行优先进行搜索；搜索；（8）在结点）在结点8，将物品，将物品4装入背包，因此，背包的重量为装入背包，因此，背包的重量为12，不满足约束条件，将结点，不满足约束条件，将结点8丢弃；在结点丢弃；在结点9，没有将物，没有将物品品4装入背包，因此，背包的重量和获得的价值与结点装入背包，因此，背包的重量和获得的价值与结点6相相同，同，目标函数值为目标函数值为65；（9）由由于于结结点点9是是叶叶子子结结点点，同同时时结结点点9的的目目标标函函数数值值是是表表PT中中的的极极大大值值，所所以以，结结点点9对对应应的的解解

44、即即是是问问题题的的最最优优解解，搜索结束。搜索结束。分支限界法的设计思想分支限界法的设计思想假假设设求求解解最最大大化化问问题题，解解向向量量为为X=(x1,x2,xn)，其其中中，xi的的取取值值范范围围为为某某个个有有穷穷集集合合Si，|Si|=ri（1in）。在在使使用用分分支支限限界界法法搜搜索索问问题题的的解解空空间间树树时时，首首先先根根据据限限界界函函数数估估算算目目标标函函数数的的界界down,up，然然后后从从根根结结点点出出发发，扩扩展展根根结结点点的的r1个个孩孩子子结结点点，从从而而构构成成分分量量x1的的r1种种可可能能的的取取值值方方式式。对对这这r1个个孩孩子子

45、结结点点分分别别估估算算可可能能取取得得的的目目标标函函数数值值bound(x1)，其其含含义义是是以以该该孩孩子子结结点点为为根根的的子子树树所所可可能能取取得得的的目目标标函数值不大于函数值不大于bound(x1)，也就是部分解应满足：也就是部分解应满足：bound(x1)bound(x1,x2)bound(x1,x2,xk)bound(x1,x2,xn)若若某某孩孩子子结结点点的的目目标标函函数数值值超超出出目目标标函函数数的的界界，则则将将该该孩孩子子结结点点丢丢弃弃；否否则则，将将该该孩孩子子结结点点保保存存在在待待处处理理结结点点表表PT中中。从从表表PT中中选选取取使使目目标标函

46、函数数取取得得极极大大值值的的结结点点作作为为下下一一次次扩扩展展的的根根结结点点，重重复复上上述述过过程程，当当到到达达一一个个叶叶子子结结点点时时，就就得得到到了了一一个个可可行行解解X=(x1,x2,xn)及及其其目目标标函函数数值值bound(x1,x2,xn)。如如果果bound(x1,x2,xn)是是表表PT中中目目标标函函数数值值最最大大的的结结点点，则则bound(x1,x2,xn)就就是是所所求求问问题题的的最最大大值值，(x1,x2,xn)就是问题的最优解；就是问题的最优解；如如果果bound(x1,x2,xn)不不是是表表PT中中目目标标函函数数值值最最大大的的结结点点，

47、说说明明还还存存在在某某个个部部分分解解对对应应的的结结点点，其其上上界界大大于于bound(x1,x2,xn)。于于是是，用用bound(x1,x2,xn)调调整整目目标标函函数数的的下下界界，即即令令down=bound(x1,x2,xn)，并并将将表表PT中中超超出出目目标标函函数数下下界界down的的结结点点删删除除，然然后后选选取取目目标标函函数数值值取取得得极极大大值值的的结结点点作作为为下下一一次次扩扩展展的的根根结结点点，继继续续搜搜索索，直直到某个叶子结点的目标函数值在表到某个叶子结点的目标函数值在表PT中最大。中最大。分支限界法求解最大化问题的一般过程分支限界法求解最大化问

48、题的一般过程分支限界法的一般过程分支限界法的一般过程1根据限界函数确定目标函数的界根据限界函数确定目标函数的界down,up；2将待处理结点表将待处理结点表PT初始化为空；初始化为空；3对根结点的每个孩子结点对根结点的每个孩子结点x执行下列操作执行下列操作3.1估算结点估算结点x的目标函数值的目标函数值value;3.2若若(value=down)，则将结点则将结点x加入表加入表PT中；中；4循环直到某个叶子结点的目标函数值在表循环直到某个叶子结点的目标函数值在表PT中最大中最大4.1i=表表PT中值最大的结点；中值最大的结点；4.2对结点对结点i的每个孩子结点的每个孩子结点x执行下列操作执行下列操作4.2.1估算结点估算结点x的目标函数值的目标函数值value;4.2.2若若(value=down)，则将结点则将结点x加入表加入表PT中；中；4.2.3若若(结点结点x是叶子结点且结点是叶子结点且结点x的的value值在表值在表PT中最大中最大)，则将结点则将结点x对应的解输出，算法结束；对应的解输出，算法结束；4.2.4若若(结点结点x是叶子结点但结点是叶子结点但结点x的的value值在表值在表PT中不是最大中不是最大)，则令则令down=value，并且将表并且将表PT中所有小于中所有小于value的结点删除；的结点删除；