Chapter 16. Traceback.ppt

《Chapter 16. Traceback.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第16章回溯例16.1(8-皇问题)在8×8的棋盘上放置8个皇后,使得这8个皇后不在同一行、同一列及同一斜角线上.如下图16.1：QQQQQQQQ12345678123456788-皇后问题的形式化8皇后问题的解可以表示为一个8-元组(x1,…,x8),其中xi是放在第i行的皇后所在的列号,则8皇后问题可形式化为在88个8-元组中找满足以下约束条件的元组:xi≠xjforalli,j

2、xi-xj

3、≠

4、j-i

5、这88个8-元组构成的集合称为8皇后问题的解空间-搜索范围.如果将约束条件之一,任意两个皇后不在同一列上,加入到元组的定义中,这时每个8-元组为(1,2,3,4,5,6,7,8)的一

6、个排列,解空间的大小由88个元组减少到8！个元组.解空间不是唯一的,取决于算法的设计.设计解空间时还要考虑生成解空间的算法的复杂度;在8皇后问题中,如果加入第二个条件,解空间很难生成.16.1搜索问题的形式化-解空间假定问题的解能用n-元组(X1,…,Xn),表示,其中Xi取自某个有穷集Si.这些n-元组构成的集合称为问题的解空间.假设

7、Si

8、=mi,则解空间的大小为m=m1m2…mn.我们考虑两类问题:存在性问题是:求满足某些条件的一个或全部元组,如果存在这样的元组算法应返回Yes,否则返回No.这些条件称为约束条件.优化问题:给定一组约束条件,在满足约束条件的元组中求使某目标函数达到

9、最大（小）值的元组.满足约束条件的元组称为问题的可行（feasible）解.16.1搜索问题的形式化解决这类问题的最一般方法是使用搜索技术,即系统化的搜索解空间的技术.本章介绍回溯法,下章介绍分支限界法.例16.2：子集和数问题已知n+1个正数：wi,1in,和M.要求找出{wi

10、1in}的所有子集,使得子集内元素之和等于M.例如：n=4,(w1,w2,w3,w4)=(11,13,24,7),M=31.则满足要求的子集是(11,13,7)和(24,7).我们可以用wi的下标i构成的元组表示一个解,则这两个解可表示为(1,2,4)和(3,4).元组(1,2,4)和(2,1,4)代表

11、同一子集,为此限制元组分量按升序排列,即不考虑元组(2,1,4).还可以用其他方式表示一个解,如下:子集和数问题的另一种表示每个子集由n-元组(x1,…,xn)表示,其中xi{0,1},1in,表示：xi=0,表示没有选择wi;xi=1,表示选择wi;则例中的解可以表示为(1,1,0,1)和(0,0,1,1)解空间的状态空间树任何搜索算法都可以用建立在解空间上的状态空间树加以描述.状态空间树是我们尝试选择元组的各个分量时产生的树结构.搜索算法并非事先将状态空间树存在计算机内再进行遍历,而是通过展开状态空间树来找所求的解.展开过程中通过使用启发式的限界方法(剪去状态空间树上的某些分枝

12、)使搜索算法只展开状态空间树的一部分,从而降低搜索算法的时间和空间复杂度.例16.3：n-皇后问题n-皇后问题是8-皇后问题的推广.n个皇后将被放置在n×n的棋盘上且使得没有两个皇后可以互相攻击.这是8-皇后问题的推广,其解空间由n-元组(1,2,…,n)的n!个排列所组成.其状态空间树如图6.2所示(n=4).树的边由xi的可能的取值标记.由i级到i+1级节点的边给出xi的值.这种树称为排列树.从根节点到叶节点的一条路径对应解空间的一个元组.图16.24-皇后问题的状态空间树图16.3子集和数问题的状态空间树图16.4子集和数问题的状态空间树有关状态空间树的术语状态空间树的每个结点代表

13、问题求解过程中达到的一个状态,根节点到它的路径代表对一些分量已作出的选择.状态空间树的所有节点构成的集合称为求解该问题的状态空间.根节点到状态空间树的一个节点X的路径可以表示为(x(1),…,x(k)),其中x(i),1≤i≤k,为搜索过程中已经选择的分量.今后我们也用这个元组标识该节点:X=(x(1),…,x(k)).(x(1),…,x(k))也对应一个子问题,即在后n-k个元组分量所对应的子空间上找满足要求的解.该子空间是状态空间树中以X为根的子树.所以也称节点X为问题节点.如果从根节点到节点S的那条路径确定了解空间的一个元组,则称S为状态空间树的一个解节点.如果一个解节点S(代表的

14、元组)满足约束条件称其为答案节点.状态空间树的展开方法每个搜索算法都是一种系统地展开状态空间树的算法.我们用以下术语描述展开状态空间树的各种方法.活结点:已展开了部分子节点,但所有子结点尚未全部展开的结点.死结点:被限界或已展开了所有子结点的结点.E-结点:当前正在展开子结点的活结点.状态空间树的展开方法深度优先展开方法:一个E-结点展开自己的一个子结点后,就让该子结点成为E-结点的展开方法(相当于对状态空间树做深度优先搜索),称为