算法分析与设计软件工程.ppt

《算法分析与设计软件工程.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

4、(0,0,0),(0,0,1),(0,1,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个可能解。对物品1的选择重20，价值20对物品3的选择重10，价值25对物品2的选择重15，价值301111110000000112345781112141

5、531069解空间树深度优先搜索解空间树背包重量251不可行解价值=20价值=55价值=30价值=25价值=011110000001128111214151310690-1背包生成树最终结果为（0,1,1），总重量为25，总价值为55物品价值{20,30,25}皇后问题N皇后问题，是一个古老而著名的问题，是回溯算法的典型例题：在N*N格的格子上摆放N个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？为了简单起间，考虑在4*4的棋盘上放置4个皇后的问题，把这个问题称为4皇后问题。4后问题可以表示成一个四元组（X1

6、，X2，X3，X4），i（i=1,2,3,4）表示第i行，Xi（i=1,2,3,4）表示第i行皇后的列位置。12341234皇后1皇后2皇后3皇后4皇后问题继续以上的回溯探索，可得4皇后问题的另一个解（3，1，4，2）。下图所示为应用回溯的实施过程，其中方格中的×表示在该方格放置一个皇后,但由于受前面已放置的皇后的攻击而放弃的位置。(2,4,1,3)定义问题的解空间解题步骤因为每一行只能放置一个皇后，每一个皇后在每一行上有4个位置可供选择，因此在4*4格的棋盘上放置4个皇后，有44种可能的布局。又因为每一个皇后不能放在同一列，所以它有4！种可能的解。确定

7、解空间树的结构4后问题的解空间可以用一棵完全4叉树来表示，如下图所示：4后问题的状态空间树其中，第1、2、3、4层节点到上一层节点的路径上所标记的数字，对应于第1、2、3、4行皇后可能的列位置。搜索以深度优先方式搜索解空间根据题意，约束方程为：xixj

8、i–j

9、

10、xi–xj

11、皇后i,j不在同一列上皇后i,j不在同一斜线上391115161924初始化(0,0,0,0)（1,0,0,0）（1,2,0,0）61575955524045QQQQQQQQ4后问题的生成树回溯法的效率分析通过前面具体实例的讨论容易看出，回溯算法的效率在很大程度上依赖于以下因素：

12、(1)产生x[k]的时间；(2)满足约束的x[k]值的个数；(3)计算约束函数c