算法分析课件第08章.ppt

《算法分析课件第08章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章回溯8.1一般方法8.28-皇后问题入口8.1一般方法什么是回溯回溯迷宫游戏什么是回溯法回溯法是一种搜索算法通用的解题法回溯法是以深度优先的方式系统地搜索问题的解,它适用于解一些组合数较大的问题。寻求一组解，或求满足某些约束条件的最优解。回溯出口回溯回溯解的形式n-元组(x1,…,xn),其中xi取自某个有穷集Si规范函数P(x1,…,xn)假设集合Si的大小是mi,满足规范函数P的可能的元组数为m=m1m2…mn硬性处理:构造m个n元组并依次测试是否满足P回溯法不断地用修改过的限界函数Pi(x1,…,xi)去测试正在构造的

2、n元组的部分向量,看是否可能导致最优解,如果不能,就将可能要测试的mi+1…mn个向量略去。回溯法的基本概念回溯法的解需要满足一组综合的约束条件,通常分为:显式约束和隐式约束显式约束条件:限定每个x只从一个给定的集合上取值,满足显式约束的所有元组确定一个可能的解空间例:xi0,si={所有非负实数}隐式约束条件:描述了xi必须彼此相关的情况隐式约束条件指前面提到的规范函数解空间中满足隐式约束条件的元组称为可行解。回溯法的基本概念可能与问题实例有关，也可能无关。与问题实例有关在一个8*8棋盘上放8个皇后,使每两个皇后之间都不能互相

3、“攻击”,即：使得每两个皇后都不能在同一行、同一列及同一条斜角线上。将皇后i放在行i上，8皇后问题可以表示为8-元组(x1,…x8)，其中xi是皇后i被放置的列号。显式约束条件:Si={1,2,3,4,5,6,7,8},1≤i≤8隐式约束条件:没有两个xi可以相同,且没有两个皇后可以在同一条斜角线上。QQQQQQQQ解空间：88解空间：8！(4,6,8,2,7,1,3,5)例8.1（8-皇后问题）例8.2子集和数问题已知n+1个正数：wi,1in,和M。要求找出{wi}的所有子集使得子集中元素之和等于M。例如：n=4,(w1,

4、w2,w3,w4)=(11,13,24,7)，M=31。则满足要求的子集是(11,13,7)和(24,7)可表示为(1,2,4)和(3,4)子集和数问题的描述解是k-元组(x1,…,xk)，1kn显示约束条件xi{j

5、j是整数,wj的下标且1jn}隐式约束条件xi互不相同且相应的wk的和数是M,k=xi，xi

6、表示为(1,1,0,1)和(0,0,1,1)解空间的树结构搜索算法通过系统的检索给定问题的解空间来确定问题的解。解空间可以用树结构加以描述。对于一个给定的解空间，可能有多种树结构。例8.3n-皇后问题n-皇后问题是8-皇后问题的推广。n个皇后将被放置在n×n的棋盘上且使得没有两个皇后可以互相攻击。这是8-皇后问题的推广，其解空间由n-元组(1,2,…,n)的n!个排列所组成。n=4时的树结构－－排列树。树的边由xi的可能的取值标记。由i级到i+1级节点的边给出xi的值。解空间由从根节点到叶节点的所有路径定义。14567433410

7、1112942421415161732322021222343432526272841143031323331133813341924291342183450342………4-皇后问题的解空间树x1=1x2=212345678910111213141516x2=2x2=3x2=4x2=3x2=4x2=4x1=1x1=2x1=3x1=4x3=3x3=4x3=4x3=4x4=4子集和数问题的解空间树1解空间树中的路径对应一个向量根结点到自身的空路径对应一个空向量()树中红色的路径分别对应向量:(1,2,4)(2,3,4)(4)17123

8、456789101112131415161820232425192122262728293031x1=1x1=0x2=1x3=1101010x2=0x3=0x3=1x3=0x2=1x2=0x3=1x3=0x3=1x3=01010101010子集和数问题的解空间树2注:结点按D-检索方式编号从根结点到叶结点的一条路径确定解空间中的一个元组树中红色路径表示元组(1,1,0,1)回溯法在求问题的所有解时,要遍历树才能结束。回溯法在求问题的任一解时,只要搜索到问题的一个解就可以结束。回溯法在包含问题所有解的解空间树中,按深度优先的策略,从

9、根结点出发搜索解空间树。回溯法搜索至解空间树的任一结点时,先判断该结点是否肯定不包含问题的解。如果肯定不包含,则跳过以该结点为根的子树,逐层向其祖先结点回溯。否则就进入该子树,继续按深度优先的策略进行搜索。回溯法的基本概念解空间树(状态空间树)的术