算法8_回溯法

1、ch8.2ch8.3ch8.4l回溯法是比回溯法是比贪心法贪心法和和动态规划法动态规划法更一般更一般的方法。的方法。l解为解为n-元组元组(x0,x1,.,xn-1)形式。形式。l通过通过搜索状态空间树搜索状态空间树来求问题的来求问题的可行解可行解（满足（满足约束条件约束条件）或）或最优解最优解（使（使目标函数目标函数取最大或最小取最大或最小值）。值）。l使用使用约束函数约束函数和和限界函数限界函数来压缩需要来压缩需要实际生成实际生成的状态空间树的结点数。的状态空间树的结点数。l通常情况下通常情况下，回溯法是为了找出，回溯法是为了找出满足约束条件满足约束条件的的所有可行解所有可行解。ch8.5

2、 回溯法要求问题的解向量具有回溯法要求问题的解向量具有n-n-元组元组( (x0,x1,xn-1) )的形的形式，每个解分量式，每个解分量xi从一个给定的集合从一个给定的集合S Si i取值。取值。l显式约束显式约束：规定每个：规定每个xi取值的约束条件。取值的约束条件。（显式约束规定了问题的（显式约束规定了问题的候选解集候选解集解空间解空间）对于问题的一个实例，解向量满足对于问题的一个实例，解向量满足显式约束显式约束条件的所有多条件的所有多元组，构成了该实例的一个元组，构成了该实例的一个解空间解空间。通常情况下通常情况下,回溯法的求解目标回溯法的求解目标是在状态空间树上找出满足是在状态空间树

3、上找出满足约束条件约束条件的的所有可行解所有可行解.l隐式约束隐式约束：给出了判定一个候选解：给出了判定一个候选解是否为可行解是否为可行解的条件。的条件。为满足问题的解而对不同分量之间施加的约束。为满足问题的解而对不同分量之间施加的约束。l目标函数（代价函数）目标函数（代价函数）：衡量每个可行解的优劣，使：衡量每个可行解的优劣，使目标函数取最大（或最小）值的可行解为问题的目标函数取最大（或最小）值的可行解为问题的最优解最优解。ch8.6例如（例如（例例8-1）：对）：对n个元素个元素(a0,a1,an-1)进行排序，进行排序，求求元素下标元素下标(0,1,n-1)的一种排列的一种排列X=(x0

4、,x1,xn-1)。使。使 (0i=0) if (还剩下尚未检测的还剩下尚未检测的xk,使得使得xk T(x0,.,xk-1)&Bk(x0,.,xk) if (x0,x1,.,xk)是一个可行解是一个可行解) 输出输出(x0,x1,.,xk);/输出可行解输出可行解 k+;/深度优先进入下一层深度优先进入下一层 else k-;/回溯到上一层回溯到上一层 ch8.14用用蒙特卡罗（蒙特卡罗（Monte Carlo）方法）方法估计回溯法处理实例时，估计回溯法处理实例时，实际生成的结点数：实际生成的结点数：l在状态空间树中在状态空间树中,从根开始从根开始随机选择一条路径随机选择一条路径(x

5、0,x1,.,xn-1);l假定搜索树中这条随机选出的路径上，代表部分向量假定搜索树中这条随机选出的路径上，代表部分向量(x0,x1,.,xk-1)的结点的结点X处处不受限制的孩子数目不受限制的孩子数目,和其他路径上和其他路径上与与X同层的的结点同层的的结点不受限制的孩子数目不受限制的孩子数目一样，一样，都是都是mk;l则可以估计整个状态空间树上则可以估计整个状态空间树上实际生成的结点数实际生成的结点数为为: m=1+m0+m0m1+m0m1m2+.回溯法的时间通常取决于：状态空间树上回溯法的时间通常取决于：状态空间树上实际生成的实际生成的那部分那部分问题状态的数目问题状态的数目（即：（即：结

6、点总数结点总数）。）。ch8.15程序程序8-3 蒙特卡罗算法蒙特卡罗算法int Estimate(SType *x)int k=0,m=1,r=1; do SetType S= xk | xk T(x0,.,xk-1)& Bk(x0,.,xk)=true; if (!Size(S) return m;/终止条件终止条件 r=r*Size(S);/r为为本层中本层中未受限结点总数的未受限结点总数的估计值估计值 m=m+r;/m为状态空间树中结点总数的估计值为状态空间树中结点总数的估计值 xk=Choose(S); /从集合从集合S S中为中为xk随机选择一个值随机选择一个值/由由xk向

7、下继续生成随机路径向下继续生成随机路径 k+;while (1);当前总结点数当前总结点数只有根结点只有根结点1个个本层结点数为本层结点数为1解分量解分量下标下标ch8.16在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。1 2 3 4 5 6 7 812345678QQQQQQQQch8.17 第一种显式约束观点：第一种显式约束观点：l显式约束：显式约束：xi=0,1,2, ,n-1l隐式约束：当隐式约束：当i j时，时， 1)不同列

8、：不同列：xi xj 2)不处于同一正、反对角线：不处于同一正、反对角线：|i-j| |xi-xj|对应的解空间大小为：对应的解空间大小为：nn 第二种显式约束观点：第二种显式约束观点：l显式约束：显式约束： 1)xi=0,1,2, ,n-1 2)不同列：不同列：xi xj (i j)l隐式约束：不处于同一正、反对角线：隐式约束：不处于同一正、反对角线：|i-j| |xi-xj| (i j)对应的解空间大小为：对应的解空间大小为：n!解向量：解向量：(x0, x1, , xn-1),其中其中xi表示第表示第i行的皇后所处的行的皇后所处的列号列号。ch8.18（采用第二种显式约束观点的）（采用第

9、二种显式约束观点的）约束函数：约束函数： 当当i j时，要求时，要求1）不同列：）不同列：xi xj2）不处于同一正、反对角线：）不处于同一正、反对角线：|i-j| |xi-xj|4-皇后问题皇后问题状态空间树状态空间树见见P180 图图8-3（排列树）（排列树）1)xi=0,1,2, ,n-12)不同列：不同列：xi xj (i j)ch8.19 第一种显式约束观点：第一种显式约束观点：l显式约束：显式约束：xi=0,1,2, ,n-1l隐式约束：当隐式约束：当i j时，时， 1)不同列：不同列：xi xj 2)不处于同一正、反对角线：不处于同一正、反对角线：|i-j| |xi-xj|对应的

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

11、 |i-j| |xi-xj| 可得可得程序程序8-4 求求n-皇后问题的全部可行解皇后问题的全部可行解（见下页）（见下页）xi=0,1,2, ,n-1ch8.21程序程序8-4 n-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 行皇后是否冲突。行皇

12、后是否冲突。若若有皇后（有皇后（j j行行 xjxj 列列） /与当前皇后与当前皇后( (k k行行 i i列列）在同一列或斜线上，则冲突，返回）在同一列或斜线上，则冲突，返回falsefalse。 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“

13、 ”; /输出一个可行解输出一个可行解 coutendl; else NQueens(k+1,n,x);/深度优先进入下一层深度优先进入下一层 若若0n-1列均已检查完毕，则自然回溯至上层调用处。列均已检查完毕，则自然回溯至上层调用处。ch8.22程序程序8-4 n-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

14、 false; /检查与前面已选定的检查与前面已选定的 0k-1 行皇后是否冲突。行皇后是否冲突。若若有皇后（有皇后（j j行行 xjxj 列列） /与当前皇后与当前皇后( (k k行行 i i列列）在同一列或斜线上，则冲突，返回）在同一列或斜线上，则冲突，返回falsefalse。 return true; void NQueens(int k,int n,int *x) /为为第第k行行皇后选择可放置的列皇后选择可放置的列 for (int i=0;in;i+) /显式约束（尝试显式约束（尝试所有可选列数所有可选列数0n-1） if (Place(k,i,x)/约束函数（隐式）约束函数（隐

15、式） xk=i; if (k=n-1) for (i=0;in;i+) coutxi“ ”; /输出一个可行解输出一个可行解 coutendl; else NQueens(k+1,n,x);/深度优先进入下一层深度优先进入下一层 此处返回此处返回for循环中当前层，搜索剩循环中当前层，搜索剩余列。因此可输出余列。因此可输出所有可行解所有可行解。ch8.23图图8-6 显示了显示了图图8-3中，中，4-皇后问题在皇后问题在得到第一个答案状得到第一个答案状态态即终止时即终止时实际生成的实际生成的那部分状态空间树那部分状态空间树。01113131231391114219203021824291631

16、3022158BBBBBBBansch8.24图图8-5 显示了显示了4-皇后问题得到第一个解的步骤皇后问题得到第一个解的步骤:QQQQQQQQQQQQQQQQQQch8.25思考题思考题：请画出如：请画出如程序程序8-4得到所有可行解得到所有可行解才终止时，实才终止时，实际生成的状态空间树际生成的状态空间树（由（由图图8-3中来）中来）:011131312313911142192030218242916313022158BBBBBBBans。？。？ch8.26ch8.27ch8.2810ikxiwM问题描述：问题描述：已知已知n个不同正数个不同正数wi的集合，求该集合的的集合，求该集合的所有

17、满足条件的子集，使每个子集中正数的和等于一所有满足条件的子集，使每个子集中正数的和等于一个给定的正数个给定的正数M。ch8.29图图8-8 子集和数问题（子集和数问题（可变元组可变元组解）状态空间树解）状态空间树03123331239813431022313161415612112357每个问题状态每个问题状态都是一个都是一个解状解状态态，代表一个，代表一个候选解候选解元组元组。ch8.3010niiiw xMch8.31图图8-9 子集和数问题（子集和数问题（固定长度固定长度元组解）状态空间树元组解）状态空间树子集树子集树每个每个叶结点叶结点是一个解状态，代表一个是一个解状态，代表一个候选解

18、元组候选解元组。非叶结点代表非叶结点代表部分向量部分向量。101101021826273031 2601611010412132917 14015101101056711809110101920212425 22023103101ch8.32l若条件满足，若条件满足，表示表示以以(x0,x1,.,xk-1)为根的子树上可能包为根的子树上可能包含答案结点含答案结点。l否则，否则，对对(x0,x1,.,xk-1)剪枝剪枝。（采用（采用固定长度元组固定长度元组解）在解）在确定确定xk-1的取值的取值（0或或1）之前之前，对对即将生成的结点即将生成的结点(x0,x1,.,xk-1) ，应判断是否，应判

19、断是否满足满足约束函数约束函数Bk(x0,x1,.,xk)：11100knkiiiiikii kiw xwMw xwM且(n个正数个正数wi已按非减次序排列已按非减次序排列)若约束函数若约束函数Bk(x0,x1,.,xk)=True，则则生成该结点生成该结点，并进入并进入考察考察(x0,x1,.,xk)子树子树的过程。的过程。ch8.33程序程序8-5（见下页见下页）前置条件前置条件： （若若wi已按非减次序排列已按非减次序排列)后置条件后置条件：在以在以(x0,x1,.,xk)为根的子树上搜索答案结点。为根的子树上搜索答案结点。110&M(,M)kniiiiikksrswsw xwr

20、其中ch8.34程序程序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

21、) /xk=0，同时约束函数，同时约束函数Bk+1为真为真 xk=0; SumOfSub(s,k+1,r-wk,x,m,w);/则沿右子树向下层搜索则沿右子树向下层搜索 由于进入最后一层结点时，必定满足前提条件：由于进入最后一层结点时，必定满足前提条件：s+wn-1m且且s+rm。 而此时仅剩物品而此时仅剩物品n-1可选，可选，r=wn-1。因此必有。因此必有s+wn-1= s+r=m。所以，。所以，只要进入最后一层结点，函数总能终止只要进入最后一层结点，函数总能终止；否则不否则不可能进入该层可能进入该层。因此，不用通过判断。因此，不用通过判断k是否大于是否大于n-1来终止程序。来终止程序。因

22、因(s+wk)+(r-wk)=s+r值未变，因此省略判断。值未变，因此省略判断。ch8.35（例例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,6810,2,580,2,5810,3,4610,4,3312,3,4612,4,3312,5,18C0,3,4613,4,330,4,33A、B、C为三个答案状态（可行解）为三个答案状态（可行解）x0

23、=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=1ch8.36（例（例8-2）设有设有n=4个正数的集合个正数的集合W=11,13,24,7和正整数和正整数M=31，求，求W的所有元素之和为的所有元素之和为M的子集。的子集。画出画出例例8-2由由SumOfSub算法算法实际生成的那部分状实际生成的那部分状态空间树：态空间树：ch8.37ch8.38例如：例如：BAEDC可用三种颜色着色，结点边上的数字代表颜色编号。可用三种颜色着色，结点边上的数字代表颜色编

24、号。20120ch8.39四色定理四色定理每幅（无每幅（无飞地飞地的）的）地图地图都可以用都可以用不多于不多于4种颜色种颜色来来着色，使得有共同边界的国家着不同的颜色。着色，使得有共同边界的国家着不同的颜色。一幅一幅地图地图很容易用一个很容易用一个平面图平面图G表示。（将地图的表示。（将地图的每个每个区域区域用图用图G的一个的一个结点结点表示，若两个区域表示，若两个区域相邻相邻，则相应的两个结点用一条则相应的两个结点用一条边边连接起来。）连接起来。）平面图的平面图的4-着色判定问题着色判定问题平面图平面图(planar graph)：图的所有结点和边都能用图的所有结点和边都能用某种方式画在一个

25、平面上，且没有任何两条边相交。某种方式画在一个平面上，且没有任何两条边相交。ch8.403410220134一幅地图及其对应的平面图一幅地图及其对应的平面图ch8.411( , ) 880i jEa ij如果（）其他采用采用n-元组元组(x0,x1,xn-1)表示表示图图G的的m-着色判定问着色判定问题题的解，并采用的解，并采用邻接矩阵邻接矩阵表示无向图表示无向图G=(V,E) 。显示约束显示约束：xi1,2,m, 0in, 表示结点表示结点i的颜色的颜色 (xi=0表示没有可用的颜色表示没有可用的颜色) 。隐式约束隐式约束：如果：如果边边(i,j)E(即即aij=1), ij，则，则xixj

26、。解空间解空间大小为大小为mn 。n为平面图中的顶点个数为平面图中的顶点个数ch8.42x0=1x0=2x0=3x1=1x1=2x1=3x2=123n=3,m=3的图的的图的m-着色判定问题的状态空间树着色判定问题的状态空间树约束函数：约束函数：对所有顶点对所有顶点i和和j（0i, jn, ij），若），若aij=1，则，则xixj。（1xi,xjm）颜色号颜色号ch8.433120 x023x1x33x23112213321122231134个结点的图个结点的图G图图G所有可能的所有可能的3-着色方案着色方案如：如：ch8.44ch8.45程序程序8-6 图的图的m-着色算法着色算法temp

27、late void MGraph : mColoring(int m,int *x) mColoring(0,m,x);/从为从为x0分配颜色开始分配颜色开始(x0,.,xn-1)的初始值均为的初始值均为0m-着色方案中指定的最多可用颜色数着色方案中指定的最多可用颜色数ch8.46程序程序8-6 图的图的m-着色算法着色算法template void MGraph : mColoring(int k,int m,int *x)/递归函数递归函数 do NextValue(k,m,x); /（约束函数）（约束函数）每次为每次为xk分配一个颜色，直到分配一个颜色，直到 if (!xk) break

28、; /xk已无适当颜色可选已无适当颜色可选，则，则向上回溯向上回溯 if (k=n-1)/得到图得到图G的一种的一种m-着色方案着色方案 for (int i=0;in;i+) coutxi; coutendl; else mColoring(k+1,m,x);/深度优先搜索下一层深度优先搜索下一层，此时前，此时前k个结点已分配了颜色个结点已分配了颜色 while(1);向上回溯向上回溯返回本返回本层循环层循环 继续为继续为xk分分配颜色，配颜色，搜索其搜索其它可行它可行着色方着色方案案ch8.47程序程序8-6 图的图的m-着色算法着色算法template void MGraph : Nex

29、tValue(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;j+) /检验当前选择的检验当前选择的xk是否会造成冲突是否

30、会造成冲突 if (akj&xk=xj) /若若(k,j)是图的边，且结点是图的边，且结点k和和j颜色相同颜色相同break; /产生冲突产生冲突，尝试下一种颜色尝试下一种颜色 if (j=k) return; /xk与已选定的结点颜色与已选定的结点颜色x0 xk-1无冲突无冲突，成功选择成功选择 while (1)；ch8.48算法的计算时间上界，由状态空间树的结点数算法的计算时间上界，由状态空间树的结点数 确定。确定。每个结点的处理时间即每个结点的处理时间即NextValue的执行时间的执行时间O(mn)。因此：因此：总时间为总时间为11()()1nninimmm nnO nmm1

31、0niimch8.49l哈密顿环哈密顿环（Hamiltonlan cycle）：）：连通图连通图G=(V,E)中的一个回路，经过图中每个顶点，中的一个回路，经过图中每个顶点，且只经过一次。且只经过一次。一个哈密顿环就是从某个结点一个哈密顿环就是从某个结点v0开始，沿着图开始，沿着图G的的n条边条边环行的一条路径环行的一条路径(v0,v1,.,vn-1,vn)。除除v0=vn外，路径上其余结点各不相同。外，路径上其余结点各不相同。(vi,vi+1) E (0in)。它访问图中每个结点且仅访问一次，最后返回开始它访问图中每个结点且仅访问一次，最后返回开始结点。结点。ch8.50并不是每个连通图都存

32、在哈密顿环并不是每个连通图都存在哈密顿环!7160534231042图图G1包含哈密顿环包含哈密顿环(0,1,7,6,5,4,3,2,0)图图G2不包含哈密顿环不包含哈密顿环要确定一个连通图是否存在哈密顿环也没有容易要确定一个连通图是否存在哈密顿环也没有容易的办法。的办法。ch8.51采用采用n-元组元组(x0,x1,xn-1)表示表示哈密顿环问题的解哈密顿环问题的解。显示约束显示约束：xi0,1,n-1, 0in, 代表路径上一个代表路径上一个结点的编号结点的编号 。隐式约束隐式约束：xixj(0i, jn，ij)，且，且(xi,xi+1)E (i=0,1,.,n-2)，又，又(xn-1,x

33、0)E。解空间解空间大小为大小为nn 。ch8.52ch8.53程序程序8-7 哈密顿环算法哈密顿环算法template void MGraph : Hamiltonian(int *x) Hamiltonian(1,x);/x0=0为约定的起始结点，不需选择。为约定的起始结点，不需选择。/因此从因此从x1开始逐个选择开始逐个选择x1xn-1的结点编号的结点编号(x0,.,xn-1)的初始值均为的初始值均为0ch8.54程序程序8-7 哈密顿环算法哈密顿环算法template void MGraph : Hamiltonian(int k, int *x)/递归函数递归函数 do NextVa

34、lue(k,x); /约束函数约束函数每次产生每次产生xk的下一个值，直到的下一个值，直到 if (!xk) return; /xk已无可选值时已无可选值时向上回溯向上回溯 if (k=n-1)/哈密顿环中已包含图中所有的哈密顿环中已包含图中所有的n个顶点，则输出该环个顶点，则输出该环 for (int i=0;in;i+) coutxi; cout” 0/n”; /哈密顿环的最后一个顶点，又回到起始点哈密顿环的最后一个顶点，又回到起始点0 else Hamiltonian(k+1,x);/深度优先搜索下一层深度优先搜索下一层，此时前，此时前k个结点编号已确定个结点编号已确定 while(1)

35、;向上回溯向上回溯返回本返回本层循环层循环继续为继续为xk选选择结点择结点编号，编号，搜索其搜索其它可行它可行着色方着色方案案ch8.55程序程序8-7 哈密顿环算法哈密顿环算法template void MGraph : NextValue(int k,int *x) /约束函数，产生约束函数，产生xk的下一个值的下一个值 /在在1,n中选择路径上的下一个结点编号中选择路径上的下一个结点编号xk /满足满足(xk-1,xk)E，且，且xk与前与前k个已经选择的结点不同。个已经选择的结点不同。 do xk=(xk+1)%n; /产生产生xk的下一个值的下一个值（结点编号）（结点编号） if(!

36、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) )

37、 /（进一步判断）（进一步判断） return; /若若xk的确的确可取可取，则，则取取xk当前值当前值/否则舍弃否则舍弃当前编号当前编号xk，尝试下一个结点尝试下一个结点 while (1)；取值失败取值失败取值成功取值成功ch8.56算法的计算时间上界估算，请参照图的着色问题算法的计算时间上界估算，请参照图的着色问题!ch8.57ln-皇后问题皇后问题、子集和数问题子集和数问题、m-图着色问题图着色问题、哈哈密顿环问题密顿环问题的求解目标都是求满足约束条件的全部的求解目标都是求满足约束条件的全部可行解可行解。l0/1背包问题背包问题是是最优化问题最优化问题。回溯法回溯法本质上是一种本质上是

38、一种深度优先搜索深度优先搜索状态空间树的算法。状态空间树的算法。l如果不引入剪枝函数如果不引入剪枝函数(约束函数约束函数+限界函数限界函数)，则是，则是穷穷举举算法。算法。l引入适当的引入适当的限界函数限界函数，剪去已能确信不含，剪去已能确信不含最优最优答案答案结点的子树，使其成为一种启发式算法。结点的子树，使其成为一种启发式算法。0/10/1背包问题是一个背包问题是一个困难问题困难问题（难以设计（难以设计最坏情况下最坏情况下可可多项式时间求解多项式时间求解的算法）。的算法）。ch8.58显示约束显示约束：xi=1表示将第表示将第i件物品装入背包件物品装入背包, xi=0表示表示第第i件物品不

39、装入背包。件物品不装入背包。隐式约束隐式约束：解空间解空间大小为大小为2n 。解空间树为高度为。解空间树为高度为n+1的满二叉树。的满二叉树。约束函数约束函数：剪去不含可行解的分枝剪去不含可行解的分枝01k(,.,),kiB x xxtruexMk-1iki=0当且仅w当w100,01niiiiiw xMwx或对对左孩子左孩子(xk=1)起约束函数作用起约束函数作用，可剪，可剪去不含可行解的分枝；去不含可行解的分枝；对对右孩子右孩子(xk=0)不需用约束函数判断不需用约束函数判断，一定可行。一定可行。ch8.59目标函数目标函数：100,01niiiiip xpx或限界函数：限界函数：状态空间

40、树中任一结点状态空间树中任一结点X，若其，若其上界函数上界函数值值bp最优解值的下界估计值变量最优解值的下界估计值变量L，则可断定，则可断定X子树子树上不含最优答案结点，可以剪去以上不含最优答案结点，可以剪去以X为根的子树。为根的子树。剪去不含最优解的分枝剪去不含最优解的分枝上界函数：上界函数：当前位于状态空间树的结点当前位于状态空间树的结点X处，处，cw为背包当前重为背包当前重量，量，cp为为当前已装入背包物品的总收益当前已装入背包物品的总收益，则，则贪心法求解剩余载贪心法求解剩余载重和剩余物品构成的一般背包问题重和剩余物品构成的一般背包问题（物品编号物品编号k+1,k+2,.,n-1,载重

41、载重M-cw）最大收益为最大收益为rp。则以。则以X为根的子树上所有可能答案为根的子树上所有可能答案结点的目标函数值结点的目标函数值 不可能超过不可能超过bp=cp+rp，因此，因此结点结点X的上界函数值为的上界函数值为bp。1iiki ncpp x 下界函数：下界函数：变量变量L初值为初值为0，遇到一个答案结点便计算该，遇到一个答案结点便计算该答案结答案结点的收益值点的收益值fp,且令且令L=maxL,fp。则。则L中始终保存中始终保存迄今为止已迄今为止已经搜索到的答案结点中收益的最大值经搜索到的答案结点中收益的最大值，0/1背包的背包的最优解值必最优解值必定大于等于定大于等于L，因此最优解

42、值的，因此最优解值的下界估计值为下界估计值为L。ch8.60例例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+1ch8.61y5=11y0=0y1=1y1=0y0=1y2=1y3=1y4=1y5=0y6=0y7=0100010100000y4=0y3=0y2=010000100被剪枝被剪枝。因为。因为w5=1时，时，不满足约束函数不满足约束函数。450iiw xwM(w0,

43、w1,.,w7)=(1,11,21,23,33,43,45,55), (p0,p1,.,p7)=(11,21,31,33,43,53,55,65), M=110。ch8.621y0=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*(1

44、10-89)=(11+21+31+33+43)+55/45*21 =139+25.67 =164.67为为当前结点当前结点X的上界函数值的上界函数值。若。若bp当前最优解值下界估计值当前最优解值下界估计值L，则可断定则可断定X子树上不含最优答案结点，子树上不含最优答案结点，可以剪去以可以剪去以X为根的子树为根的子树。ch8.631y0=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

45、)=(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+33+43)+65/55*21 =139+24.81 =163.81为为当前结点当前结点X的上界函数值的上界函数值。若若bp当前最优解值下界估计值当前最优解值下界估计值L，则可断定则可断定X子树上不含最优答案结点，子树上不含最优答案结点，可以剪去以可以剪去以X为根的子树为根的子树。ch8.641y0=0y1=1y1=0y0=1y2=1y3=1y4=1y5=0y6=0y7=01000101

46、00000y4=0y3=0y2=010000100164.67163.81139L=139若得到若得到最新可行解最新可行解（到达（到达状态空间树的第状态空间树的第n+1层层），则），则更新更新当前最优解当前最优解下下界值界值L。ch8.65164.67163.81139L=1390kiiiw x向左向左走：走：更新更新 值，值，bp值不变。用值不变。用约束函数约束函数 剪剪去去不含可行解不含可行解的分枝；的分枝；向右向右走：走：更新更新bp的值，的值， 值不变。用值不变。用限界函数限界函数bpL剪去剪去不含最优解不含最优解的分枝。的分枝。10kiikiw xw10kiikiw xwM162.4

47、4162149161.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=010000100ch8.66程序程序8-8 背包类背包类Knapsacktemplate class Knapsackpublic:T BKnapsack(int *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;；