算法回溯法学习.pptx

《算法回溯法学习.pptx》由会员分享，可在线阅读，更多相关《算法回溯法学习.pptx（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学习要点：理解回溯法的深度优先搜索策略理解剪枝函数（约束函数和限界函数）的作用掌握回溯法解题的算法框架（1）递归回溯的算法框架（2）迭代回溯的算法框架（3）蒙特卡罗方法进行效率分析通过应用范例学习回溯法的设计策略。（1）n-皇后问题（2）子集和数问题（3）图的着色（4）哈密顿环（5 5）0/10/1背包背包第1页/共71页章节内容：8.1 一般方法8.2 n-皇后8.3 子集和数8.4 图的着色8.5 哈密顿环8.6 0/1背包第2页/共71页8.1 回溯法的一般方法l回溯法是比贪心法和动态规划法更一般的方法。l解为n-元组(x0,x1,.,xn-1)形式。l通过搜索状态空间树来求问题的可行解

2、（满足约束条件）或最优解（使目标函数取最大或最小值）。l使用约束函数和限界函数来压缩需要实际生成的状态空间树的结点数。l通常情况下，回溯法是为了找出满足约束条件的所有可行解。第3页/共71页问题的解空间 回溯法要求问题的解向量具有n-元组(x0,x1,xn-1)的形式，每个解分量xi从一个给定的集合Si取值。l显式约束：规定每个xi取值的约束条件。（显式约束规定了问题的候选解集解空间）对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。通常情况下,回溯法的求解目标是在状态空间树上找出满足约束条件的所有可行解.l隐式约束：给出了判定一个候选解是否为可行解的条件。为满

3、足问题的解而对不同分量之间施加的约束。l目标函数（代价函数）：衡量每个可行解的优劣，使目标函数取最大（或最小）值的可行解为问题的最优解。第4页/共71页例如（例8-1）：对n个元素(a0,a1,an-1)进行排序，求元素下标(0,1,n-1)的一种排列X=(x0,x1,xn-1)。使 (0in-1)一种方法：l显式约束：x xi i S Si i，S Si i=0,1,.,n-1=0,1,.,n-1。此时。此时解空间大小为nn。l隐式约束：(0in-1)(0in-1)，且，且x xi i x xj j(i(i j)j)另一种方法：l显式约束：x xi i S Si i，S Si i=0,1,.

4、,n-1=0,1,.,n-1且且x xi ixxj j(ij)(ij)。此时此时解空间大小为n!。l隐式约束：(0in-1)(0i=0)if(还剩下尚未检测的xk,使得xkT(x0,.,xk-1)&Bk(x0,.,xk)if(x0,x1,.,xk)是一个可行解)输出(x0,x1,.,xk);/输出可行解 k+;/深度优先进入下一层 else k-;/回溯到上一层 第12页/共71页回溯法的效率分析用蒙特卡罗（Monte Carlo）方法估计回溯法处理实例时，实际生成的结点数：在状态空间树中,从根开始随机选择一条路径(x0,x1,.,xn-1);假定搜索树中这条随机选出的路径上，代表部分向量(x

5、0,x1,.,xk-1)的结点X处不受限制的孩子数目,和其他路径上与X同层的的结点不受限制的孩子数目一样，都是mk;则可以估计整个状态空间树上实际生成的结点数为:m=1+m0+m0m1+m0m1m2+.回溯法的时间通常取决于：状态空间树上实际生成的那部分问题状态的数目（即：结点总数）。第13页/共71页程序8-3 蒙特卡罗算法int Estimate(SType*x)int k=0,m=1,r=1;do SetType S=xk|xkT(x0,.,xk-1)&Bk(x0,.,xk)=true;if(!Size(S)return m;/终止条件 r=r*Size(S);/r为本层中未受限结点总数

6、的估计值 m=m+r;/m为状态空间树中结点总数的估计值 xk=Choose(S);/从集合S中为xk随机选择一个值/由xk向下继续生成随机路径 k+;while(1);当前总结点数只有根结点1个本层结点数为1解分量下标第14页/共71页8.2 n-皇后问题在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。1 2 3 4 5 6 7 812345678QQQQQQQQ第15页/共71页 第一种显式约束观点：l显式约束：xi=0,1,2,n

7、-1l隐式约束：当ij时，1)不同列：xixj 2)不处于同一正、反对角线：|i-j|xi-xj|对应的解空间大小为：nn 第二种显式约束观点：l显式约束：1)xi=0,1,2,n-1 2)不同列：xixj(ij)l隐式约束：不处于同一正、反对角线：|i-j|xi-xj|(ij)对应的解空间大小为：n!解向量：(x0,x1,xn-1),其中xi表示第i行的皇后所处的列号。第16页/共71页（采用第二种显式约束观点的）约束函数：当ij时，要求1）不同列：xixj2）不处于同一正、反对角线：|i-j|xi-xj|4-皇后问题状态空间树见P180 图8-3（排列树）1)xi=0,1,2,n-12)不

8、同列：xixj(ij)第17页/共71页 第一种显式约束观点：l显式约束：xi=0,1,2,n-1l隐式约束：当ij时，1)不同列：xixj 2)不处于同一正、反对角线：|i-j|xi-xj|对应的解空间大小为：nn 第二种显式约束观点：l显式约束：1)xi=0,1,2,n-1 2)不同列：xixj(ij)l隐式约束：不处于同一正、反对角线：|i-j|xi-xj|(ij)对应的解空间大小为：n!解向量：(x0,x1,xn-1),其中xi表示第i行的皇后所处的列号。第18页/共71页（采用第一种显式约束观点）设计约束函数：对0i,jk,当ij时，要求 xixj 且|i-j|xi-xj|可得程序8

9、-4 求n-皇后问题的全部可行解（见下页）xi=0,1,2,n-1第19页/共71页程序8-4 n-皇后问题的回溯算法bool Place(int k,int i,int*x)/约束函数（隐式）/判断当前第k行皇后是否可放在第i列位置 for(int j=0;jk;j+)if(xj=i)|(abs(xj-i)=abs(j-k)return false;/检查与前面已选定的 0k-1 行皇后是否冲突。若有皇后（j行 xj列）/与当前皇后(k行 i列）在同一列或斜线上，则冲突，返回false。return true;void NQueens(int k,int n,int*x)/为第k行皇后选择可

10、放置的列 for(int i=0;in;i+)/显式约束（尝试所有可选列数0n-1）if(Place(k,i,x)/约束函数（隐式）xk=i;if(k=n-1)for(i=0;in;i+)coutxi“”;/输出一个可行解 coutendl;else NQueens(k+1,n,x);/深度优先进入下一层 若0n-1列均已检查完毕，则自然回溯至上层调用处。第20页/共71页程序8-4 n-皇后问题的回溯算法bool Place(int k,int i,int*x)/约束函数（隐式）/判断当前第k行皇后是否可放在第i列位置 for(int j=0;jk;j+)if(xj=i)|(abs(xj-i

11、)=abs(j-k)return false;/检查与前面已选定的 0k-1 行皇后是否冲突。若有皇后（j行 xj列）/与当前皇后(k行 i列）在同一列或斜线上，则冲突，返回false。return true;void NQueens(int k,int n,int*x)/为第k行皇后选择可放置的列 for(int i=0;in;i+)/显式约束（尝试所有可选列数0n-1）if(Place(k,i,x)/约束函数（隐式）xk=i;if(k=n-1)for(i=0;in;i+)coutxi“”;/输出一个可行解 coutendl;else NQueens(k+1,n,x);/深度优先进入下一层

12、此处返回for循环中当前层，搜索剩余列。因此可输出所有可行解。第21页/共71页图8-6 显示了图8-3中，4-皇后问题在得到第一个答案状态即终止时实际生成的那部分状态空间树。011131312313911142192030218242916313022158BBBBBBBans第22页/共71页图8-5 显示了4-皇后问题得到第一个解的步骤:QQQQQQQQQQQQQQQQQQ第23页/共71页思考题：请画出如程序8-4得到所有可行解才终止时，实际生成的状态空间树（由图8-3中来）:011131312313911142192030218242916313022158BBBBBBBans。？第

13、24页/共71页时间分析以程序程序8-48-4求解8-8-皇后问题皇后问题为例，运用蒙特卡罗方法估计实际生成的结点数：如果随机生成的5条路径分别为：(1,3,0,2,4)(1,3,0,2,4)，(3,5,2,4,6,0)(3,5,2,4,6,0)，(0,7,5,2,6,1,3)(0,7,5,2,6,1,3)，(0,2,4,1,3)(0,2,4,1,3)和(2,5,1,6,0,3,7,4)(2,5,1,6,0,3,7,4)。选择(1,3,0,2,4)路径时，生成树上实际生成的结点数目为：（见图见图8-7 8-7 a a）1+8+8*5+8*5*4+8*5*4*3+8*5*4*3*2=164916

14、49同理，其他几条路径分别实际生成的结点数目为：（见图见图8-7 b-e8-7 b-e）769769、14011401、19771977、23292329。因此这5条随机路径实际生成的结点数平均值为16251625。而8-皇后问题状态空间树的结点总数为：1+8+8*7+8*7*6+.+8*7*6*5*4*3*2*1=109601109601因此，需要实际生成的结点数目大约占总结点数的1.55%1.55%。第25页/共71页课外作业如何修改修改P180 P180 程序程序8-48-4，使之在求得第一个可行解后算法终止求得第一个可行解后算法终止？第26页/共71页l l若采用：可变长度若采用：可变

15、长度k k元组元组(x(x0 0,x,x1 1,.,x,.,xk-1k-1),),0 0knkn表示解，元组的每表示解，元组的每个分量为个分量为入选正数的下标入选正数的下标。l l显式约束为显式约束为：x xi i j|j j|j是整数且是整数且0 0jjn n 且且 x xi ixxi+1i+1(0(0iin-1)n-1)(条件条件x xi ixxi+1i+1可以避免产生重复子集）可以避免产生重复子集）隐式约束隐式约束为：为：l ln=4n=4时子集和数问题的（时子集和数问题的（可变长度可变长度元组解）元组解）状态空间树状态空间树见下页：见下页：8.3 子集和数（例（例8-28-2）设有设有

16、n=4n=4个正数的集合个正数的集合W=wW=w0 0,w,w1 1,w,w2 2,w,w3 3=(11,13,24,7)=(11,13,24,7)和和正整数正整数M=31M=31，求，求WW所有满足所有满足条件的子集，使得子集中的正数之和等于条件的子集，使得子集中的正数之和等于MM。问题描述：已知n个不同正数wi的集合，求该集合的所有满足条件的子集，使每个子集中正数的和等于一个给定的正数M。第27页/共71页图8-8 子集和数问题（可变元组解）状态空间树03123331239813431022313161415612112357每个问题状态都是一个解状态，代表一个候选解元组。第28页/共71

17、页 若采用：固定长度若采用：固定长度n n元组元组(x(x0 0,x,x1 1,.,x,.,xn-1n-1)表示解,xi0,1,0in。（xi=0，表示wi未入选子集；xi=1，表示wi入选子集。）则显式约束显式约束为：x xi i 0,1 0,1 (0in-1)隐式约束隐式约束为：n=4时子集和数问题的（固定长度元组解）状态空间树状态空间树见下页：第29页/共71页图8-9 子集和数问题（固定长度元组解）状态空间树子集树每个叶结点是一个解状态，代表一个候选解元组。非叶结点代表部分向量。101101021826273031 2601611010412132917 140151011010567

18、11809110101920212425 22023103101第30页/共71页l若条件满足，表示以(x0,x1,.,xk-1)为根的子树上可能包含答案结点。l否则，对(x0,x1,.,xk-1)剪枝。（采用固定长度元组解）在确定xk-1的取值（0或1）之前，对即将生成的结点(x0,x1,.,xk-1)，应判断是否满足约束函数Bk(x0,x1,.,xk)：(n个正数wi已按非减次序排列)若约束函数Bk(x0,x1,.,xk)=True，则生成该结点，并进入考察(x0,x1,.,xk)子树的过程。第31页/共71页程序8-5（见下页）前置条件：（若wi已按非减次序排列)后置条件：在以(x0,x

19、1,.,xk)为根的子树上搜索答案结点。第32页/共71页程序8-5 子集和数的回溯算法void SumOfSub(float s,int k,float r,int*x,float m,float*w)/s为已选择的元素和，r为剩余元素和，k为即将选择的元素下标/m为子集和数，w为权值元组，x为解元组xk=1;if(s+wk=m)/xk=1若得到一个可行解 for(int j=0;j=k;j+)coutxj;coutendl;else if(s+wk+wk+1=m)&(s+wk+1=m)/xk=0，同时约束函数Bk+1为真 xk=0;SumOfSub(s,k+1,r-wk,x,m,w);/则

20、沿右子树向下层搜索 由于进入最后一层结点时，必定满足前提条件：s+wn-1m且s+rm。而此时仅剩物品n-1可选，r=wn-1。因此必有s+wn-1=s+r=m。所以，只要进入最后一层结点，函数总能终止；否则不可能进入该层。因此，不用通过判断k是否大于n-1来终止程序。因(s+wk)+(r-wk)=s+r值未变，因此省略判断。第33页/共71页（例8-3）设有n=6个正数的集合W=5,10,12,13,15,18和整数M=30，求W的所有元素之和为M的子集。Ax0=10,0,735,1,6815,2,585,2,5815,3,4615,4,3317,3,46B5,3,465,4,330,1,6

21、810,2,580,2,5810,3,4610,4,3312,3,4612,4,3312,5,18C0,3,4613,4,330,4,33A、B、C为三个答案状态（可行解）x0=0 x1=1x1=0 x2=0 x3=0 x4=1x2=0 x2=1x3=1x3=0 x2=0 x3=0 x1=1x1=0 x2=1x2=0 x3=1x3=0 x3=0 x4=0 x5=1第34页/共71页作业（例8-2）设有n=4个正数的集合W=11,13,24,7和正整数M=31，求W的所有元素之和为M的子集。画出例8-2由SumOfSub算法实际生成的那部分状态空间树：第35页/共71页8.4 图的着色m-m-着

22、色判定问题着色判定问题(m-colorability decision problem)：已知无向图无向图G=(V,E)G=(V,E)和mm种不同的颜色种不同的颜色，如果只允许使用这m种颜色对图G的结点着色，每个结点着一种颜色，问是否存在是否存在一种着色方案，使得图中任意相邻的两个结点都有不同的颜色。任意相邻的两个结点都有不同的颜色。m-m-着色最优化问题着色最优化问题(m-colorability optimization problem)：对给定的无向图G，求对图G的结点着色 所需的最少颜色数最少颜色数mm，使得图中任意两个相邻结点有不同的颜色。mm称为图图G G的着色数的着色数(chro

23、matic number)。第36页/共71页例如：BAEDC可用三种颜色着色，结点边上的数字代表颜色编号。20120第37页/共71页四色定理每幅（无飞地的）地图都可以用不多于4种颜色来着色，使得有共同边界的国家着不同的颜色。一幅地图很容易用一个平面图G表示。（将地图的每个区域用图G的一个结点表示，若两个区域相邻，则相应的两个结点用一条边连接起来。）平面图的4-着色判定问题平面图(planar graph)：图的所有结点和边都能用某种方式画在一个平面上，且没有任何两条边相交。第38页/共71页3410220134一幅地图及其对应的平面图第39页/共71页采用n-元组(x0,x1,xn-1)表

24、示图G的m-着色判定问题的解，并采用邻接矩阵表示无向图G=(V,E)。显示约束：xi1,2,m,0in,表示结点i的颜色(xi=0表示没有可用的颜色)。隐式约束：如果边(i,j)E(即aij=1),ij，则xixj。解空间大小为mn。n为平面图中的顶点个数第40页/共71页x0=1x0=2x0=3x1=1x1=2x1=3x2=123n=3,m=3的图的m-着色判定问题的状态空间树约束函数：对所有顶点i和j（0i,jn,ij），若aij=1，则xixj。（1xi,xjm）颜色号第41页/共71页3120 x023x1x33x23112213321122231134个结点的图G图G所有可能的3-着

25、色方案如：第42页/共71页m-着色算法实现以深度优先方式深度优先方式生成状态空间树中的结点，寻找所有答案结点，即m-着色方案。搜索中使用约束函数使用约束函数剪去不可能包含答案结点的分枝。对给定的无向图无向图G G和mm，列出图中结点所有可能的m-m-着色方案着色方案。图类图类MGraphMGraph用邻接矩阵邻接矩阵表示图；函数mColoring为该类的公有公有成员函数；递归函数mColoring和NextValue为该类的私有私有成员函数。（NextValue为约束函数约束函数。）第43页/共71页程序8-6 图的m-着色算法template void MGraph:mColoring(i

26、nt m,int*x)mColoring(0,m,x);/从为x0分配颜色开始(x0,.,xn-1)的初始值均为0m-着色方案中指定的最多可用颜色数第44页/共71页程序8-6 图的m-着色算法template void MGraph:mColoring(int k,int m,int*x)/递归函数 do NextValue(k,m,x);/（约束函数）每次为xk分配一个颜色，直到 if(!xk)break;/xk已无适当颜色可选，则向上回溯 if(k=n-1)/得到图G的一种m-着色方案 for(int i=0;in;i+)coutxi;coutendl;else mColoring(k+

27、1,m,x);/深度优先搜索下一层，此时前k个结点已分配了颜色 while(1);向上回溯返回本层循环 继续为xk分配颜色，搜索其它可行着色方案第45页/共71页程序8-6 图的m-着色算法template void MGraph:NextValue(int k,int m,int*x)/约束函数，每次为xk分配一个颜色 /在1,m中为xk确定一个值最小的，且不与其邻接点冲突的颜色 /颜色从1开始编号，若xk=0表示没有可用颜色 do xk=(xk+1)%(m+1);/为xk尝试下一种颜色 if(!xk)return;/直到尝试完所有m种颜色，没有可用的颜色为止 for(int j=0;jk;

28、j+)/检验当前选择的xk是否会造成冲突 if(akj&xk=xj)/若(k,j)是图的边，且结点k和j颜色相同break;/产生冲突，尝试下一种颜色 if(j=k)return;/xk与已选定的结点颜色x0 xk-1无冲突，成功选择 while(1)；第46页/共71页算法的计算时间上界，由状态空间树的结点数 确定。每个结点的处理时间即NextValue的执行时间O(mn)。因此：总时间为第47页/共71页8.5 哈密顿环哈密顿环（Hamiltonlan cycle）：连通图G=(V,E)中的一个回路，经过图中每个顶点，且只经过一次。一个哈密顿环就是从某个结点v0开始，沿着图G的n条边环行的

29、一条路径(v0,v1,.,vn-1,vn)。除v0=vn外，路径上其余结点各不相同。(vi,vi+1)E (0in)。它访问图中每个结点且仅访问一次，最后返回开始结点。第48页/共71页并不是每个连通图都存在哈密顿环!7160534231042图G1包含哈密顿环(0,1,7,6,5,4,3,2,0)图G2不包含哈密顿环要确定一个连通图是否存在哈密顿环也没有容易的办法。第49页/共71页采用n-元组(x0,x1,xn-1)表示哈密顿环问题的解。显示约束：xi0,1,n-1,0in,代表路径上一个结点的编号。隐式约束：xixj(0i,jn，ij)，且(xi,xi+1)E(i=0,1,.,n-2)，

30、又(xn-1,x0)E。解空间大小为nn。第50页/共71页哈密顿环算法实现求一个无向图无向图或有向图有向图的所有哈密顿环所有哈密顿环，并输出所有不相同的环所有不相同的环。图类MGraph用邻接矩阵邻接矩阵表示图；指定指定x x0 0=0=0，即哈密顿环始终从顶点0开始，避免同一环被重复多次输出。因此公有公有成员函数Hamiltonian中以Hamiltonian(1 1,x)调用Hamiltonian私有私有递归函数；NextValue为约束函数约束函数。对最后一个结点对最后一个结点x xn-1n-1，还需进一步要求，还需进一步要求(x(xn-n-1 1,x,x0 0)E)E，才能形成哈密顿

31、环。，才能形成哈密顿环。第51页/共71页程序8-7 哈密顿环算法template void MGraph:Hamiltonian(int*x)Hamiltonian(1,x);/x0=0为约定的起始结点，不需选择。/因此从x1开始逐个选择x1xn-1的结点编号(x0,.,xn-1)的初始值均为0第52页/共71页程序8-7 哈密顿环算法template void MGraph:Hamiltonian(int k,int*x)/递归函数 do NextValue(k,x);/约束函数每次产生xk的下一个值，直到 if(!xk)return;/xk已无可选值时向上回溯 if(k=n-1)/哈密顿

32、环中已包含图中所有的n个顶点，则输出该环 for(int i=0;in;i+)coutxi;cout”0/n”;/哈密顿环的最后一个顶点，又回到起始点0 else Hamiltonian(k+1,x);/深度优先搜索下一层，此时前k个结点编号已确定 while(1);向上回溯返回本层循环继续为xk选择结点编号，搜索其它可行着色方案第53页/共71页程序8-7 哈密顿环算法template void MGraph:NextValue(int k,int*x)/约束函数，产生xk的下一个值 /在1,n中选择路径上的下一个结点编号xk /满足(xk-1,xk)E，且xk与前k个已经选择的结点不同。d

33、o xk=(xk+1)%n;/产生xk的下一个值（结点编号）if(!xk)return;/直到尝试完所有n个结点，没有可选的结点编号为止 if(axk-1xk)/若(xk-1,xk)是图中的一条边 for(int j=0;jk;j+)/检验当前选择的xk与前k个结点是否相同 if(xj=xk)break;/若xk与前k个结点有重复，尝试下一个结点 if(j=k)/否则表示当前结点编号xk与前k个结点均不重复 if(kn-1)|(k=n-1)&axn-1x0)/（进一步判断）return;/若xk的确可取，则取xk当前值/否则舍弃当前编号xk，尝试下一个结点 while(1)；取值失败取值成功第

34、54页/共71页算法的计算时间上界估算，请参照图的着色问题!第55页/共71页8.6 0/1背包n-皇后问题、子集和数问题、m-图着色问题、哈密顿环问题的求解目标都是求满足约束条件的全部可行解。0/1背包问题是最优化问题。回溯法本质上是一种深度优先搜索状态空间树的算法。l如果不引入剪枝函数(约束函数+限界函数)，则是穷举算法。l引入适当的限界函数，剪去已能确信不含最优答案结点的子树，使其成为一种启发式算法。0/1背包问题是一个困难问题（难以设计最坏情况下可多项式时间求解的算法）。第56页/共71页显示约束：xi=1表示将第i件物品装入背包,xi=0表示第i件物品不装入背包。隐式约束：解空间大小

35、为2n。解空间树为高度为n+1的满二叉树。l本节讨论采用本节讨论采用固定长度元组固定长度元组解结构的解结构的 0/10/1背包问题背包问题的的回溯算法回溯算法。l0/10/1背包问题的解用背包问题的解用n-n-元组元组表示：表示：X X=(x=(x0 0,x,x1 1,.,x,.,xn-1n-1)x xi i=0=0或或1 1（0in)0in)约束函数：剪去不含可行解的分枝对左孩子(xk=1)起约束函数作用，可剪去不含可行解的分枝；对右孩子(xk=0)不需用约束函数判断，一定可行。第57页/共71页目标函数：限界函数：状态空间树中任一结点X，若其上界函数值bp最优解值的下界估计值变量L，则可断

36、定X子树上不含最优答案结点，可以剪去以X为根的子树。剪去不含最优解的分枝上界函数：当前位于状态空间树的结点X处，cw为背包当前重量，cp为当前已装入背包物品的总收益，则贪心法求解剩余载重和剩余物品构成的一般背包问题（物品编号k+1,k+2,.,n-1,载重M-cw）最大收益为rp。则以X为根的子树上所有可能答案结点的目标函数值 不可能超过bp=cp+rp，因此结点X的上界函数值为bp。下界函数：变量L初值为0，遇到一个答案结点便计算该答案结点的收益值fp,且令L=maxL,fp。则L中始终保存迄今为止已经搜索到的答案结点中收益的最大值，0/1背包的最优解值必定大于等于L，因此最优解值的下界估计

37、值为L。第58页/共71页例8-4 设有0/1背包n=8,M=110，(w0,w1,.,w7)=(1,11,21,23,33,43,45,55),(p0,p1,.,p7)=(11,21,31,33,43,53,55,65)。按pi/wi非增排列，即pi/wipi+1/wi+1第59页/共71页y5=11y0=0y1=1y1=0y0=1y2=1y3=1y4=1y5=0y6=0y7=0100010100000y4=0y3=0y2=010000100被剪枝。因为w5=1时，不满足约束函数。(w0,w1,.,w7)=(1,11,21,23,33,43,45,55),(p0,p1,.,p7)=(11,2

38、1,31,33,43,53,55,65),M=110。第60页/共71页1y0=0y1=1y1=0y0=1y2=1y3=1y4=1y5=0y6=0y7=0100010100000y4=0y3=0y2=010000100164.67X(w0,w1,.,w7)=(1,11,21,23,33,43,45,55),(p0,p1,.,p7)=(11,21,31,33,43,53,55,65),M=110。bp=cp+rp=p0*1+p1*1+p2*1+p3*1+p4*1+p5*0+p6/w6*(110-89)=(11+21+31+33+43)+55/45*21 =139+25.67 =164.67为当前

39、结点X的上界函数值。若bp当前最优解值下界估计值L，则可断定X子树上不含最优答案结点，可以剪去以X为根的子树。第61页/共71页1y0=0y1=1y1=0y0=1y2=1y3=1y4=1y5=0y6=0y7=0100010100000y4=0y3=0y2=010000100164.67163.81(w0,w1,.,w7)=(1,11,21,23,33,43,45,55),(p0,p1,.,p7)=(11,21,31,33,43,53,55,65),M=110。bp=cp+rp=p0*1+p1*1+p2*1+p3*1+p4*1+p5*0+p6*0+p7/w7*(110-89)=(11+21+31

40、+33+43)+65/55*21 =139+24.81 =163.81为当前结点X的上界函数值。若bp当前最优解值下界估计值L，则可断定X子树上不含最优答案结点，可以剪去以X为根的子树。第62页/共71页1y0=0y1=1y1=0y0=1y2=1y3=1y4=1y5=0y6=0y7=0100010100000y4=0y3=0y2=010000100164.67163.81139L=139若得到最新可行解（到达状态空间树的第n+1层），则更新当前最优解下界值L。第63页/共71页164.67163.81139L=139向左走：更新 值，bp值不变。用约束函数 剪去不含可行解的分枝；向右走：更新b

41、p的值，值不变。用限界函数bpL剪去不含最优解的分枝。162.44162149161.64151L=149 L=151159.7896159L=159160.18160.22159.77158157.56159.33157.64159.77157.11154.89157.44155.12y4=11y0=0y1=1y1=0y0=1y2=1y3=1y5=0y6=0y7=0100010100000y4=0y3=0y2=010000100第64页/共71页0-1背包问题算法实现程序8-8 背包类Knapsacktemplate class Knapsackpublic:T BKnapsack(int*

42、x);protected:void BKnapsack(int k,T cp,T cw,T&fp,int*x,int*y);T Bound(int k,T cp,T cw);/Bound为上界函数bpT m,*w,*p;/已按pi/wipi+1/wi+1排序int n;；背包载重物品个数当前最大收益(下界函数L值)存入x中,保存当前最优可行解k是当前待考察的物品编号；（0kn-1）cp是当前收益；cw是当前背包重量。第65页/共71页程序8-8 上界函数Boundtemplate T Knapsack:Bound(int k,T cp,T cw)/向右走（xk=0时）调用Bound函数重新计算

43、bp值/向左走（xk=1时），收益上界值bp不变，无需重新计算；/向右走（xk=0时），收益上界值bp会变，因此需要重新计算。/若新的bp值当前最优解下界fp，则对右孩子剪枝，不生成右子树。/cp是当前收益，cw是当前背包重量，k是当前待考察的物品编号 T b=cp,c=cw;/当前收益cp和当前背包重量cw不变（xk=0）for(int i=k+1;in;i+)/对剩余物品求一般背包问题的解 c+=wi;if(cm)b+=pi;/第i个物品可以全部放入else return(b+(1-(c-m)/wi)*pi);/第i个物品只能放部分 return b;第66页/共71页程序8-8 背包类(

44、物品已按pi/wipi+1/wi+1排好序）template void Knapsack:BKnapsack(int k,T cp,T cw,T&fp,int*x,int*y)/cp是当前收益，cw是当前背包重量，k是当前待考察的物品编号 /fp是当前最大收益 /考察左孩子结点 int j;T bp;if(cw+wk=m)/左子树，需重新计算约束函数，上界函数无需计算 yk=1;if(kfp&k=n-1)/到最底层fp=cp+pk;/更新最优解下界估计值for(j=0;j=k;j+)xj=yj;。第67页/共71页程序8-8 背包类(物品已按pi/wipi+1/wi+1排好序）template

45、 void Knapsack:BKnapsack(int k,T cp,T cw,T&fp,int*x,int*y)/cp是当前收益，cw是当前背包重量，k是当前待考察的物品编号 /fp是当前最大收益。/考察右孩子结点 if(Bound(k,cp,cw)=fp)/右子树，需重新计算上界函数，约束函数无需计算 yk=0;if(kfp&k=n-1)/到最底层fp=cp;/更新最优解下界估计值for(j=0;j=k;j+)xj=yj;第68页/共71页程序8-8 背包类(物品已按pi/wipi+1/wi+1排好序）template void Knapsack:BKnapsack(int*x)int ymSize=0;T fp;BKnapsack(0,0,0,fp,x,y);return fp;第69页/共71页作业P197 P197 8-6 8-108-6 8-10 课外题：P197P197 8-28-2 8-11 8-118-128-12补充题：用回溯法实现24点问题（求所有解）第70页/共71页感谢您的观看！第71页/共71页