算法分析设计8_回溯法

第8章回溯法ch8.2学习要点：理解回溯法的深度优先搜索策略理解剪枝函数（约束函数和限界函数）的作用掌握回溯法解题的算法框架（1）递归回溯的算法框架（2）迭代回溯的算法框架（3）蒙特卡罗方法进行效率分析通过应用范例学习回溯法的设计策略。（1）n-皇后问题（2）子集和数问题（3）图的着色（4）哈密顿环（5）0/1背包ch8.3章节内容：8.1一般方法8.2n-皇后8.3子集和数8.4图的着色8.5哈密顿环8.60/1背包ch8.48.1回溯法的一般方法回溯法是比贪心法和动态规划法更一般的方法。解为n-元组(x0,x1,...,xn-1)形式。通过搜索状态空间树来求问题的可行解（满足约束条件）或最优解（使目标函数取最大或最小值）。使用约束函数和限界函数来压缩需要实际生成的状态空间树的结点数。通常情况下，回溯法是为了找出满足约束条件的所有可行解。ch8.5问题的解空间回溯法要求问题的解向量具有n-元组(x0,x1,…,xn-1)的形式，每个解分量xi从一个给定的集合Si取值。显式约束：规定每个xi取值的约束条件。（显式约束规定了问题的候选解集——解空间）对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。通常情况下,回溯法的求解目标是在状态空间树上找出满足约束条件的所有可行解.隐式约束：给出了判定一个候选解是否为可行解的条件。为满足问题的解而对不同分量之间施加的约束。目标函数（代价函数）：衡量每个可行解的优劣，使目标函数取最大（或最小）值的可行解为问题的最优解。ch8.6例如（例8-1）：对n个元素(a0,a1,……,an-1)进行排序，求元素下标(0,1,……n-1)的一种排列X=(x0,x1,……,xn-1)。使(0≤in-1)ii+1xxaa一种方法：显式约束：xiSi，Si={0,1,......,n-1}。此时解空间大小为nn。隐式约束：(0≤in-1)，且xi≠xj(i≠j)ii+1xxaa另一种方法：显式约束：xiSi，Si={0,1,......,n-1}且xi≠xj(i≠j)。此时解空间大小为n!。隐式约束：(0≤in-1)ii+1xxaa注意：同一个问题可以有多种表示。（其中某些表示方法更简单，所需表示的状态空间更小，搜索方法更简单！）ch8.7有n!个叶结点（解状态）01211220022011012738510151349611161412如：（例8-1）n个元素排序问题。若n=3则状态空间树为：排序问题一般不用回溯法求解当所给的问题是用于确定n个元素满足某种性质的排列时，相应的状态空间树为排列树，通常有n!个叶节点。ch8.8又如：0-1背包问题。若n=3则状态空间树为一个完全二叉树：有2n个解状态10110101236457011110109101381214015当所给的问题是从n个元素的集合中找出满足某种性质的子集时，相应的状态空间树为子集树，通常有2n个叶节点。ch8.9状态空间树状态空间树：描述问题解空间的树形结构。树中每个结点称为一个问题状态；若从根到树中某个状态的路径代表一个候选解元组，则该状态为解状态；若从根到某个解状态的路径代表一个可行解元组，则该解状态为答案状态；如果求解的是最优化问题，还要用目标函数衡量每个答案结点，找出其中目标函数取最优值的最优答案结点。ch8.10穷举法的一般方法使用深度优先或广度优先搜索方法，检查状态空间树中每个问题状态；如果是解状态则用判定函数判定它是否是答案结点；对于最优化问题，搜索过程中还需对每个答案结点计算其目标函数值，记录下其中最优者。——这种遍历状态空间树的求解方法是问题求解的穷举法。回溯法与穷举搜索不同：回溯法使用约束函数，剪去那些可以断定不含答案状态的子树，从而提高算法效率。回溯法适用于解一些组合数相当大的问题。事实上，状态空间树并不需要事先生成，而只需在求解的过程中，随着搜索算法的进展，逐个生成状态空间树的问题状态结点。ch8.11回溯法的一般方法采用深度优先产生状态空间树的结点，并使用剪枝函数的方法称为——回溯法。回溯法：在求解的过程中，以深度优先方式逐个生成状态空间树中结点，求问题的可行解或最优解。为提高搜索效率，在搜索过程中用约束函数和限界函数（统称剪枝函数）来剪去不必要搜索的子树，减少问题求解所需实际生成的状态空间树结点数，从而避免无效搜索。常用的剪枝函数：用约束函数剪去已知不含答案状态（可行解）的子树；用限界函数剪去得不到最优答案结点（最优解）的子树。在搜索过程中动态产生问题的解空间。算法搜索至任一结点时，先判断以该结点为根的子树是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。ch8.12递归回溯回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。程序8-1递归回溯算法框架voidRBacktrack(intk){for(每个x[k],使得x[k]T(x[0],...,x[k-1])&&(Bk(x[0],...,x[k])){//T(x0,x1,...,xk-1)表示沿路径(x0,x1,...,xk-1)从根到某个问题状态时，孩子结点xk可取值的集合。//Bk(x0,x1,...,xk)为约束函数。若子树上不含任何答案状态，则为false；否则,为true。if((x[0],x[1],...,x[k])是一个可行解)//判断是否可行解输出(x[0],x[1],...,x[k]);//输出可行解RBacktrack(k+1);//深度优先进入下一层}}由于叶结点的孩子集合T()为空集合，因此对于有限状态空间树，算法必能终止。ch8.13迭代回溯采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。程序8-2迭代回溯算法框架voidIBacktrack(intn){intk=0;while(k=0){if(还剩下尚未检测的x[k],使得x[k]T(x[0],...,x[k-1])&&Bk(x[0],...,x[k]){if((x[0],x[1],...,x[k])是一个可行解)输出(x[0],x[1],...,x[k]);//输出可行解k++;//深度优先进入下一层}elsek--;//回溯到上一层}}ch8.14回溯法的效率分析用蒙特卡罗（MonteCarlo）方法估计回溯法处理实例时，实际生成的结点数：在状态空间树中,从根开始随机选择一条路径(x0,x1,...,xn-1);假定搜索树中这条随机选出的路径上，代表部分向量(x0,x1,...,xk-1)的结点X处不受限制的孩子数目,和其他路径上与X同层的的结点不受限制的孩子数目一样，都是mk;则可以估计整个状态空间树上实际生成的结点数为:m=1+m0+m0m1+m0m1m2+......回溯法的时间通常取决于：状态空间树上实际生成的那部分问题状态的数目（即：结点总数）。ch8.15程序8-3蒙特卡罗算法intEstimate(SType*x){intk=0,m=1,r=1;do{SetTypeS={x[k]|x[k]T(x[0],...,x[k-1])&&Bk(x[0],...,x[k])==true};if(!Size(S))returnm;//终止条件r=r*Size(S);//r为本层中未受限结点总数的估计值m=m+r;//m为状态空间树中结点总数的估计值x[k]=Choose(S);//从集合S中为xk随机选择一个值//由xk向下继续生成随机路径k++;}while(1);当前总结点数只有根结点1个本层结点数为1解分量下标ch8.168.2n-皇后问题在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。1234567812345678QQQQQQQQch8.17第一种显式约束观点：显式约束：xi=0,1,2,…,n-1隐式约束：当ij时，1)不同列：xixj2)不处于同一正、反对角线：|i-j||xi-xj|对应的解空间大小为：nn第二种显式约束观点：显式约束：1)xi=0,1,2,…,n-12)不同列：xixj(ij)隐式约束：不处于同一正、反对角线：|i-j||xi-xj|(ij)对应的解空间大小为：n!解向量：(x0,x1,…,xn-1),其中xi表示第i行的皇后所处的列号。ch8.18（采用第二种显式约束观点的）约束函数：当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第一种显式约束观点：显式约束：xi=0,1,2,…,n-1隐式约束：当ij时，1)不同列：xixj2)不处于同一正、反对角线：|i-j||xi-xj|对应的解空间大小为：nn第二种显式约束观点：显式约束：1)xi=0,1,2,…,n-12)不同列：xixj(ij)隐式约束：不处于同一正、反对角线：|i-j||xi-xj|(ij)对应的解空间大小为：n!解向量：(x0,x1,…,xn-1),其中xi表示第i行的皇后所处的列号。ch8.20（采用第一种显式约束观点）设计约束函数：对0≤i,jk,当ij时，要求xixj且|i-j||xi-xj|可得程序8-4——求n-皇后问题的全部可行解（见下页）xi=0,1,2,…,n-1ch8.21程序8-4n-皇后问题的回溯算法boolPlace(intk,inti,int*x)//约束函数（隐式）{//判断当前第k行皇后是否可放在第i列位置for(intj=0;jk;j++)if((x[j]==i)||(abs(x[j]-i)==abs(j-k)))returnfalse;//检查与前面已选定的0~k-1行皇后是否冲突。若有皇后（j行x[j]列）//与当前皇后(k行i列）在同一列或斜线上，则冲突，返回false。returntrue;}voidNQueens(intk,intn,int*x)//为第k行皇后选择可放置的列{for(inti=0;in;i++)//显式约束（尝试所有可选列数0~n-1）{if(Place(k,i,x))//约束函数（隐式）{x[k]=i;if(k==n-1){for(i=0;in;i++)coutx[i]“”;//输出一个可行解coutendl;}elseNQueens(k+1,n,x);//深度优先进入下一层}}}若0~n-1列均已检查完毕，则自然回溯至上层调用处。ch8.22程序8-4n-皇后问题的回溯算法boolPlace(intk,inti,int*x)//约束函数（隐式）{//判断当前第k行皇后是否可放在第i列位置for(intj=0;jk;j++)if((x[j]==i)||(abs(x[j]-i)==abs(j-k)))returnfalse;//检查与前面已选定的0~k-1行皇后是否冲突。若有皇后（j行x[j]列）//与当前皇后(k行i列）在同一列或斜线上，则冲突，返回false。returntrue;}voidNQueens(intk,intn,int*x)//为第k行皇后选择可放置的列{for(inti=0;in;i++)//显式约束（尝试所有可选列数0~n-1）{if(Place(k,i,x))//约束函数（隐式）{x[k]=i;if(k==n-1){for(i=0;in;i++)coutx[i]“”;//输出一个可行解coutendl;}elseNQueens(k+1,n,x);//深度优先进入下一层}}}此处返回for循环中当前层，搜索剩余列。因此可输出所有可