第5讲 回溯法专题讲座 编程大赛课程

第5章回溯法5.1回溯法概述与穷举的“笨拙”搜索相比，回溯法则是一种“聪明”的求解效益更高的搜索法。下面介绍回溯设计及其应用，体会回溯法相对于穷举的特点与优势。5.1.1回溯的概念有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往使用回溯法。回溯法是一种试探求解的方法：通过对问题的归纳分析，找出求解问题的一个线索，沿着这一线索往前试探，若试探成功，即得到解；若试探失败，就逐步往回退，换其他路线再往前试探。因此，回溯法可以形象地概括为“向前走，碰壁回头”。回溯法的基本做法是试探搜索，是一种组织得井井有条的、能避免一些不必要搜索的穷举式搜索法。回溯法在问题的解空间树中，从根结点出发搜索解空间树，搜索至解空间树的任意一点，先判断该结点是否包含问题的解；如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其父结点回溯；否则，进入该子树，继续搜索。从解的角度理解，回溯法将问题的候选解按某种顺序进行枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。倘若当前候选解除了不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。与穷举法相比，回溯法的“聪明”之处在于能适时“回头”，若再往前走不可能得到解，就回溯，退一步另找线路，这样可省去大量的无效操作。因此，回溯与穷举相比，回溯更适宜于量比较大，候选解比较多的问题。5.1.2回溯描述1．回溯的一般方法下面简要阐述回溯的一般方法。回溯求解的问题P，通常要能表达为：对于已知的由n元组(x1,x2,…,xn)组成的一个状态空间E={(x1,x2,…,xn)|xi∈si,i=1,2,…,n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中si是分量xi的定义域，且|si|有限，i=1,2,…,n。称E中满足D的全部约束条件的任一n元组为问题P的一个解。解问题P的最朴素的方法就是穷举法，上面已经作了介绍，即对E中的所有n元组逐一地检验其是否满足D的全部约束，若满足，则为问题P的一个解。显然，其计算量是相当大的。对于许多问题，所给定的约束集D具有完备性，即i元组(x1,x2,…,xi)满足D中仅涉及到x1,x2,…,xi的所有约束，意味着j(ji)元组(x1,x2,…,xj)一定也满足D中仅涉及到x1,x2,…,xj的所有约束，i=1,2,…,n。换句话说，只要存在0≤j≤n-1，使得(x1,x2,…,xj)违反D中仅涉及到x1,x2,…,xj的约束之一，则以(x1,x2,…,xj)为前缀的任何n元组(x1,x2,…,xj,xj+1,…,xn)也一定违反D中仅涉及到x1,x2,…,xj的一个约束，n≥i＞j。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组(x1,x2,…,xj)违反D中仅涉及x1,x2,…,xj的一个约束，就可以肯定，以(x1,x2,…,xj)为前缀的任何n元组(x1,x2,…,xj,xj+1,…,xn)都不会是问题P的解，因而就不必去搜索它们，即省略了对部分元素(xj+1,…,xn)的操作与测试。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比穷举法效率更高的算法。2.4皇后问题的回溯实施为了具体说明回溯的实施过程，先看一个简单实例。如何在4×4的方格棋盘上放置4个皇后，使它们互不攻击，即任意两个皇后不允许处在同一横排，同一纵列，也不允许处在同一与棋盘边框成45°角的斜线上。图5-1所示为应用回溯的实施过程，其中方格中的×表示试图在该方格放置一个皇后,但由于受前面已放置的皇后的攻击而放弃的位置。图5-14皇后问题回溯实施求解图（a）为在第1行第1列放置一个皇后的初始状态。图（b）中，第2个皇后不能放在第1、2列，因而放置在第3列上。图（c）中，表示第3行的所有各列均不能放置皇后，则返回第2行，第2个皇后需后移。图（d）中，第2个皇后后移到第4列，第3个皇后放置在第2列。图（e）中，第4行的所有各列均不能放置皇后，则返回第3行；第3个皇后后移的所有位置均不能放置皇后，则返回第2行；第2个皇后已无位可退，则返回第1行；第1个皇后需后移。图（f）中，第1个皇后后移至第2格。图（g）中，第2个皇后不能放在第1，2，3列，因而放置在第4列上。图（h）中，第3个皇后放在第1列；第4个皇后不能放置1，2列，于是放置在第3列。这样经以上回溯，得到4皇后问题的一个解：2413。继续以上的回溯探索，可得4皇后问题的另一个解：3142。3．回溯算法框架描述(1)回溯描述对于一般含参量m,n的搜索问题，回溯法框架描述如下：输入正整数n,m,(n≥m)i=1;a[i]=元素初值;while(1){for(g=1,k=i-1;k=1;k--)if(约束条件1)g=0;//检测约束条件,不满足则返回if(g&&约束条件2)printf(a[1-m]);//输出一个解if(in&&g){i++;a[i]=取值点;continue;}while(a[i]==回溯点&&i1)i--;//向前回溯if(a[i]==n&&i==1)break;//退出循环，结束elsea[i]=a[i]+1;}具体求解问题的试探搜索范围与要求不同，在应用回溯设计时，需根据问题的具体实际确定数组元素的初值、取值点与回溯点，同时需把问题中的约束条件进行必要的分解，以适应上述回溯流程。其中实施向前回溯的循环while(a[i]==回溯点&&i1)i--;是向前回溯一步，还是回溯两步或更多步，完全根据a[i]是否达到回溯点来确定。例如，回溯点是n，i=6，当a[6]=n时回溯到i=5；若a[5]=n时回溯到i=4；依此类推，到a[i]达到回溯点则停止。图5-1所示的4皇后问题迭代回溯过程描述为：n=4;i=1;a[i]=1;while(1){g=1;for(k=i-1;k=1;k--)if(a[i]=a[k]&&abs(a[i]-a[k])=i-k)g=0;//检测约束条件,不满足则返回if(g&&i==4)printf(a[1-4]);//输出一个解if(in&&g){i++;a[i]=1;continue;}while(a[i]==n&&i1)i--;//向前回溯if(a[i]==n&&i==1)break;//退出循环结束elsea[i]=a[i]+1;}以上回溯体现在迭代式i=i-1，因而又称为迭代回溯。此外，递归也能实现回溯。（2）递归回溯intput(intk){inti,j,u;if(k=问题规模){u=0;if(约束条件)u=1;//当k时不可操作if(u==0)//当k时可操作{if(k==规模)//若已满足规模，则打印出一个解printf(一个解);elseput(k+1);//调用put(k+1)}}}在调用put(k)时，当检测约束条件知不可操作（记u=1），即再往前不可能得解，此时当然不可能输出解，也不调用put(k+1)，而是回溯，返回调用put(k)之处。这就是递归回溯的机理。如果是主程序调用put(1)，最后返回到主程序调用put(1)的后续语句，完成递归。图5.1所示的4皇后问题迭代回溯过程描述为：intput(intk){inti,j,u;if(k=4){for(i=1;i=4;i++)//探索第k行从第1格开始放皇后{a[k]=i;for(u=0,j=1;j=k-1;j++)if(a[k]==a[j]||abs(a[k]-a[j])==k-j)u=1;//若第k行第i格放不下,则置u=1if(u==0)//若第k行第i格可放,则检测是否满4行{if(k==4)//若已放满到4行时，则打印出一个解{s++;printf();for(j=1;j=4;j++)printf(%d,a[j]);}elseput(k+1);//若没放满4行,则放下一行put(k+1)}}}}4.回溯法的效益分析应用回溯设计求解实际问题，由于解空间的结构差异，很难精确计算与估计回溯产生的结点数，因此回溯法的复杂度是分析回溯法效率时遇到的主要困难。回溯法产生的结点数通常只有解空间结点数的一小部分，这也是回溯法的计算效率大大高于穷举法的原因所在。回溯求解过程实质上是一个遍历一棵“状态树”的过程，只是这棵树不是遍历前预先建立的。回溯算法在搜索过程中，只要所激活的状态结点满足终结条件，应该把它输出或保存。由于在回溯法求解问题时，一般要求输出问题的所有解，因此在得到结点后，同时也要进行回溯，以便得到问题的其他解，直至回溯到状态树的根且根的所有子结点均已被搜索过为止。组织解空间便于算法在求解集时更易于搜索，典型的组织方法是图或树。一旦定义了解空间的组织方法，这个空间即可从开始结点进行搜索。回溯法的时间通常取决于状态空间树上实际生成的那部分问题状态的数目。对于元组长度为n的问题，若其状态空间树中结点总数为n!，则回溯算法的最坏情形的时间复杂度可达O(p(n)n!)；若其状态空间树中结点总数为2n，则回溯算法的最坏情形的时间复杂度可达O(p(n)2n)，其中p(n)为n的多项式。对于不同的实例，回溯法的计算时间有很大的差异。对于很多具有大n的求解实例，应用回溯法一般可在很短的时间内求得其解，可见回溯法不失为一种快速有效的算法。对于某一具体实际问题的回溯求解，常通过计算实际生成结点数的方法即蒙特卡罗方法（Montecarlo）来评估其计算效率。蒙特卡罗方法的基本思想是在状态空间树上随机选择一条路径(x0,x1,…,xn-1)，设X是这一路径上部分向量(x0,x1,…,xk-1)的结点，如果在Ｘ处不受限制的子向量数是mk，则认为与X同一层的其他结点不受限制的子向量数也都是mk。也就是说，若不受限制的x0取值有m0个，则该层上有m0个结点；若不受限制的x1取值有m1个，则该层上有m0m1个结点；依此类推。由于认为在同一层上不受限制的结点数相同，因此，该路径上实际生成的结点数估计为0010121mmmmmmm…计算路径上结点数m的蒙特卡罗算法描述如下：//已知随机路径上取值数据m0,m1,…,mk-1m=1;t=1;for(j=0;j=k-1;j++){t=t*m[j];m=m+t;}printf(“%ld”,m);把所求得的随机路径上的结点数（或若干条随机路径的结点数的平均值）与状态空间树上的总结点数进行比较，由其比值可以初步看出回溯设计的效益。在下面的n皇后问题的回溯求解时将具体应用以上蒙特卡罗算法估计回溯设计的效益。5.2桥本分数式5.2.1桥本分数式1．案例提出日本数学家桥本吉彦教授于1993年10月在我国山东举行的中日美三国数学教育研讨会上向与会者提出以下填数趣题：把1,2,…,9这9个数字填入下式的9个方格中(数字不得重复)，使下面的分数等式成立桥本教授当即给出了一个解答。这一分数式填数趣题究竟共有多少个解答？试求出所有解答。(等式左边两个分数交换次序只算一个解答)。这一填数趣题的解是否唯一？如果不唯一究竟有多少个解?由人工推算求解难度太大，通过程序设计由计算机来探求更为合适。2．回溯设计(1)设计要点我们采用回溯法逐步调整探求。把式中9个□规定一个顺序后，先在第一个□中填入一个数字（从1开始递增），然后从小到大选择一个不同于前面□的数字填在第二个□中，依此类推，把九个□都填入没有重复的数字后，检验是否满足等式。若等式成立，打印所得的解。然后第九个□中的数字调整增1再试，直到调整为9（不能再增）；返回前一个□中数字调整增1再试；依此类推，直至第一个□中的数字调整为9时，完成调整探求。可见，问题的解空间是9位的整数组，其约束条件是9位数中没有相同数字且必须满足分式的要求。为此，设置a数组，式中每一□位置用一个数组元素来表示：)9()8()7()6()5()4()3()2()1(aaaaaaaaa