算法分析与设计软件工程

1、算法分析与设计, 回溯法,专业：软件工程 姓名：王鸿雁 学号：2013090013,回溯的概念,回溯法的基本思想,回溯法的应用,回溯法的效率分析,主要内容：,回溯的概念,相信大家都玩过走迷宫的游戏吧，在走迷宫的过程中，我们从入口 出发，到达路口后，选择 一条岔路进入，到达下一个路口，然后再 选择一条岔路，。在这个过程中，我们经常会走入死路，这时 我们只能退回到最近的路口，重新选择一条岔路，而如果某个路口 所有的岔路都是死路的话，还必须再往前面的路口退回去，这样不 停的进进退退，直到最后走出迷宫为止。像走迷宫这样，遇到死路 就回头的搜索思路就叫做“回溯”。,从问题的某种可能情况出发，搜索所有能到

2、达的可能情况，然后以其 中一种可能的情况为新的出发点，继续向下探索，当所有可能情况都 探索过且都无法到达目标的时候，再回退到上一个出发点，继续探索 另一个可能情况，这种不断回头寻找目标的方法称为“回溯法”。,回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。,求问题所有解：要回溯到根

3、，且根结点的所有子树都已被搜索遍才结束。 求任一解：只要搜索到问题的一个解就可结束。,回溯法的基本思想,回溯法有“通用的解题法”之称,回溯法解题步骤: 1).针对所给问题,定义问题的解空间，该空间包含问题的解 2).确定状态空间树的结构 3).列出约束条件，以深度优先方式搜索解空间，生产搜索树，得 到问题的解,回溯法的应用,皇后问题,迷宫问题,0-1背包问题,自然数排列问题,图的着色问题,可能解由一个等长向量x1, x2, , xn组成，其中xi=1(1in)表示物品i 装入背包，xi=0表示物品i没有装入背包，当n=3时，其解空间是： (0, 0, 0), (0, 0, 1), (0, 1,

4、 0), (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1) ,0-1背包问题,问题描述： 对于n=3的0/1背包问题，三个物品的重量为20, 15, 10，价值为20, 30, 25，背包容量为25，求怎样选取物品将得到效益最大（物品不可分割）？,问题的解空间,对于n=3的0/1背包问题，其解空间树如图所示，树中的8个叶子结点分别代表该问题的8个可能解。,解空间树,深度优先搜索解空间树,背包重量 25,0-1背包 生成树,最终结果为（0,1,1），总重量为25，总价值为55,物品价值20, 30, 25,皇后问题,N皇后问题，是一个古老

5、而著名的问题，是回溯算法的典型例题：在N*N格的格子上摆放N个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？,为了简单起间，考虑在4*4的棋盘上放置4个皇后的问题，把这个问题称为4皇后问题。4后问题可以表示成一个四元组（X1，X2，X3，X4），i（i=1,2,3,4 ）表示第 i 行，Xi（i=1,2,3,4）表示第i行皇后的列位置。,皇后问题,继续以上的回溯探索，可得4皇后问题的另一个解（3，1，4，2）。,下图所示为应用回溯的实施过程，其中方格中的表示在该方格放置一个皇后,但由于受前面已放置的皇后的攻击而放弃的位置。,(2,4,1,3),定义

6、问题的解空间,解题步骤,因为每一行只能放置一个皇后，每一个皇后在每一行上有4个位置可供选择，因此在4*4格的棋盘上放置4个皇后，有44种可能的布局。又因为每一个皇后不能放在同一列，所以它有4！种可能的解。,确定解空间树的结构,4后问题的解空间可以用一棵完全4叉树来表示，如下图所示：,4后问题的状态空间树,其中，第1、2、3、4层节点到上一层节点的路径上所标记的数字，对应于第1、2、3、4行皇后可能的列位置。,搜索以深度优先方式搜索解空间,根据题意， 约束方程为：,xi x j | i j | | x i x j |,皇后i,j不在同一列上,皇后i,j不在同一斜线上,3,9,11,15,16,1

7、9,24,初始化(0,0,0,0),（1,0,0,0）,（1,2,0,0）,61,57,59,55,52,40,45,4后问题的生成树,回溯法的效率分析,通过前面具体实例的讨论容易看出，回溯算法的效率在很大程度上依赖于以下因素： (1)产生xk的时间； (2)满足约束的xk值的个数； (3)计算约束函数constraint的时间； (4)满足约束函数和上界函数约束的所有xk的个数。,可以用“重排原理”提高效率,一个好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。,对于许多问题而言，在搜索试探时选取xi值

8、的顺序是任意的。在其它条件相当的前提下，让可取值最少的xi优先将更为有效。从图中关于同一问题的2棵不同解空间树，可体会这种策略的潜力。,图(a)从第1层剪去1棵子树，则从所有应当考虑的3元组中一次消去12个3元组。图(b)同样从第1层剪去1棵子树，却只从应当考虑的3元组中消去8个3元组。前者的效果明显比后者好。,回溯法总结-重排原理,解空间的结构一经选定，影响回溯法效率的前三个因素就可以确定，只剩下生成结点数的数目是可变的，它将随问题的具体内容以及结点的不同生成方式而变动。即使是对同一问题的不同实例，回溯法所产生的结点数也会有很大变化。,对一个具体问题来说，回溯法的有效性往往就体现在当问题实例的规模n较大时，它能够用很