算法设计技巧与分析课件(英文版)：ch13 Backtracking

1、Algorithms Design Techniques and Analysis,Chapter 13,Backtracking An Efficient Searching Algorithm,Algorithms Design Techniques and Analysis,What we have known after previous learning,A subclass of intractable problems have been studied, commonly referred to as the class of NP-complete problems. The

2、 Class P The Class NP NP-Complete Problems The Class co-NP The Class NPI,Algorithms Design Techniques and Analysis,Coping with hardness,Three useful methodologies: One, Suitable for those problems that exhibit good average time complexity, but for which the worst case polynomial time solution is exc

3、lusive. This methodology is based on a methodic examination of the implicit state space induced by the problem instance under study. In the process of exploring the state space of the instance, some pruning takes place. Two, based on the probabilistic notion of accuracy. Three, useful for incrementa

4、l solutions where one is willing to compromise on the quality of solution in return for faster (polynomial time) solutions.,Algorithms Design Techniques and Analysis,Contents of current chapter,Backtracking. The 3-coloring problem The 8-queens problem The general backtracking method Sub of sub set p

5、roblem Hamilton cycle problem Branch and bound TSP problem,Algorithms Design Techniques and Analysis,13.1 Introduction,In many real world problems, as in most of the problems NP-hard problems, a solution can be obtained by exhaustively searching through a large but finite number of possibilities Mor

6、eover, for virtually all these problems, there does not exist an algorithm that uses a method other than exhaustive search,How to develop systematic techniques of searching?,And how to cut down the search space to possibly a much smaller space?,Algorithms Design Techniques and Analysis,回溯法,问题要求: (1)

7、所要求的解必须能表示成一个n-元组(x1,x2,xn),其中xi是取自某个有穷集Si. 通常,所求解的问题需要求取一个使某一个规范函数P(x1,x2,xn)取极值或满足规范条件的向量,有时还要找出满足P的所有向量. (2)许多问题还要求所有的解满足一组综合的约束条件,这些条件分两种类型:显式约束和隐式约束. 显式约束限定每个x只从一个给定的集合上取值,满足显式约束的所有元组确定一个可能的解空间; 隐式约束规定解空间中那些实际上满足规范函数的元组,因此,描述了xi必须彼此相关的情况.,Algorithms Design Techniques and Analysis,回溯法,问题的求解方法： 假

8、定集合Si的大小为mi，于是就有m= m1m2 mn个n-元组可能满足函数P。 问题的硬性处理求解方法： 构造出m个n-元组并逐一测试它们是否满足P，从而找出该问题的所有最优解。 问题的回溯处理求解方法： 不断地用修改过的规范函数Pi(x1,x2,xn)（有时称为限界函数）去测试正在构造中的n-元组的部分向量(x1,x2,xi),看其是否可能导致（最优）解。如果判定(x1,x2,xi)不可能导致（最优）解，那么就将可能要测试的mi+1mi+2 mn个向量一概略去。 回溯法比硬性处理作的测试（m次）要少得多。,Algorithms Design Techniques and Analysis,问

9、题举例,8皇后问题：在一个88的棋盘上放8个皇后，且使得每两个之间都不能互相“攻击”，即都不出现在同一行、同一列及同一条斜对角线上。 解的表示：假定第i个皇后放在第i行，用8元组(x1,x2,x8)表示解，其中xi示放置皇后i的列号。 显示约束:Si=(1,2,3,8),1i8 隐示约束：没有两个xi(1i8)可以相同（在不同的列上），且没有两个皇后在同一斜对角线上。,Algorithms Design Techniques and Analysis,问题举例,子集和数问题：已知n+1个正整数：w1,w2,wn和M，要求找出wi的和数等于M的所有子集。 解的表示1：用其和数为M的wi的下标来表

10、示解向量。则可以用k-元组(x1,x2,xk)来表示解,1kn。不同的解可以是大小不同的元组。 显示约束：xij|j是一个整数且1 jn . 隐示约束：没有两个xi是相同的且对应的wi的和数是M；为避免子集重复，要求xixi+1, 1in.,Algorithms Design Techniques and Analysis,问题举例,子集和数问题：已知n+1个正整数：w1,w2,wn和M，要求找出wi的和数示M的所有子集。 解的表示2：用n-元组(x1,x2,xn)来表示解, xi0,1 ,1in。如果没有选择wi，则xi0，否则xi1。解是大小相同的元组。 显示约束：xi0，1 . 隐示约束

11、：为1的xi对应的wi的和数是M.,Algorithms Design Techniques and Analysis,解空间树结构,树中的每个结点确定所求解问题的一个问题状态. 由根结点到其它结点的所有路径确定了这个问题的状态空间. 解状态是这样一些问题状态S,对于这些问题状态,由根到S的那条路径确定了这解空间中的一个元组. 答案状态是这样的一些解状态S,对于这些解状态而言,由根到S的这条路径确定了这问题的一个解. 解空间的树结构成为状态空间树.,Algorithms Design Techniques and Analysis,状态空间树=问题解,对于任何一个问题,一旦设想出一种状态空间树

12、,就可以系统地生成问题状态,接着确定这些问题状态中的哪些状态是解状态,最后确定哪些解状态是答案状态,从而将问题解出. 问题状态的生成: 从根结点开始生成其它结点. 活结点: 如果已生成一个结点而它的儿子结点还没有全部生成,则这个结点叫做活结点;当前正在生成其儿子结点的活结点叫E-结点(正在扩展的结点). 死结点:不再进一步扩展或者其儿子结点已经全部生成的生成结点是死结点.,Algorithms Design Techniques and Analysis,问题状态的生成方法,回溯法:当前的E-结点R一旦生成一个新的儿子C,这个儿子结点就变成一个新的E-结点,当完全检测了子树C之后,R结点就再次

13、成为E-结点. 使用限界函数的深度优先结点生成方法称为回溯法. 分枝-限界法:一个E-结点一直保持到变成死结点为止.(队列方法, 栈方法) 两种方法都用限界函数去杀死还没有全部生成儿子结点的那些活结点. This algorithm design technique can be described as an organized exhaustive search which often avoids searching all possibilities,Algorithms Design Techniques and Analysis,解空间树结构例,4皇后问题 解不定长表示的子集和数问

14、题 解定长表示的子集和数问题,Algorithms Design Techniques and Analysis,13.2 The 3-Coloring Problem,Problem description Given an undirected graph G=(V,E), it is required to color each vertex in V with one of three colors, say 1,2, and 3, such that no two adjacent vertices have the same color. A coloring can be rep

15、resented by an n-tuple （c1, c2, , cn）such that ci1, 2, 3, 1in For example,(1,2,2,3,1) denotes a coloring of a graph with five verticesThere are 3n possible colorings（legal and illegal）to color a graph with n vertices.,Algorithms Design Techniques and Analysis,Search Tree,The set of all possible colo

16、rings can be represented by a complete ternary tree called the search treeEach path from the root to a leaf node represents one coloring assignment.,Algorithms Design Techniques and Analysis,The search tree for all possible 3-colorings for a graph with 3 vertices,Algorithms Design Techniques and Ana

17、lysis,Backtracking: Partial Coloring Scheme,Partial: An incomplete coloring of a graph is partial if no two adjacent colored vertices have the same color. Idea: Backtracking works by generating the underlying tree one node at a time. If the length of the path from the root to the current node is les

18、s than n and the corresponding coloring is partial, then one child of the current node is generated and is marked as the current node. If, on the other hand, the corresponding path is not partial, then the current node is marked as a dead node and a new node corresponding to another color is generat

19、ed. If, however, all three colors have been tried with no success, the search backtracks to the parent node whose color is changed, and so on.,Algorithms Design Techniques and Analysis,An example,a,b,c,d,e,a=1,b=1,b=2,c=1,c=2,d=1,e=1,e=2,e=3,Find a solution!,Algorithms Design Techniques and Analysis

20、,Observations,We have arrived at the solution after generating only 10 nodes out of the 364 nodes comprising the search tree. The nodes are generated in a depth-first-search manner. There is no need to store the whole search tree; we only need to store the path from the root to the current active no

21、de. In fact, no physical nodes are generated at all; the whole tree is implicit. In above example, we only need to keep track of the color assignment.,Algorithms Design Techniques and Analysis,Algorithm 13.1 3-COLORREC Input: An undirected graph G=(V,E). Output: A 3-coloring c1.n of the vertices of

22、G, where each cj is 1,2 or 3. 1. for k1 to n 2. ck0 3. end for 4. flagfalse 5. graphcolor(1) 6. if flag then output c 7. else output “no solution” Procedure graphcolor(k) 1. for color=1 to 3 2. ckcolor 3. if c is a legal coloring then set flagtrue and exit 4. else if c is partial then graphcolor(k+1

23、) 5. end for,Algorithms Design Techniques and Analysis,Algorithm 13.2 3-COLORITER Input: An undirected graph G=(V,E). Output: A 3-coloring c1.n of the vertices of G, where each cj is 1,2 or 3. 1. for k1 to n 2.ck0 3. end for 4. flagfalse 5. k1 6. while k 1 7. while ck 2 8.ckck+1 9.if c is a legal co

24、loring then set flagtrue and exit from the two while loops 10. else if c is partial then kk+1 advance 11. end while 12. ck0 13. kk-1 14. end while 15. if flag then output c 16 else output “no solution”,Algorithms Design Techniques and Analysis,Algorithm analysis,As to the time complexity of these tw

25、o algorithms, we note that O(3n) nodes are generated in the worst case. For each generated node, O(n) work is required to check if the current coloring is legal, partial, or neither. Hence, the overall running time is O(n3n) in the worst case. The space complexity is (n).,Algorithms Design Technique

26、s and Analysis,13.3 The n-Queens Problem,n-Queens Problem description How can we arrange n queens on an nn chessboard (n 1) so that no two queens can attack each other? Two queens can attack each other if they are in the same row, column or diagonal.,Algorithms Design Techniques and Analysis,The 4-Q

27、ueens Problem,For the 4-queens problem, since no two queens can be placed in the same row, each queen is in a different row. Since there are four positions in each row, there are 44 possible configurations. Each possible configuration can be described by a vector with four components x= (x1,x2,x3,x4

28、). In fact, since no two queens can be placed in the same column, a legal placement corresponds to a permutation of the numbers 1, 2, 3 and 4. This reduces the search space from 44 to 4!.,Algorithms Design Techniques and Analysis,An example,The vector (2,3,4,1),The partial vector (3,1),Algorithms De

29、sign Techniques and Analysis,Attack Each Other,Suppose: the solution is represented by (x1,xn). Since each row place one queen, two queen can not place in the same row; If two queens i and j are placed in the same column, they attack each other. In this case, xi=xj; If two queens i and j are placed

30、in the same diagonal, they attack each other. In this case, xi-xj=i-j or xi-xj=j-i.,Algorithms Design Techniques and Analysis,Algorithm 13.3 4-QUEENS(iterative) Input: none. Output: A vector x1.4 corresponding to the solution of the 4-queens problem. 1.for k1 to 4 2.xk0 no queens are placed on the c

31、hessboard 3.end for 4.flagfalse 5.k1 6. while k 1 7. while xk 3 8. xkxk+1 9. if x is a legal placement then set flagtrueand exit from the two while loops 10.else if x is partial then kk+1 advance 11. end while 12. xk0 13. kk-1 14. end while 15. if flag then output x 16. else output “no solution”,Alg

32、orithms Design Techniques and Analysis,An example: 4-Queens Problem,1,X,X,2,X,X,X,X,1,2,X,3,X,X,X,X,1,X,X,X,2,3,X,X,4,1,2,X,X,Find a solution!,Algorithms Design Techniques and Analysis,Algorithm analysis,Now, consider a brute-force method to solve the general n-queens problem. Since no two queens ca

33、n be placed in the same column, the solution vector must be a permutation of the numbers 1,2,n. Thus, the brute-force method can be improved to test n! configurations instead of nn. Consider the (n-2)! Vectors corresponding to those configurations in which the first two queens are placed in the firs

34、t column.The brute-force method blindly tests all these vectors, whereas in backtracking method to solve the n-queens problem costs O(nn) in the worst case, it empirically far exceeds the O(n!) brute-force method in efficiency, as its expected running time is generally much faster.,Algorithms Design

35、 Techniques and Analysis,13.4 The general backtracking method,Representation of solution The general backtracking algorithm as a systematic search method can be applied to a class of search problems whose solution consists of a vector (x1, x2, . . . , xi) satisfying some predefined constraints. Here

36、 i is some integer between 0 and n, where n is a constant that is dependent on the problem formulation. In the two algorithms we have covered, 3-COLORING and the n-QUEENs problems, i was fixed. However, in some problems i may vary from one solution to another.,Algorithms Design Techniques and Analys

37、is,Example: fixed and variable length of solution,Given a set of n integers X = x1,x2,.,xn and an integer y, find a subset Y of X whose sum is equal to y. For instance if X = 10,20,30,40,80,60 and y = 60 Variable length of solution: Three solutions of different lengths 10,20,30 20,40 60 Fixed length

38、 of solution: The solution is a Boolean vector of length n in the obvious way. 1,1,1,0,0,0 0,1,0,1,0,0 0,0,0,0,0,l.,Algorithms Design Techniques and Analysis,Basic idea of backtracking,In backtracking, each xi in the solution vector belongs to a finite linearly ordered set Xi. Thus, the backtracking

39、 algorithm considers the elements of the cartesian product X1X2 Xn in lexicographic order. Initially, the algorithm starts with the empty vector. It then chooses the least element of X1 as x1. If (x1) is a partial solution, the algorithm proceeds by choosing the least element of X2 as x2. If (x1,x2)

40、 is a partial solution, then the least element of X3 is included; otherwise x2 is set to the next element in X2. In general, suppose that the algorithm has detected the partial solution (x1,x2,xj). It then considers the vector v=(x1,x2,xj,xj+1).,Algorithms Design Techniques and Analysis,Basic idea o

41、f backtracking (continue),If v represents a final solution to the problem, the algorithm records it as a solution and either terminates in case only one solution is desired or continues to find other solutions. (The advance step). If v represents a partial solution, the algorithm advanced by choosin

42、g the least element in the set Xj+2. If v is neither a final nor a partial solution, we have two subcases: If there are still more elements to choose from in the set Xj+1 , the algorithm sets xj+1 to the next member of Xj+1. (The backtrack step). If there are no more elements to choose from in the s

43、et Xj+1, the algorithm backtracks by setting xj to the next member of Xj. If again there are no more elements to choose from in the set of Xj, the algorithm backtracks by setting Xj-1 to the next member of Xj-1, and so on.,Algorithms Design Techniques and Analysis,Algorithm 13.4 BACKTRACKREC Input:

44、Explicit or implicit description of the sets X1,X2,Xn. Output: A solution vector v=(x1,x2,xi), 0 i n. 1.v() 2.flagfalse 3.advance(1) 4.if flag then output v 5.else output “no solution” Procedure advance(k) 1.for each x Xk 2.xkx; append xk to v 3.if v is a final solution then set flagtrue and exit 4.

45、else if v is partial then advance(k+1) 5. end for,Algorithms Design Techniques and Analysis,Algorithm 13.5 BACKTRACKITER Input: Explicit or implicit description of the sets X1,X2,Xn. Output: A solution vector v=(x1,x2,xi), 0 i n. 1.v() 2.flagfalse 3.k1 4.while k 1 5.while Xk is not exhausted 6.xknex

46、t element in Xk; append xk to v 7.if v is final solution then set flagtrue and exit from the two while loops 8 else if v is partial then kk+1 advance 9.end while 10.Reset Xk so that the next element is the first 11.kk-1 12. end while 13. if flag then output v 14. else output “no solution”,Algorithms

47、 Design Techniques and Analysis,子集和数问题,已知n+1个正数:wi,(1i n), 和M, 要求找出wi的和数是M的所有子集. 解的表示形式: 采用定长元组:解为n元组(X1,X2,Xn), 其中Xi表取0或1, 表示wi的在子集合中是否出现。 约束条件：并设定wi (1i n)按非降次序排列。,Algorithms Design Techniques and Analysis,限界函数,Bk(x(1),x(k)=true 当且仅当: 假定wi已经按照非降次序排列, 则可以强化限界函数, 如果下式成立, Bk(x(1),x(k)为假: 故,假定wi已经按照非降

48、次序排列, 限界函数 Bk(x(1),x(k)=true 当且仅当:,Algorithms Design Techniques and Analysis,Algorithm SUMOFSUBREC Input:w1,2,n and M, wi0, M 0. Output: A solution vector x1,2,n, where each xi is 0 or 1. 1. for k1 to n 2. xk0 3. end for 4. flagfalse 5. s 0; r w1+w2+wn 6. If r M then SUBOFSUB(s,1,r) endif 7. if flag

49、 then output x 8. else output “no solution” 9. end if Procedure SUMOFSUB (s,k,r) 1. xk 1 2. if s+wk=M /x is a legal solution 3. then set flagtrue and exit 4. else 5. if s+wk+wk+1M /x is partial Bk=true 6. then SUMOFSUB(s+wk,k+1,r-wk) 7. end if 8. end if 9. if s+r-wkM and s+wk+1M /Bk=true 10. then xk

50、 0, SUMOFSUB(s,k+1,r-wk) 11.end if,Algorithms Design Techniques and Analysis,Example,w1.6=5,10,12,13,15,18, M=30,0,1,73,X1=1,5,2,68,X2=1,15,3,58,X3=1,15,4,46,X3=0,X4=1,15,5,33,X4=0,X5=1,Algorithms Design Techniques and Analysis,哈密顿环,哈密顿环: 设G=(V,E)是一个n结点的连通图. 一个哈密顿环是一条沿着图G的n条边环行的路径,它访问每个结点一次并且回到它的原始位

51、置. 找出一个图中哈密顿环的回溯算法. 解的表示: (x1,xn)表示解,其中,xi是找到的环中第i个被访问的结点. 约束: x(1)=1, 如果1kn,则x(k)可以是不同于x(1),x(k-1)且和x(k-1)有边相连的任一结点.x(n)只能是必须与x(n-1)和x(1)有边相连的结点.,Algorithms Design Techniques and Analysis,Algorithm HAMILTONIANREC Input: An undirected graph G=(V,E). Output: A solution vector x1,2,n, where xi is the

52、number of ith visited node, and x1=1. 1. for k1 to n 2. xk0 3. end for 4. flagfalse 5. HAMILTON(1) 6. if flag then output x 7. else output “no solution” 8. end if Procedure HAMNILTON(k) 1. while true 2. NEXTVALUE(k) /assign xk 3. if xk=0 then exit end if 4. if k=n then flagtrue and exit 5. else HAMI

53、LTON(k+1) 6. end if 7. end while,Algorithms Design Techniques and Analysis,Procedure NEXTVALUE(k) while true xk = xk+1 mod (n+1) if xk=0 then exit endif if GRAPH (xk-1, xk) then for j=1 to k-1 do if xj=xk then exit endif end for if j=k then if kn or (k=n and GRAPH(xn,1) then exit endif endif endif e

54、ndwhile,Algorithms Design Techniques and Analysis,分枝-限界法:在生成当前E-结点的全部儿子之后再生成其它活结点的儿子且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法. 检索策略分为: FIFO(first in first out)检索:类似于BFS的状态空间检索,它的活结点表采用一张先进先出表(队列) LIFO(last in first out)检索:类似于D-检索的状态空间检索,它的活结点表是一张后进先出表(栈) LC-检索,13.5 Branch and Bound,Algorithms Design Technique

55、s and Analysis,例子：4皇后问题的FIFO分枝限界法,1,2,3,4,5,7,8,6,10,11,9,13,14,12,16,17,15,19,18,21,20,23,22,25,24,27,26,29,28,30,31,Algorithms Design Techniques and Analysis,FIFO/LIFO方法的缺陷,FIFO/LIFO-分枝限界法缺点:对下一个E-结点的选择相当死板,而且在某种意义上是盲目的.这种选择对于有可能快速检索到一个答案结点的结点没有任何优先权. 解决: 对活结点使用一个“有智力的”排序函数c(.)来选取下一个E-结点,使有可能产生答案结

56、点的活结点优先称为E-结点, 从而可以加快到达一个答案结点的检索速度. 对任一结点X,若要排序,必要进行计算,计算代价的度量标准: (1) 在生成一个答案结点之前,子树X需要生成的结点数; (2)子树X中离X最近的那个答案结点到X的路径长度.,Algorithms Design Techniques and Analysis,成本函数,结点成本函数c(.)定义如下: 如果X是答案结点,则c(X)是由状态空间树的根结点到X的成本(即所用的代价,它可以是级数,计算复杂度等); 如果X不是答案结点且子树X不包含任何答案结点,则c(X)=;否则c(X)等于子树X中具有最小成本的答案结点的成本. 问题：

57、要得到结点成本函数c(.)所用的计算工作量与解原问题具有相同的复杂度, 这是因为计算一个结点的代价通常要检索包含一个答案结点的子树X才能确定, 而这正是解决此问题所要做的工作. 因此, 要得到精确的成本函数一般是不现实的. 解决：定义新的成本估计函数: (X). 函数强使算法优先选择更靠近答案结点但又离根较近的结点.,Algorithms Design Techniques and Analysis,LC-检索,解决: (.):结点成本的估计函数（由X到达一个答案结点所需做的附加工作的估计函数）, 但单纯使用(.)会导致算法偏向于做纵深检查. 不只考虑结点X到一个答案结点的估计成本(.),还考

58、虑有根结点到结点X的成本h(X). 定义新的成本估计函数: (X)=f(h(X)+(X). 其中, (X)是由X到达一个答案结点所需做的附加工作的估计函数;h(X)是由根结点到结点X的成本.f(.)是一个非降函数. f函数强使算法优先选择更靠近答案结点但有离根较近的结点 LC-检索:选取下一个E-结点的检索策略总是选取(.)值最小的活结点作为下一个E-结点. 称为最小成本检索, 简称为LC-检索. LC分枝-限界检索: 伴之有限界函数的LC-检索称为LC分枝-限界检索.,Algorithms Design Techniques and Analysis,15-谜问题(例子),问题描述：在一个分

59、成44的方形棋盘上放有15块编号为1，2，15的牌，给定这些牌的初始排列（例图1），要求通过一系列合法的移动(只有相邻于空格的牌移动到空格才是合法的移动)将初始排列转换目标排列（如图2）。,图1,图2,Algorithms Design Techniques and Analysis,15-谜问题(例子),目标状态是否可由初始状态到达 (即目标状态是否在初始状态的状态空间中)的判定： 给棋盘的方格编上116的编号，位置i是目标排列中放i号牌的方格位置，位置16是空格的位置； 设POSITION(i)表示编号为i的牌在初始状态下的位置号，1iPOSITION(i)的数目； 在初始状态下，如果空格

60、在右图中阴影位置中的某一格处，则令X=1,否则令X=0。,定理：当且仅当LESS(1)+LESS(2)+LESS(16)+X是偶数时，目标状态可由初始状态到达。,Algorithms Design Techniques and Analysis,FIFO检索,Algorithms Design Techniques and Analysis,DFS检索,Algorithms Design Techniques and Analysis,15-谜问题的LC-检索,成本函数c(.): 从根出发到最近目标结点路径上的每个结点赋予这条路径的长度作为它们的成本. 估计成本函数(.): (X)=f(X)+