回溯法的效率分析

《回溯法的效率分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、回溯法概述与穷举的“笨拙”搜索相比，回溯法则是一种“聪明”的求解效益更高的搜索法。下面介绍回溯设计及其应用，体会回溯法相对于穷举的特点与优势。回溯的概念有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往使用回溯法。回溯法是一种试探求解的方法：通过对问题的归纳分析，找出求解问题的一个线索，沿着这一线索往前试探，若试探成功，即得到解；若试探失败，就逐步往回退，换其他路线再往前试探。因此，回溯法可以形象地概括为“向前走，碰壁回头”。回溯法的基本做法是试探搜索，是一种组织得井井有条的、能避免一些不必要搜索的穷举式搜索法。回溯

2、法在问题的解空间树中，从根结点出发搜索解空间树，搜索至解空间树的任意一点，先判断该结点是否包含问题的解；如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其父结点回溯；否则，进入该子树，继续搜索。从解的角度理解，回溯法将问题的候选解按某种顺序进行枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。倘若当前候选解除了不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。与穷举法相

3、比，回溯法的“聪明”之处在于能适时“回头”，若再往前走不可能得到解，就回溯，退一步另找线路，这样可省去大量的无效操作。因此，回溯与穷举相比，回溯更适宜于量比较大，候选解比较多的问题。5.1.2回溯描述1．回溯的一般方法下面简要阐述回溯的一般方法。回溯求解的问题P，通常要能表达为：对于已知的由n元组(x1,x2,…,xn)组成的一个状态空间E={(x1,x2,…,xn)

4、xi∈si,i=1,2,…,n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中si是分量xi的定义域，且

5、si

6、有限，i=1,2,…,n。

7、称E中满足D的全部约束条件的任一n元组为问题P的一个解。解问题P的最朴素的方法就是穷举法，上面已经作了介绍，即对E中的所有n元组逐一地检验其是否满足D的全部约束，若满足，则为问题P的一个解。显然，其计算量是相当大的。对于许多问题，所给定的约束集D具有完备性，即i元组(x1,x2,…,xi)满足D中仅涉及到x1,x2,…,xi的所有约束，意味着j(j

8、j的约束之一，则以(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)的操作与测试。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比

9、穷举法效率更高的算法。2.4皇后问题的回溯实施为了具体说明回溯的实施过程，先看一个简单实例。如何在4×4的方格棋盘上放置4个皇后，使它们互不攻击，即任意两个皇后不允许处在同一横排，同一纵列，也不允许处在同一与棋盘边框成45°角的斜线上。图5-1所示为应用回溯的实施过程，其中方格中的×表示试图在该方格放置一个皇后,但由于受前面已放置的皇后的攻击而放弃的位置。图5-14皇后问题回溯实施求解图（a）为在第1行第1列放置一个皇后的初始状态。图（b）中，第2个皇后不能放在第1、2列，因而放置在第3列上。图（c）中，表示第3行的所有各列均不能放置皇后，则返回第

10、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．回溯算法框架

11、描述(1)回溯描述对于一般含参量m,n的搜索问题，回溯法框架描述如下：输入正整数n,m,(n≥m)i=1;a[i]=<元素