算法分析课件第08章

1、第第 八八 章章回回 溯溯8.1 一般方法一般方法8.2 8-皇后问题皇后问题入口入口8.1 一般方法一般方法什么是回溯什么是回溯回溯回溯迷宫游戏迷宫游戏什么是回溯法什么是回溯法回溯法是一种回溯法是一种搜索搜索算法算法通用通用的解题法的解题法回溯法是以回溯法是以深度优先深度优先的方式的方式系统地系统地搜索问题的搜索问题的解解, 它适用于解一些它适用于解一些组合数较大组合数较大的问题。的问题。寻求一组解，或求满足某些约束条件的最优解。寻求一组解，或求满足某些约束条件的最优解。回溯回溯出口出口回溯回溯回溯回溯p解的形式解的形式n-元组元组(x1,xn),其中其中xi取自某个有穷集取自某个有穷集Si

2、p规范函数规范函数 P(x1,xn) p假设集合假设集合Si的大小是的大小是mi,满足规范函数满足规范函数P的可能的元的可能的元组数为组数为m=m1m2mnp硬性处理硬性处理:构造构造m个个n元组并依次测试是否满足元组并依次测试是否满足Pp回溯法回溯法 不断地用修改过的限界函数不断地用修改过的限界函数Pi(x1,xi)去测试正在去测试正在构造的构造的n元组的部分向量元组的部分向量, 看是否可能导致最优解看是否可能导致最优解, 如果不能如果不能, 就将可能要测试的就将可能要测试的mi+1 mn个向量略去。个向量略去。 回溯法的基本概念回溯法的基本概念回溯法的解需要满足一组综合的约束条件回溯法的解

3、需要满足一组综合的约束条件, 通常分通常分为为: 显式约束和隐式约束显式约束和隐式约束显式约束条件显式约束条件: 限定每个限定每个x只从一个给定的集合上取只从一个给定的集合上取值值, 满足显式约束的满足显式约束的所有元组所有元组确定一个可能的解空间确定一个可能的解空间 例例: xi 0 , si=所有非负实数所有非负实数隐式约束条件隐式约束条件: 描述了描述了xi必须彼此相关的情况必须彼此相关的情况 隐式约束条件指前面提到的规范函数隐式约束条件指前面提到的规范函数解空间中满足隐式约束条件的元组称为解空间中满足隐式约束条件的元组称为可行解可行解。 回溯法的基本概念回溯法的基本概念可能与问题实例有

4、可能与问题实例有关，也可能无关。关，也可能无关。与问题实例有关与问题实例有关p在一个在一个8*8棋盘上放棋盘上放8个皇后个皇后, 使每两使每两个皇后之间都不能互相个皇后之间都不能互相“攻击攻击”, 即：即：使得每两个皇后都不能在使得每两个皇后都不能在同一行、同一行、同一列及同一条斜角线上同一列及同一条斜角线上。p将皇后将皇后i放在行放在行i上，上，8皇后问题可以皇后问题可以表示为表示为8-元组元组(x1,x8)，其中，其中xi是皇是皇后后i被放置的列号。被放置的列号。p显式约束条件显式约束条件: Si=1, 2, 3, 4, 5, 6, 7, 8, 1i8p隐式约束条件隐式约束条件: 没有两个

5、没有两个xi可以相同可以相同, 且没有两个皇后可以在同一条斜角且没有两个皇后可以在同一条斜角线上线上。QQQQQQQQ解空间：解空间：88解空间：解空间：8！(4,6,8,2,7,1,3,5)例例8.1（8-皇后问题）皇后问题）例例8.2 子集和数问题子集和数问题p已知已知n+1个正数：个正数：wi, 1 i n, 和和M。要求找出要求找出wi 的的所有子集所有子集使得使得子集中元素之和等于子集中元素之和等于M。p例如：例如：n=4, (w1,w2,w3,w4)=(11,13,24,7)，M=31。 则满足要求的子集是则满足要求的子集是(11,13,7) 和和(24,7) 可表示为可表示为(1

6、,2,4) 和和 (3,4)子集和数问题的描述子集和数问题的描述p解是解是k-元组元组(x1,xk) ，1 k n p显示约束条件显示约束条件 xi j|j是整数是整数,wj的下标且的下标且1 j np隐式约束条件隐式约束条件 xi互不相同互不相同且相应的且相应的wk的和数的和数是是M, k=xi，xi0) do if ( 还剩有没检验的还剩有没检验的X(k)使得使得X(k)T(X(1)X(k-1) and B(X(1)X(k)=TRUE ) then if (X(1) X(k)是一条抵达答案结点的路径是一条抵达答案结点的路径) then print ( X(1)X(k) ); endif k

7、k+1; else kk-1; endifrepeatend BACKTRACK/回溯回溯/打印数组打印数组X/考虑下一个集合考虑下一个集合在在X(1)X(k-1)已经被确定已经被确定的情况下的情况下, T(X(1)X(k-1)给出给出X(k)的所有可能的取值的所有可能的取值,限界函数限界函数B(X(1)X(k)判断判断哪些哪些X(k)满足隐式约束条件满足隐式约束条件131513211981416procedure BACKTRACK(n) int k, n local X(1: n) k 1 while (k0) do if (还剩有没检验的还剩有没检验的X(k) 使得使得X(k)T(X(1

8、)X(k-1) and B(X(1)X(k)=TRUE) then if (X(1) X(k)是一条是一条 抵达答案结点的路径抵达答案结点的路径) then print ( X(1)X(k) endif k k+1 else k k-1 endif repeatend BACKTRACKk=2k=3k=4若只需要一个解若只需要一个解,怎样修改算法？怎样修改算法？procedure RBACKTRACK(k)global X(1:n); int k, n;for ( 满足下式的每个满足下式的每个X(k), X(k) T(X(1)X(k-1) and B(X(1),B(k)=true) do if

9、 (X(1),X(k)是一条抵达答案结点的路径是一条抵达答案结点的路径 then print (X(1)X(k); call RBACKTRACK(k+1); end RBACKTRACK 回溯算法的递归描述回溯算法的递归描述进入算法时进入算法时, 解向量解向量X中的中的前前k-1个个分量分量X(1) X(k-1)已经被赋值已经被赋值对于所有可以由根结点对于所有可以由根结点到达到达, 并可能使限界函数并可能使限界函数B为真的结点为真的结点X(k), 判断判断(X(1)X(k)是否是一条是否是一条能抵达答案结点的路径能抵达答案结点的路径效率估计效率估计 回溯法的效率主要取决于四种因素回溯法的效率

10、主要取决于四种因素: 生成下一个生成下一个X(k)的时间的时间 满足显示约束条件的满足显示约束条件的X(k)的数目的数目 限界函数限界函数Bi的计算时间的计算时间 满足满足Bi的的X(k)的数目的数目 限界函数限界函数：减少结点数，本身的计算时间减少结点数，本身的计算时间生成节点的时间生成节点的时间子节点的数量子节点的数量检验节点的时间检验节点的时间通过检验的节点数量通过检验的节点数量在计算时间和减少节点数量上进行折中在计算时间和减少节点数量上进行折中p一旦选定了一种状态空间树结构一旦选定了一种状态空间树结构, 前三种因素对于所前三种因素对于所要解决的实例没有多大的关系要解决的实例没有多大的关

11、系, 只有只有第四种因素第四种因素,对于对于问题的不同实例问题的不同实例, 生成的结点数是不相同的生成的结点数是不相同的。p易知，回溯算法最坏情况下的时间复杂度为易知，回溯算法最坏情况下的时间复杂度为O(p(n)2n)或或O(q(n)n!)，其中，其中p(n)和和q(n)为为n的多项式。的多项式。p由于回溯法对同一问题不同实例在计算时间上出现巨由于回溯法对同一问题不同实例在计算时间上出现巨大差异，大差异，在在n很大时，对某些实例仍然十分有效很大时，对某些实例仍然十分有效。p用回溯算法处理一棵树所要生成的节点数，可以用用回溯算法处理一棵树所要生成的节点数，可以用蒙蒙特卡罗方法特卡罗方法估算出来。

12、估算出来。效率估计效率估计效率估计效率估计-估计满足估计满足Bi的的X(k)的数目的数目p蒙特卡罗方法蒙特卡罗方法在状态空间树中生成一条在状态空间树中生成一条随机路径随机路径。设设X是这条路径上是这条路径上第第i级级的一个结点。的一个结点。在结点在结点X处处用限界函数确定用限界函数确定没受限界的儿子结点没受限界的儿子结点数目数目mi，在这，在这mi个儿子结点中个儿子结点中随机选择随机选择一个结点一个结点作为这条路径上的下一个结点。作为这条路径上的下一个结点。这条路径在以下结点处结束：或者它是一个这条路径在以下结点处结束：或者它是一个叶子叶子结点结点，或者该结点的，或者该结点的所有儿子结点都已被

13、限界所有儿子结点都已被限界。用这些用这些mi可以估算出这棵状态空间树中不受限界可以估算出这棵状态空间树中不受限界结点的总数结点的总数m。效率估计效率估计-估计满足估计满足Bi的的X(k)的数目的数目p蒙特卡罗方法蒙特卡罗方法优点：优点： 找到找到所有答案结点所有答案结点的情况非常有用，的情况非常有用， 限界函数固定不变限界函数固定不变，计算方便，对状态空间树中同一，计算方便，对状态空间树中同一级结点都适用。级结点都适用。缺点：缺点： 只求只求一个解一个解时，生成的结点数远小于时，生成的结点数远小于m， 随着检索的进行，限界函数应该更强，使得随着检索的进行，限界函数应该更强，使得m的值更的值更小

14、。小。 效率估计效率估计Procedure ESTIMATE /程序沿着状态空间树中一条随机路径产生这棵树中不受限界结点的估计数程序沿着状态空间树中一条随机路径产生这棵树中不受限界结点的估计数/ m 1; r 1; k 1 loop Tk X(k):X(k) T(X(1), ,X(k-1) ) and Bk (X(1), ,X(k-1) if SIZE(Tk)=0 then exit endif r r SIZE(Tk) m m+r X(k) CHOOSE(Tk) k k+1 repeat return(m)end ESTIMATE/第第k级的结点数级的结点数/从从Tk中随机地挑选一个元素中随

15、机地挑选一个元素/前第前第k级的结点总数级的结点总数返回集合返回集合Tk的大小的大小回溯法求解问题的基本步骤回溯法求解问题的基本步骤p 为所求问题定义解空间，使其包含所有为所求问题定义解空间，使其包含所有 解；解；p 确定适于搜索的解空间结构；确定适于搜索的解空间结构；p 用深度优先方法搜索该解空间，在搜索用深度优先方法搜索该解空间，在搜索 过程中利用限界函数避免无效搜索。过程中利用限界函数避免无效搜索。8.2 8-皇后问题皇后问题p问题描述及分析问题描述及分析p限界函数限界函数p求求n-皇后问题的所有解皇后问题的所有解p效率分析效率分析8.2 8-皇后问题皇后问题问题描述问题描述:在一个在一

16、个8*8棋盘上放置棋盘上放置8个皇后个皇后, 使得每两个皇后之间使得每两个皇后之间都不能互相都不能互相“攻击攻击”, 即每两个皇后都不能在同一行、即每两个皇后都不能在同一行、同一列及同一条斜角线上同一列及同一条斜角线上Q1Q2Q3Q4Q5Q6Q7Q88皇后问题可以表示皇后问题可以表示为为8- -元组元组(x1, , x8) ,其中其中xi是放置皇后是放置皇后i所所在的列号在的列号图中的可行解表示为图中的可行解表示为一个一个8- -元组元组即即(4, 6, 8, 2, 7, 1, 3, 5)a11a12a13a14a15a16a17a18a21a22a23a24a25a26a27a28a31a3

17、2a33a34a35a36a37a38a41a42a43a44a45a46a47a48a51a52a53a54a55a56a57a58a61A62a63a64a65a66a67a68a71a72a73a74a75a76a77a78a81a82a83a84a85a86a87a88用二维数组用二维数组A(1:8,1:8)的的下标来标记每个皇后的下标来标记每个皇后的位置，那么可以看到位置，那么可以看到: 对于在对于在由左到右由左到右的同一的同一条斜角线上的每个元素条斜角线上的每个元素具有具有相同的相同的“行行- -列列”值值;对于在对于在由右到左由右到左的同一的同一条斜角线上的每个元素条斜角线上的每

18、个元素则具有则具有相同的相同的“行行+列列”值值设有两个皇后被放置在设有两个皇后被放置在(i, j )和和(k, l )位置上位置上, 那么当且仅当那么当且仅当 i-j = k-l 或或 i+j = k+l 时时, 它们才在同一条斜角线上。它们才在同一条斜角线上。将这两个等式分别变换成将这两个等式分别变换成: j-l = i-k 或或 j-l = k-i因此当且仅当因此当且仅当 |j-l| = |i-k| 时时( 即两个皇后所在位置的行差距即两个皇后所在位置的行差距等于列差距时等于列差距时), 两个皇后在同一条斜角线上两个皇后在同一条斜角线上限界函数限界函数pPLACE(k)： 令令X(k)与

19、与X(i)逐个逐个比较，比较，i=1.k-1。 若存在若存在X(k)=X(i)或者或者|X(i)-X(k)|=|i-k| 则返回则返回false； 否则返回否则返回true。对对X(k)的限定的限定procedure PLACE(k)int i , k;i1;while ( i0) do X(k)X(k)+1; while ( X(k) n and Not PLACE(k) ) do X(k)X(k)+1; repeat if (X(k) n) then if (k=n) then print (X); else kk+1; X(k)0; endif else kk-1; endifrepea

20、tend NQUEENS/若是一个完整的解则打印数组若是一个完整的解则打印数组X/ k是当前行是当前行; X(k)是当前列是当前列 / 对所有的行执行循环语句对所有的行执行循环语句/移到下一列移到下一列当该位置不当该位置不能放皇后时能放皇后时转到下一列转到下一列/找到一个位置找到一个位置/否则转到下一行否则转到下一行/ 没有合适的位置没有合适的位置, 回溯回溯1234X001Q1PLACE(1)i=1;while ( ik ) do 10) do X(k)=X(k)+1; while (X(k) n and Not PLACE(k) do1 n and Not true , 循环不执行循环不执

21、行if (X(k) n) then if (kn) then 不执行不执行 else k=k+1=2; X(2)=0; end whilek=2; while (k0) do X(k)=X(k)+1; while ( X(k) n and Not PLACE(k) ) do1 n and Not false , X(k)=X(k)+1=2; 2 n and Not false , X(k)=X(k)+1=3; 3 n and Not true , 循环不执行循环不执行1 2 3if (X(k) n) then if (kn) then 不执行不执行 else k=k+1=3; X(3)=0;

22、0 end whileQ2PLACE(2)i=1;while ( ik ) do if (X(i)=X(k) then return (false);PLACE(2)i=1;while ( ik ) do if (|X(i)- -X(k)|=|i- -k|) then return (false);PLACE(2)i=1;while ( i0) do X(k)=X(k)+1; while (X(k) n and Not PLACE(k) doif (X(k) n) then 不执行不执行 else k=k- -1=2; /回溯回溯 end whilek=2; while (k0) do X(k

23、)=X(k)+1=3+1=4; while ( X(k) n and Not PLACE(k) ) do1 n and Not false , X(k)=X(k)+1=2; 2 n and Not false , X(k)=X(k)+1=3; 4 n and Not true , 循环不执行循环不执行if (X(k) n) then if (kn) then 不执行不执行 else k=k+1=3; X(3)=0; end whileQ213 n and Not false , X(k)=X(k)+1=4; 4 n and Not false , X(k)=X(k)+1=5; 2 3 4 54

24、05 n , 循环不执行循环不执行1234X140Q1Q2k=3; while (k0) do X(k)=X(k)+1; while (X(k) n and Not PLACE(k) doif (X(k)0) do X(k)=X(k)+1=1; while ( X(k) n and Not PLACE(k) ) do1 n and Not false , X(k)=X(k)+1=2; 2 n and Not true , 循环不执行循环不执行; end whileQ21 20Q31 n and Not false , X(k)=X(k)+1=2; 1 2 32 n and Not true ,

25、 X(k)=X(k)+1=3; 43 n and Not true , X(k)=X(k)+1=4; 54 n and Not true , X(k)=X(k)+1=5;5 n , 循环不执行循环不执行if (X(k) n) then 不执行不执行 else k=k- -1=3; /回溯回溯 1234X142Q1k=3; while (k0) do X(k)=X(k)+1; while (X(k) n and Not PLACE(k) doif (X(k) n) then 不执行不执行 else k=k- -1=2; /回溯回溯 end whilek=2; while (k0) do X(k)

26、=X(k)+1=4+1=5; while ( X(k) n and Not PLACE(k) ) do end whileQ23 n and Not false , X(k)=X(k)+1=4; 4 n and Not false , X(k)=X(k)+1=5; 3 4 55 n , 循环不执行循环不执行55 n , 循环不执行循环不执行if (X(k) n) then 不执行不执行 else k=k- -1=1; /回溯回溯 1234X1Q2k=1; while (k0) do X(k)=X(k)+1; while (X(k) n and Not PLACE(k) do end while

27、k=2; while (k0) do X(k)=X(k)+1; while ( X(k) n and Not PLACE(k) ) do2 n and Not true , 循环不执行循环不执行; 1 n and Not false , X(k)=X(k)+1;if (X(k) n) then if (kn) then 不执行不执行 else k=k+1=3; X(3)=0; end whileif (X(k) n) then if (kn) then 不执行不执行 else k=k+1=2; X(2)=0; 2 n and Not false , X(k)=X(k)+1;3 n and Not false , X(k)=X(k)+1;4 n and Not true , 循环不执行循环不执行;20Q1Q21 2 3 41234X240Q1Q2k