Lecture9-Backtracking-复件

1、 Analysis and Design of Computer Algorithms 中南大学信息科学与工程学院中南大学信息科学与工程学院School of Information Science and EngineeringCentral South University主讲：李敏主讲：李敏联系方式：联系方式： 2回溯法回溯法(Backtracking)n有有“通用的解题法通用的解题法”之称。之称。n回溯法的基本做法是回溯法的基本做法是搜索搜索，或是一种组织得井井有条，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适的，能避免不必要搜索的穷举式搜索法。这种方法适用于解

2、一些组合数相当大的问题。用于解一些组合数相当大的问题。回溯法指导思想回溯法指导思想走不通，就掉头。走不通，就掉头。 3n回溯法在问题的解空间树中，按回溯法在问题的解空间树中，按深度优先深度优先策略，从根策略，从根结点出发搜索解空间树。结点出发搜索解空间树。n算法搜索至解空间树的任意一点时，先判断该结点是算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。否包含问题的解。n如果肯定不包含，则跳过对该结点为根的子树的搜索，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；逐层向其祖先结点回溯；n否则，进入该子树，继续按深度优先策略搜索。否则，进入该子树，继续按深度优先

3、策略搜索。回溯法的基本思想回溯法的基本思想回溯法指导思想回溯法指导思想走不通，就掉头。走不通，就掉头。 Review: Depth-First Searcho The idean traverse “deeper” whenever possible. n On each iteration, the algorithm proceeds to an unvisited vertex that is adjacent to the one it is currently in.n When reaching a dead end ( a vertex with no adjacent unvi

4、sited vertices), the algorithm backs up to the parent and tries to continue visiting unvisited vertices from there.n The algorithm halts after backing up to the starting vertex, with it being a dead end.42022-2-285DFS Examplesourcevertex2022-2-286DFS Example1 | | | | | | | | sourcevertexd f2022-2-28

5、7DFS Example1 | | | | | | 2 | | sourcevertexd f2022-2-288DFS Example1 | | | | | 3 | 2 | | sourcevertexd f2022-2-289DFS Example1 | | | | | 3 | 42 | | sourcevertexd f2022-2-2810DFS Example1 | | | | 5 | 3 | 42 | | sourcevertexd f2022-2-2811DFS Example1 | | | | 5 | 63 | 42 | | sourcevertexd f2022-2-2812

6、DFS Example1 | | | | 5 | 63 | 42 | 7 | sourcevertexd f2022-2-2813DFS Example1 | 8 | | | 5 | 63 | 42 | 7 | sourcevertexd f2022-2-2814DFS Example1 | 8 | | | 5 | 63 | 42 | 7 | sourcevertexd f2022-2-2815DFS Example1 | 8 | | | 5 | 63 | 42 | 79 | sourcevertexd f2022-2-2816DFS Example1 | 8 | | | 5 | 63 | 4

7、2 | 79 |10sourcevertexd f2022-2-2817DFS Example1 | 8 |11 | | 5 | 63 | 42 | 79 |10sourcevertexd f2022-2-2818DFS Example1 |128 |11 | | 5 | 63 | 42 | 79 |10sourcevertexd f2022-2-2819DFS Example1 |128 |1113| | 5 | 63 | 42 | 79 |10sourcevertexd f2022-2-2820DFS Example1 |128 |1113| 14| 5 | 63 | 42 | 79 |1

8、0sourcevertexd f2022-2-2821DFS Example1 |128 |1113| 14|155 | 63 | 42 | 79 |10sourcevertexd f2022-2-2822DFS Example1 |128 |1113|1614|155 | 63 | 42 | 79 |10sourcevertexd f2022-2-2823Depth-First Search: The CodeDFS(G) for each vertex u u.color = WHITE; time = 0; for each vertex u if (u.color = WHITE) D

9、FS_Visit(u); DFS_Visit(u) u.color = GREY; time = time+1; du = time; for each v u.Adj if (v.color = WHITE) DFS_Visit(v); u.color = BLACK; time = time+1; fu = time; 回溯法回溯法n回溯法在问题的解空间树中，按回溯法在问题的解空间树中，按深度优先深度优先策略，从根策略，从根结点出发搜索结点出发搜索解空间树解空间树。n算法搜索至解空间树的任意一点时，先判断该结点是算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。否包含问题的解。

10、n如果肯定不包含，则跳过对该结点为根的子树的搜索，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；逐层向其祖先结点回溯；n否则，进入该子树，继续按深度优先策略搜索。否则，进入该子树，继续按深度优先策略搜索。n直到根结点的所有子树都已被搜索。直到根结点的所有子树都已被搜索。2425回溯算法设计过程回溯算法设计过程o step1 确定问题的解空间；确定问题的解空间；o step2 确定结点的扩展规则；确定结点的扩展规则；o step3 搜索解空间搜索解空间。o 求问题所有解：要回溯到根，且根结点的所有子树求问题所有解：要回溯到根，且根结点的所有子树都已被搜索遍才结束。都已被搜

11、索遍才结束。o 求任一解：只要搜索到问题的一个解就可结束。求任一解：只要搜索到问题的一个解就可结束。 回溯法回溯法Solution space of problem How to construct the solution space of given problem? For example: for 0/1 knapsack problem with n items Its solution space: 0-1 vector of length n. n=3, its solution space is:(0,0,0),(0,1,0),(1,0,0),(0,1,1),(1,0,1),(

12、1,1,0),(1,1,1) How to organize those solutions in solution space?Binary Tree26Solution space of problemEach path from root to leaf denotes a solution of the problem.ABDHIEJKCFLMGNO1110010001101027Basic idea of BacktrackingBased on the given structure of solution space, from the root node, backtracki

13、ng algorithm searches optimal solution in solution space by the method like Depth-First way. The start point is called a “live node”, also as a “extension node”(the current working node). For an “extension node”, the backtracking algorithm moves to the next deeper new node. Then, the new node become

14、s a “live node”, also becomes an “extension node”.28Basic idea of BacktrackingIf the current “extension node” could not move any longer, then it becomes a “dead node”. Then, the backtrack algorithm moves back to the nearest “live node”, and let this node be an “extension node”.When there is no “live

15、 node” in the solution space, a solution is found.When the algorithm works at an “extension node”, decide whether the subtree rooted at this “extension node” contains a solution of problem. If the subtree contains no solution of problem, do not search this subtree, move back, until an unvisited node

16、 is found, then do the search.29oExample: 0/1 knapsack problem with n=3, W=16,15,15, P=45,25,25,M=30.oAt first, A is a “live node”, and also an “extension node”, then move deeper to B, B to D, D is a “dead node”( why?)ABDHIEJKCFLMGNO1110010001101030oMove back to the nearest “live node” B, extend to

17、E(E is a “live node” now, until J. oJ is a “dead node”, then returns to E, and extends to K (feasible solution with value 45).o Move back to E. E could not be extended any more, and becomes a “dead node”. ABDHIEJKCFLMGNO1110010001101031oMove back to B, and B becomes a “dead node”.oMove back to A, an

18、d extends to C (“live node”), until F, L.ABDHIEJKCFLMGNO1110010001101032Basic steps using Backtracking（1）Based on the problem given, define solution space of problem.（2）Define the structure of the solution space, and organize it in specific data structure( Tree). （3）search solution space by depth-fi

19、rst method, and use constraint function to avoid useless search. 33n-queen problemn皇后问题皇后问题:要在要在n*n的国际象棋棋盘中放的国际象棋棋盘中放n个皇后，使任意两个皇后都不能互相吃个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。求所有的解。同一对角线的任意棋子。求所有的解。How to solve it?lsystematically generate every possible arrangementltest each

20、one to see if it is a valid solution34n-queen problemif we were smart, we could greatly reduce the search spacel e.g., any board arrangement with a queen at (1,1) and (2,1) is invalidl no point in looking at the other queens, so can eliminate 12 boards from considerationif a choice does not lead to

21、a solution, back up and try an alternative358-queen problem36o设八个皇后为设八个皇后为xi，分别在第，分别在第i行行(i=1，2，3，4，8)；o问题的解状态问题的解状态：可以用：可以用(1,x1)，(2,x2)，(8,x8)表示表示8个皇后个皇后的位置；的位置；n由于行号固定，可简单记为：由于行号固定，可简单记为：(x1,x2,x3,x4,x5,x6,x7,x8)；o问题的解空间问题的解空间：(x1,x2,x3,x4,x5,x6,x7,x8)，1xi8(i=1，2，3，4，8)，共，共88个状态；个状态；o约束条件约束条件：八个：

22、八个(1,x1),(2,x2) ,(3,x3),(4,x4) ,(5,x5), (6,x6) , (7,x7), (8,x8)不在同一行、同一列和同一对角线上。不在同一行、同一列和同一对角线上。n原问题即：在解空间中原问题即：在解空间中寻找符合约束条件寻找符合约束条件的解状态。的解状态。n按什么顺序去搜？按什么顺序去搜？q目标是没有漏网之鱼，尽量速度快。目标是没有漏网之鱼，尽量速度快。378-queen problemo a 盲目的枚举算法盲目的枚举算法n通过通过8重循环模拟搜索空间中的重循环模拟搜索空间中的88个状态；个状态；n按按枚举思想枚举思想，以以DFS的方式的方式，从第，从第1个皇后

23、在第个皇后在第1列开始列开始搜索，枚举出所有的搜索，枚举出所有的“解状态解状态”：o 从中找出满足约束条件的从中找出满足约束条件的“答案状态答案状态”。q违规的情况可以整合改写为：违规的情况可以整合改写为：nabs(xi - xj)=abs( i-j ) or (xi = xj)枚举得有个顺序，否则枚举得有个顺序，否则轻则有漏的、重复的；轻则有漏的、重复的；重则无法循环表示。重则无法循环表示。n约束条件？约束条件？q不在同一列：不在同一列：xixj；q不在同一主对角线上：不在同一主对角线上：xi-i xj-j；q不在同一负对角线上：不在同一负对角线上：xi+i xj+j。38a 盲目的枚举算法

24、盲目的枚举算法queen1( ) int a9; for (a1=1;a1=8;a1+) for (a2=1;a2=8;a2+) for (a3=1;a3=8;a3+) for (a4=1;a4=8;a4+) for (a5=1;a5=8;a5+) for (a6=1;a6=8;a6+) for(a7=1;a7=8;a7+) for(a8=1;a8=8;a8+)if (check(a,8)=0) continue; else for(i=1;i=8;i+) print(ai); check(a,n)int i,j; for (i=2;i=n;i+) for(j=1;j=i-1;j+) if (

25、ai=aj) or (abs(ai-aj)=abs(i-j) return(0); return(1); 双重循环，任意两个皇双重循环，任意两个皇后之间都必须检查。后之间都必须检查。用用a1a8存储存储x1x839b加约束的枚举算法加约束的枚举算法o 如果能够排除那些没有前途的状态，会节约时间；如果能够排除那些没有前途的状态，会节约时间；n如何提前发现？如何提前发现？回溯法指导思想回溯法指导思想走不通，就掉头走不通，就掉头 n这种状态扩展后会产生这种状态扩展后会产生86个结点；个结点；q同样的同样的(1,2, x3,x4,x5,x6,x7,x8)，也应被排除。也应被排除。q在每一次扩展在每一次

26、扩展E结点后，都进行检查；结点后，都进行检查；n对检查结果如何处理？对检查结果如何处理？q检查合格的才继续向下扩展；检查合格的才继续向下扩展；q遇到不合格的遇到不合格的“掉头就走掉头就走”。q如如(1,1, x3,x4,x5,x6,x7,x8)没有必要再扩展；没有必要再扩展；40b加约束的枚举算法加约束的枚举算法41b加约束的枚举算法加约束的枚举算法queen1( )int a9; for (a1=1;a1=8;a1+) for (a2=1;a2=8;a2+) if ( check(a,2)=0 ) continue; for (a3=1;a3=8;a3+) if (check(a,7)=0)

27、 continue; for(a8=1;a8=8;a8+) if (check(a,8)=0)continue; else for(i=1;i=8;i+) print(ai); o 此算法可读性很好，此算法可读性很好，体现了体现了“回溯回溯”。但它只能解决八皇但它只能解决八皇后问题，而不能解后问题，而不能解决任意的决任意的n皇后问皇后问题。题。check2 (int a ,int n)/多次被调用，只是一重循环多次被调用，只是一重循环 int i; for(i=1;in) 找到一个解输出结果找到一个解输出结果; else for (int i = 1;i n) 输出结果输出结果; else f

28、or(j=下界下界 ; j0 ) ak=ak+1; while (ak=n) and (check(a,k)=0) /搜索第搜索第k个皇后位置个皇后位置 ak=ak+1; if（ ak0(有路可走有路可走) and (未达到目标未达到目标) /还未回溯到头还未回溯到头 if (i=n) 搜索到一个解，输出搜索到一个解，输出; /搜索到叶结点搜索到叶结点 else /正在处理第正在处理第i个元素个元素 ai第一个可能的值；第一个可能的值； while (ai不满足约束条件且在搜索空间内不满足约束条件且在搜索空间内) ai下一个可能的值；下一个可能的值； if (ai在搜索空间内在搜索空间内) 标

29、识占用的资源标识占用的资源; i=i+1; /扩展下一个结点扩展下一个结点 else 清理所占的状态空间；清理所占的状态空间；i=i-1; /回溯回溯 46算法说明算法说明o 八皇后问题中的核心代码：八皇后问题中的核心代码：n 遍历过程函数；遍历过程函数；n check函数。函数。n解决此类问题的核心内容：解决此类问题的核心内容：q解空间树的搜索算法；解空间树的搜索算法；q估值估值/判断函数：判断哪些状态适合继续扩展，或者作判断函数：判断哪些状态适合继续扩展，或者作为答案状态。为答案状态。策略：能进则进，不能进则换，不能换则退。策略：能进则进，不能进则换，不能换则退。 47再说递归-函数调用m

30、ain() f1(); codeA; f2(x);/传入传入x=9f1() codeB; f3(); codeC;f2(a) if(a=8) codeD;f3() codeE;main() codeB; codeE; codeC; codeA;codeB;f3();codeC;codeE;o 调用、返回n 谁调用，返回谁；n 返回后，执行下一句代码；o 参数传递n 传值、传址；48再说递归- n皇后问题backtrack(int k)if (k = n)for (int i = 1;i =n; i+)ak = i;if (check(k) backtrack(k+1);if (!check(k

31、)& ak=8) ak = 0; 递归两要素递归两要素递归关系递归关系递归边界递归边界(终止条件终止条件)49搜索代价o对于对于4Queen，若每个分支都是，若每个分支都是“一分为四一分为四”，则：，则：n0个皇后的状态：个皇后的状态：1个，即个，即40；n1个皇后的状态：个皇后的状态：4个，即个，即41；n2个皇后的状态：个皇后的状态：16个，即个，即42；n3个皇后的状态：个皇后的状态：64个，即个，即43；n4个皇后的状态：个皇后的状态：256个，即个，即44；n共共341个状态。个状态。n使用回溯策略，实际扫描过的状态如图：共使用回溯策略，实际扫描过的状态如图：共16个，仅占个

32、，仅占5%50搜索代价-排列树o对于对于4Queen，其实可以不让每个分支都，其实可以不让每个分支都“一分为四一分为四”；n如图，当第如图，当第1行皇后处于第行皇后处于第1列时，第列时，第2行的皇后选择范围可以行的皇后选择范围可以缩小为缩小为(24)，而非，而非(14)；n同样的，当第同样的，当第2行的皇后选择第行的皇后选择第2列时，第列时，第3行的皇后选择范围行的皇后选择范围可以缩小为可以缩小为(34)。n如果据此原则，状态空间中：如果据此原则，状态空间中：q0个皇后的状态：个皇后的状态：1个，即个，即P40；q1个皇后的状态：个皇后的状态：4个，即个，即P41；q2个皇后的状态：个皇后的状

33、态：12个，即个，即P42；q3个皇后的状态：个皇后的状态：24个，即个，即P43；q4个皇后的状态：个皇后的状态：24个，即个，即P44；q共共65个状态。个状态。51搜索代价o“剪枝剪枝”通过对状态通过对状态“估值估值”(包括检查是否符合约束条件包括检查是否符合约束条件)，判，判断状态是否需要继续扩展；断状态是否需要继续扩展；n估值估值&检查机制检查机制q好的机制能显著地减少所生成的结点数；好的机制能显著地减少所生成的结点数；q但往往计算量大；但往往计算量大；q折衷问题：折衷问题：“剪枝剪枝”节约的节约的 vs.估值检查机制消耗的。估值检查机制消耗的。n回溯算法的效率很大程度上依赖

34、于以下因素：回溯算法的效率很大程度上依赖于以下因素：q产生一个产生一个xk的时间；的时间；q过程中经过检查的过程中经过检查的xk的个数；的个数；q计算估值计算估值(约束约束)函数的时间代价。函数的时间代价。52搜索代价-空间代价o 如果要把整个树存储下来的话，那空间代价是惊人的；o 在回溯算法中，并不需要真正创建一个空间树；o 树的深度优先搜索策略的空间代价一般为最长路径的长度。53算法思路算法思路 利用之前利用之前“枚举枚举”所有所有1-n的排列，从中选出满足约的排列，从中选出满足约束条件的解来。这时约束条件只有不在同一对角线，而束条件的解来。这时约束条件只有不在同一对角线，而不需要不同列的

35、约束了。共有不需要不同列的约束了。共有2n-1=7个主对角线，对应个主对角线，对应地也有地也有7个负对角线。个负对角线。 八皇后问题-排列树搜索法54o 给定给定n种物品和一背包。物品种物品和一背包。物品i的重量是的重量是wi，其价值为，其价值为vi，背包的容量为背包的容量为C。问应如何选择装入背包的物品，使得。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大装入背包中物品的总价值最大?o 0-1背包问题也是一个子集选取问题。背包问题也是一个子集选取问题。niiixv1maxnixCxwiniii1,1 ,01再看再看0-1背包问题背包问题解空间：子集树解空间：子集树5511cxwniii约束条件？约束条件？ 再看再看0-1背包问题背包问题如何扩展？如何扩展？ 仅当仅当Cwwi C时进入左子树，递归搜索左子树；可行结点的右子树总是时进入左子树，递归搜索左子树；可行结点的右子树总是可行的。可行的。是否可以剪枝？剪去不含最