算法设计-课件

第5章 回溯法1学习要点学习要点v理解回溯法的深度优先搜索策略。v掌握用回溯法解题的算法框架（1）递归回溯（2）迭代回溯（3）子集树算法框架（4）排列树算法框架2通过应用范例学习回溯法的设计策略。（1）装载问题；（2）批处理作业调度；（3）符号三角形问题（4）n后问题；（5）0-1背包问题；（6）最大团问题；（7）图的m着色问题（8）旅行售货员问题（9）圆排列问题（10）电路板排列问题（11）连续邮资问题3回溯法的基本概念回溯法的基本概念n在现实生活中，有些问题是不能用数学公式去解决的，它需在现实生活中，有些问题是不能用数学公式去解决的，它需要通过一个过程，此过程要经过若干个步骤才能完成，每一要通过一个过程，此过程要经过若干个步骤才能完成，每一个步骤又分为若干种可能。个步骤又分为若干种可能。同时，为了完成任务，还必须遵同时，为了完成任务，还必须遵守一些规则，这些规则也无法用数学公式表示，对于这类问守一些规则，这些规则也无法用数学公式表示，对于这类问题，一般采用题，一般采用搜索搜索的方法来解决。的方法来解决。n所谓所谓“搜索搜索”是指利用计算机的高性能有目的地穷举一个问是指利用计算机的高性能有目的地穷举一个问题的部分或所有的解题的部分或所有的解(也称为候选解也称为候选解)，然后依次检查每一个，然后依次检查每一个候选解，在检查完所有或部分候选解后，即可找到满足某种候选解，在检查完所有或部分候选解后，即可找到满足某种条件的所需要的解。条件的所需要的解。n搜索过程是搜索过程是根据初始条件和扩展规则根据初始条件和扩展规则构造一棵树并寻找符合构造一棵树并寻找符合目标状态的结点的过程。目标状态的结点的过程。4方法概述:搜索算法介绍n搜索的重要性和提高效率的途径 搜索是人工智能的基本手段.推理可以看成一种搜索，联想、回忆、灵感也是一种搜索过程;搜索效率:Time Complexity,Space Time Complexity,Space Complexity,Solution QualityComplexity,Solution Quality;Completeness Completeness 提高搜索的基本途径:一是积累并恰当使用有助于减少搜索的信息和知识(启发式方法);二是采用并行处理技术;5方法概述:搜索算法介绍n搜索算法(1)穷举搜索(ExhaustiveExhaustive SearchSearch)(2)盲目搜索(Blind or Blind or Brute-Force Brute-Force SearchSearch)-深度优先(DFSDFS)或回溯搜索(BacktrackingBacktracking);-广度优先搜索(BFSBFS);-迭代加深搜索(Iterative DeepeningIterative Deepening);-分枝限界法(Branch&BoundBranch&Bound);-博弈树搜索(-Search Search)(3)启发式搜索(Heuristic SearchHeuristic Search)-A*算法和最佳优先(Best-Fist SearchBest-Fist Search)-迭代加深的A*算法 -B*,AO*,SSS*等算法 -Local Search,GA等算法6v回溯法是一个既带有系统性又带有跳跃性的搜索算法。v它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。v算法搜索至解空间树的任一结点时，判断该结点为根的子树是否包含问题的解，如果肯定不包含，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。v回溯法求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。回溯法7v回溯法求解问题的一个解时，只要搜索到问题的一个解就结束。v这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。8 在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。回溯法是一种通用性解法，可以将回溯法看作是带优化的穷举法。9回溯法解迷宫问题回溯法解迷宫问题v例如，老鼠走迷宫问题。当老鼠进入迷宫后，它先随意选择例如，老鼠走迷宫问题。当老鼠进入迷宫后，它先随意选择一个方向前进，一步一步地向前试探前进，如果碰到墙，说一个方向前进，一步一步地向前试探前进，如果碰到墙，说明此方向不通，这时，它首先看其它方向是否还有路可走，明此方向不通，这时，它首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探。如果有路可走，则沿该方向再向前试探。v如果已无路可走，则返回一步，再看其它方向是否还有路可如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。走；如果有路可走，则沿该方向再向前试探。v按此原则反复按此原则反复搜索、回溯、再搜索搜索、回溯、再搜索，直到找到新的出路或从，直到找到新的出路或从原路返回入口处无解为止。原路返回入口处无解为止。v假如，现有如图所示的一个假如，现有如图所示的一个3333的迷宫，其中，的迷宫，其中，1 1表示此路表示此路径不同，径不同，0 0表示此路径通。要求老鼠从表示此路径通。要求老鼠从A0,0A0,0进入从进入从A2,2A2,2走出迷宫，即要寻找一条从走出迷宫，即要寻找一条从A0,0A0,0到到A2,2A2,2的路径。的路径。10回溯法解迷宫问题回溯法解迷宫问题v为了方便问题的解决，首先将表示迷宫的为了方便问题的解决，首先将表示迷宫的3333矩阵转换为如矩阵转换为如图所示的一棵搜索树。图所示的一棵搜索树。v其中，搜索树中的一个结点代表迷宫解空间中的一个元素，其中，搜索树中的一个结点代表迷宫解空间中的一个元素，如果如果两个结点之间存在通路就用实线连接的，否则用虚线连两个结点之间存在通路就用实线连接的，否则用虚线连接接。11回溯法解迷宫问题回溯法解迷宫问题v按照回溯法的约定，搜索首先从按照回溯法的约定，搜索首先从A A0,00,0开始，由图可知，从该结点开始，由图可知，从该结点能行走到的结点有能行走到的结点有A A1,01,0和和A A0,10,1两个。两个。v假如选择结点假如选择结点A A0,10,1，由于从，由于从A A0,10,1结点能行走的路径只有结点能行走的路径只有A A0,20,2，所以，所以，此时只能选择结点此时只能选择结点A A0,20,2，由于从该结点出发不存在任何可行走的，由于从该结点出发不存在任何可行走的路径，此时，老鼠只能从路径，此时，老鼠只能从A A0,20,2回溯到回溯到A A0,10,1结点。由于从结点结点。由于从结点A A0,10,1出出发只有到结点发只有到结点A A0,20,2这一条路径，因此，老鼠须继续回溯，也即从这一条路径，因此，老鼠须继续回溯，也即从A A0,10,1结点回溯到结点回溯到A A0,00,0结点。由于从结点。由于从A A0,00,0出发还存在一条到出发还存在一条到A A1,01,0结点结点的路径，因此，老鼠将从的路径，因此，老鼠将从A A1,01,0结点开始，重复上述搜索工作，直结点开始，重复上述搜索工作，直到搜索出如下一条路径为止。到搜索出如下一条路径为止。vA A0,00,0AA1,01,0AA2,02,0AA2,12,1AA2,22,2v需要指出的是利用回溯法找到的路径不一定是最短路径。需要指出的是利用回溯法找到的路径不一定是最短路径。125.1 回溯法的算法框架n本节介绍回溯法算法框架的有关问题：一、问题的解空间二、回溯法的基本思想三、递归回溯四、迭代回溯五、子集树与排列树13一、问题的解空间v应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个(最优)解。问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,xn)的形式。显约束：对分量xi的取值限定。隐约束：为满足问题的解而对不同分量之间施加的约束。解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。v例如，对于有n种可选物品的0-1背包问题，其解空间由长度为n的0-1向量组成。该解空间包含对变量的所有可能0-1赋值。n=3时的0-1背包问题用完全二叉树表示的解空间14确定了解空间的组织结构后，回溯法从从开始结点（根结点）出发，以DFS搜索整个解空间。开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处向纵深方向移至一个新结点，这个新结点就成为一个新的活结点，也成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向扩展，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。生成问题状态的基本方法15start?dead enddead end?dead enddead end?success!dead end16n回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法17二、回溯法的基本思想(1)针对所给问题，定义问题的解空间（对解进行编码）；(2)确定易于搜索的解空间结构（按树或图组织解）；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n)。而显式地存储整个解空间则需要O(2h(n)或O(h(n)!)内存空间。v关于复杂性：v回溯法的基本步骤：v常用剪枝函数：18n=3,w=(16,15,15),v=(45,25,25),c=30 (1)定义解空间：X=(0,0,0),(0,0,1),(0,1,0),(1,1,0),(1,1,1)(2)构造解空间树：(1,1,1)AHIDJKEBLMFNOGC10101010101010(1,1,0)(1,0,1)(1,0,0)(0,1,1)(0,1,0)(0,0,1)(0,0,0)示例1 0-1背包问题19n=3,w=(16,15,15),v=(45,25,25),c=30(3)从A出发按DFS搜索：AHIDJKEBLMFNOGC10101010101010455025250可行解:(1,0,0)(0,1,1)(0,1,0)(0,0,1)(0,0,0)死结点解值:最优解L=(0,1,1),最优值为 50示例1 0-1背包问题20示例1 0-1背包问题n=3,C=30,w=16,15,15,v=45,25,25n开始时，Cr=C=30，V=0，A为唯一活结点，也是当前扩展结点n扩展A，先到达B结点Cr=Cr-w1=14，V=V+v1=45此时A、B为活结点，B成为当前扩展结点扩展B，先到达DnCrw2，D导致一个不可行解，回溯到B再扩展B到达EnE可行，此时A、B、E是活结点，E成为新的扩展结点n扩展E，先到达JCr45，皆得到一个可行解x=(0,1,1)，V=50L不可扩展，成为死结点，返回到Fn再扩展F到达MM是叶结点，且2550，不是最优解M不可扩展，成为死结点，返回到FnF没有可扩展结点，成为死结点，返回到C再扩展C到达GnCr=30，V=0，活结点为A、C、G，G为当前扩展结点n扩展G，先到达N，N是叶结点，且2550，不是最优解，又N不可扩展，返回到Gn再扩展G到达O，O是叶结点，且050，不是最优解，又O不可扩展，返回到GnG没有可扩展结点，成为死结点，返回到CC没有可扩展结点，成为死结点，返回到AnA没有可扩展结点，成为死结点，算法结束，最优解X=(0,1,1)，最优值V=50ACr=C=30，V=0Bw1=16，v1=45Cr=14，V=45C Cr=30，V=0DCrw2不可行解JCr45x=(0,1,1)Fw2=15，v2=25Cr=15，V=25M25n)output(x);/叶结点是可行解，输出解 else for(int i=f(n,t);i0)if(f(n,t)=g(n,t)for(int i=f(n,t);in)output(x);else for(int i=0;in)output(x);else for(int i=t;ic1时，以结点z为根的子树中所有结点都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪去。n用回溯法设计解装载问题的O(2n)计算时间算法。在某些情况下该算法优于动态规划算法。33四、算法描述void backtrack(int i)/搜索第i层结点 if(i n)/到达叶结点 /更新最优解bestw;return;if(cwbestw)bestw=cw;return;if(cw+wi n)/到达叶结点 更新最优解bestw;return;bestw=cw;return;/搜索子树 r-=wi;if(cw+wi bestw)/xi=0;backtrack(i+1);r+=wi;四、算法描述36构造最优解为了构造最优解，必须在算法中记录与当前最优值相应的当前最优解。为此，在类中添加了两个私有数据成员x和bestx。X用于记录从根至当前结点的路径；bestx记录当前最优解。算法搜索到达叶结点处，就修正bestx的值。37void backtrack(int i)/搜索第i层结点 if(i n)/到达叶结点 更新最优解bestw，bestx;return;if (cwbestw)for j=1;j=n;j+)bestxj=xj;bestw=cw;return;r-=wi;if(cw+wi bestw)/搜索右子树 xi=0;backtrack(i+1);r+=wi;385.3 批处理作业调度v一、问题描述v二、实例分析v三、算法描述39一、问题描述 给定n个作业的集合J1,J2,Jn。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。40二、实例分析这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分别是19，18，20，21，19，19。最佳调度方案是1,3,2，其完成时间和为18。tji机器1机器2作业121作业231作业32341三、算法描述void Flowshop:Backtrack(int i)if(i n)for(int j=1;j=n;j+)bestxj=xj;bestf=f;else for(int j=i;j f1)?f2i-1:f1)+Mxj2;f+=f2i;if(f bestf)Swap(xi,xj);Backtrack(i+1);Swap(xi,xj);f1-=Mxj1;f-=f2i;解空间：排列树复杂性：T(n)=O(n!)public class FlowShop static int n,/作业数 f1,/机器1完成处理时间 f,/完成时间和 bestf;/当前最优值 static int m;/各作业所需的处理时间 static int x;/当前作业调度 static int bestx;/当前最优作业调度 static int f2;/机器2完成处理时间425.5 n后问题v一、问题描述v二、问题分析v三、算法描述43一、问题描述在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。1 2 3 4 5 6 7 812345678QQQQQQQQ4445二、问题分析n解向量：(x1,x2,xn)xi表示皇后i放在i行上的列号，如(3,1,2,4)n显约束：xi=1,2,nn隐约束(ij)：1)不同列：xixj (不在同一列)2)不处于同一正、反对角线：|i-j|xi-xj|(不在同一斜线)46搜索求解：搜索求解：从从起按起按DFS搜索，搜索时应满足隐约束，搜索到叶搜索，搜索时应满足隐约束，搜索到叶结点输出解：结点输出解：(2,4,1,3)，(3,1,4,2)111121122123124131 132 133 134141 142 143 14412221222223224131473747576241 242 243 244153 154 155 1562134123412341 234123412341234 解空间树（满四叉树）47输出解：(2,4,1,3)(3,1,4,2)48三、算法描述bool Queen:Place(int k)/检查xk位置是否合法 for(int j=1;jn)sum+;else for(int i=1;i=n;i+)xt=i;if(约束函数 )Backtrack(t+1);v递归算法递归算法Place(t)算法效率：O(nnn)495.6 0-1背包问题v一、问题描述（略）v二、解表示和解空间 v三、解空间树 v四、无限界函数的算法v五、有限界函数的算法50n问题描述（略）n解表示和解空间:(x1,x2,xn)|xi0,1,i=1n n解空间树123101010i层次12n+1x1x251 0-1背包问题是子集选取问题。其解空间可以用子集树表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树中有可能包含最优解时才进入右子树搜索。否则将右子树剪去。为了便于计算上界，可先将物品依其单位重量价值从小到大排序，此后只要按顺序考察各物品即可。52n可行性约束函数：可行性约束函数：wixiCn上界函数：上界函数：Bound()53class Knapfriend int Knapsack(int p,int w,int c,int n);public:void print()for(int m=1;m=n;m+)coutbestxm;coutn)if(bestpcp)for(int j=1;j=n;j+)bestxj=xj;bestp=cp;return;if(约束函数约束函数 )/搜索左子树搜索左子树 xi=1;cw+=wi;cp+=pi;Backtrack(i+1);cw-=wi;cp-=pi;if(限界函数限界函数 )/搜索右子树搜索右子树 xi=0;Backtrack(i+1);cw+wibestp55int Knap:Bound(int i)/计算上界计算上界 int cleft=c-cw;/剩余容量剩余容量 int b=cp;/以物品单位重量价值递减序装入物品以物品单位重量价值递减序装入物品 while(i=n&wi=cleft)cleft-=wi;b+=pi;i+;/装满背包装满背包 if(i bestn61三、算法描述void Clique:Backtrack(int i)/计算最大团 if(i n)/到达叶结点 for(int j=1;j=n;j+)bestxj=xj;bestn=cn;return;/检查顶点 i 与当前团的连接 int OK=1;for(int j=1;j bestn62v选择合适的搜索顺序，可以使得上界函数更有效的发挥作用。例如在搜索之前可以将顶点按度从小到大排序。这在某种意义上相当于给回溯法加入了启发性。四、进一步改进635.8 图的m着色问题n一、基本概念n二、问题描述n二、问题分析n三、算法描述n四、复杂性分析64一、基本概念v给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。v若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。v求一个图的色数m的问题称为图的m可着色优化问题。65四色猜想：图 地图及其相应的平面图66二、问题描述v给定图G=（V，E）和m种颜色，如果这个图不是m可着色，给出否定回答；如果这个图是可着色的，找出所有不同的着色法。v用图的邻接矩阵a来表示无向连通图G=（V，E）。若（i，j）属于图的边集E，则ai,j=1,否则ai,j=0。v整数1，2，m用来表示m中不同的颜色。顶点i所着的颜色用Xi表示。67三、问题分析v定义解向量：(x1,x2,xn)表示顶点i所着颜色xi v构造解空间树。v问题的解空间可表示为一棵高度为n+1的完全m叉树。解空间树的第i层中每个结点都有m个儿子，每个儿子相应于xi的m个可能的着色之一。第n+1层结点均为叶子结点。68v可行性约束函数：顶点i与已着色的相邻顶点颜色不重复。(akj=1)&(xj!=xk)69三、算法描述void Color:Backtrack(int t)if(tn)sum+;for(int i=1;i=n;i+)cout xi ;cout endl;else for(int i=1;i=m;i+)xt=i;if(约束函数)Backtrack(t+1);xt=0;bool Color:Ok(int k)/检查颜色可用性 for(int j=1;j=n;j+)if(akj=1)&(xj=xk)return false;return true;Ok(t)70v图m可着色问题的解空间树中内结点个数是 mi(0in-1)。v对于每一个内结点，在最坏情况下，用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn)。因此，回溯法总的时间耗费是mi(mn)=nm(mn-1)/(m-1)=O(nmn)(0in-1)i=0n-1四、复杂性分析715.9 旅行售货员问题v一、问题描述v二、问题分析v三、算法描述v四、复杂性分析72n某售货员要到若干城市去推销商品，已知各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短。n该问题是一个NP完全问题，有(n-1)!条可选路线一、问题描述731234206305410ABCDEFGHIJKLMNOPQ1234344342322423最优解(1,3,2,4,1)，（1，4，2，3，1）最优值2574 (1)定义解空间：X=12341,12431,13241,13421,14231,14321 (2)构造解空间树：（3）约束条件？1202343061045ABCFLGM4334DHNIO4224EJPKQ32232341596625662559一、问题分析axi-1xj!=NoEdge&(cc+axi-1xi bestc|bestc=NoEdge)75解空间：排列树templatevoid Traveling:Backtrack(int i)if(i=n)if(axn-1xn!=NoEdge&axn1!=NoEdge&(cc+axn-1xn+axn1 bestc|bestc=NoEdge)for(int j=1;j=n;j+)bestxj=xj;bestc=cc+axn-1xn+axn1;else for(int j=i;j=n;j+)/是否可进入xj子树?if(axi-1xj!=NoEdge&(cc+axi-1xi bestc|bestc=NoEdge)/搜索子树 Swap(xi,xj);cc+=axi-1xi;Backtrack(i+1);cc-=axi-1xi;Swap(xi,xj);76复杂度分析复杂度分析算法backtrack在最坏情况下可能需要更新当前最优解O(n-1)!)次，每次更新bestx需计算时间O(n)，从而整个算法的计算时间复杂性为O(n!)。77n回溯法的最坏时间和空间复杂度（理论分析）n 时间性能:n最坏情况要搜索到整个解空间，因此复杂度是指数型。若剪枝操作有力，则平均性能往往很好。n 空间性能n回溯法的附加空间为O(h),其中h为搜索树的高度。5.13 回溯法效率分析785.13 回溯法效率分析通过前面具体实例的讨论容易看出，回溯算法的效率在很大程度上依赖于以下因素：(1)产生xk的时间；(2)满足显约束的xk值的个数；(3)计算约束函数constraint的时间；(4)计算上界函数bound的时间；(5)满足约束函数和上界函数约束的所有xk的个数。好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。79重排原理对于许多问题而言，在搜索试探时选取xi的值顺序是任意的。在其它条件相当的前提下，让可取值最少的在其它条件相当的前提下，让可取值最少的xi优先优先。从图中关于同一问题的2棵不同解空间树，可以体会到这种策略的潜力。图(a)中，从第1层剪去1棵子树，则从所有应当考虑的3元组中一次消去12个3元组。对于图(b)，虽然同样从第1层剪去1棵子树，却只从应当考虑的3元组中消去8个3元组。前者的效果明显比后者好。(a)(b)80 解空间的结构一经选定，影响回溯法效率的前三个因素就可以确定，只剩下生成结点的数目是可变的，它将随问题的具体内容及结点的不同生成方式而变动。即使对同一问题的不同实例，回溯法所产生的结点数也会有很大变化。对于一个实例，回溯法可能只产生O(n)个结点，而对另一个非常相近的实例，回溯法可能就会产生解空间中的所有结点。如果解空间的结点数是2n或n!，则在最坏情况下，回溯法的时间耗费一般为O(p(n)2n)或O(q(n)n!)。其中p(n)和q(n)均为n的多项式。回溯法的效率 81n=3，c=30p=(100,1,1)，v=(30,20,20)p=(1,1,100)，v=(20,20,30)82概率方法 对于一个具体的问题来说，回溯法的有效性往往就体现在当问题实例的规模n较大时，它能够用很少的时间就求出问题的解。而对于一个问题的具体实例我们又很难预测回溯法的算法行为。特别是我们很难估计出回溯法在解这一具体事例时所产生的结点数，这是分析回溯法效率的主要困难。83下面我们介绍一个概率算法，用于克服这一困难：1、基本思想 2、估算m 3、一个实例：8后问题84 当应用回溯法解某一具体问题的具体实例时，可用蒙特卡罗方法来估算回溯法将要产生的结点数目。85该方法的基本思想是：在解空间树上产生一条随机的路径，然后沿此路径估算满足约束条件的结点总数m：设x是所产生的随机路径上的一个结点，且位于解空间树的第i层上；对于x的所有儿子结点用约束函数检测出满足条件的结点数目mi；路径上下一个结点是从x的这mi个孩子中随机选取的；这条路径一直延伸到一个叶结点或没有满足条件的子结点为止；通过这些mi的值，就可以估算出解空间树中满足约束条件的结点总数m。基本思想 86在回溯法求解问题的所有解时，这个数特别有用，因为在这种情况下，解空间中所有满足条件的结点都必须生成；若只要求用回溯法找出问题的一个解，则所生成的结点数一般只是这m个结点中的一小部分，此时用m来估计回溯法生成的结点数就过于保守。87估算m的公式：88结点总数m=1+m0+m0*m1+m0*m1*m2+m0*m1*m2*m389