湘潭大学算法设计与分析第五章回溯法

2020/9/26,计算机算法设计与分析,1,第五章回溯法,2020/9/26,计算机算法设计与分析,2,用计算机求解问题,问题空间,现实求解过程,实际解,状态空间,对象的定义,机器求解过程,算法与程序的设计,机内解,2020/9/26,计算机算法设计与分析,3,计算机求解的过程,在状态空间寻找机内解可以看成是从初始状态出发搜索目标状态(解所在的状态)的过程。,状态空间,初始状态,目标状态,搜索,搜索的过程可描述为：S0S1Sn，其中S0为初态，Sn为终态。或者说(S0)且(Sn)，这里称为初始条件，称为终止条件。,2020/9/26,计算机算法设计与分析,4,求解是状态空间的搜索,求解的过程可以描述为对状态空间的搜索,S0,S11,S12,S1k, , , ,Sn1,Sni,Snm,其中S0为初始状态，不妨设Sni为 终止状态,S0,Sni,于是问题的求解就是通过搜索寻找出一条从初始状态S0到终止状态Sni的路径。,2020/9/26,计算机算法设计与分析,5,几种搜索方法,状态空间的搜索实际上是一种树的搜索，常用的方法有：,广度优先的搜索 深度优先的搜索 启发式的搜索,从初始状态开始，逐层地进行搜索。,从初始状态开始，逐个分枝地进行搜索。,从初始状态开始，每次选择最有可能达到终止状态的结点进行搜索。,2020/9/26,计算机算法设计与分析,6,三种搜索的优劣之处,一般来说，三种搜索方法各有优劣之处： 广度优先搜索的优点是一定能找到解；缺点是空间复杂性和时间复杂性都大。 深度优先搜索的优点是空间复杂性和时间复杂性较小；缺点是不一定能找到解。 启发式搜索是最好优先的搜索，优点是一般来说能较快地找到解，即其时间复杂性更小；缺点是需要设计一个评价函数，并且评价函数的优劣决定了启发式搜索的优劣。,2020/9/26,计算机算法设计与分析,7,树搜索的一般形式,SearchTree(Space T)/表L用来存放待考察的结点 unfinish = true; L = T.initial; / unfinish表示搜索未结束，先将初始状态放入L while (unfinish | L) a = L.first; /从L中取出第一个元素 if (a is goal) unfinish = false /若a是终态则结束 else Control-put-in(L, Sons(a); /否则，将a的儿子们以某种控制方式放入L中,2020/9/26,计算机算法设计与分析,8,三种搜索的不同之处,树的三种搜索方法的不同就在于它们对表L使用了不同控制方式：,L是一个队列 L是一个栈 L的元素按照某方式排序,广度优先搜索 深度优先搜索 启发式搜索,其中，深度优先搜索就是回溯法。,2020/9/26,计算机算法设计与分析,9,回溯法的形式化描述,假设能够用n元组（x1,x2,xn）表示一个给定的问题P的解，其中xi集合Si；n元组的子组（ x1,x2,xi ）（in），如果它满足一定的约束条件，则称为部分解。 如果它已经是满足约束条件的部分解，则添加xi+1Si+1形成新的子组（ x1,x2,xi ,xi+1 ）并检查它是否满足约束条件，若满足则继续添加xi+2Si+2，并以此类推。如果所有的xi+1Si+1都不满足约束条件，那么去掉xi+1，回溯到xi的位置，并去掉当前的xi，另选一个xiSi，组成新的子组（ x1,x2,xi ）并判断其是否满足约束条件。 如此反复下去，直到得到解或者证明无解为止。,2020/9/26,计算机算法设计与分析,10,递归回溯法的一般形式,Try(s) 做挑选候选者的准备； while (未成功且还有候选者) 挑选下一个候选者next； if (next可接受) 记录next； if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; return 成功与否,2020/9/26,计算机算法设计与分析,11,迭代回溯法的一般形式,先让我们回顾解空间搜索的一般形式：,SearchTree(Space T)/表L用来存放待考察的结点 unfinish = true; L = T.initial; / unfinish表示搜索未结束，先将初始状态放入L while (unfinish | L) a = L.first; /从L中取出第一个元素 if (a is goal) finish = false /若a是终态则结束 else Control-put-in(L, Sons(a); /否则，将a的儿子们以某种控制方式放入L中,回溯法中表L为栈，将初始状态压入栈中。,弹出栈顶元素,在通常求解问题时，解是由逐个状态构成的。因此，这里还需要判断状态是否可接受，并进行纪录路径等工作。,如果a可接收但未终止，则要将a的后继压入栈中。如果要抛弃状态a，当a是最后一个儿子时，还需要消除原有纪录甚至回溯一步。,2020/9/26,计算机算法设计与分析,12,如何判断最后一个儿子？,若只要遍历解空间树上的结点，那么将各个结点按栈的方式控制便可实现深度为主的搜索。 但是在求解问题时，需要记录解的路径，在回溯时还需要删除结点和修改相应的信息。 栈中的结点是分层次的，而现在没有区分它们的层次。这就增加了回溯判断和操作的困难。,那么怎么办？,采用一个简洁有效的方法：设计一个末尾标记，每次压栈时，先压入末尾标记。,2020/9/26,计算机算法设计与分析,13,用末尾标记的迭代回溯,Backtrack(Tree T) unfinish = true; L.Push(T.root); while (unfinish | L) a = L.Pop( ); if (a is the last mark) backastep( ); else if (a is good) record(a); if (a is goal) unfinish = false; output( ); else if (a has sons) L.Push-Sons(a) else move-off(a);,2020/9/26,计算机算法设计与分析,14,不可接受的结点,破坏了解的相容条件的结点 超出了状态空间的范围，或者说不满足约束条件的结点； 评价值很差的结点，即已经知道不可能获得解的结点； 已经存在于被考察的路径之中的结点，这种结点会造成搜索的死循环。,2020/9/26,计算机算法设计与分析,15,数的全排列问题,对于指定的n个数字，输出它所有可能的排列。 容易知道n个数字恰有n!个排列。 它有一个隐含的约束条件：每个数字用且只能用一次。,2020/9/26,计算机算法设计与分析,16,全排列问题的解空间树,设n=4，而需要排列的4个数字分别为：1，2，3，4。回顾我们手工对这四个数字的排列过程： （1 2 3 4）（1 2 4 3）（1 3 2 4）（）（4 3 2 1）,2020/9/26,计算机算法设计与分析,17,全排列问题中的数据表示,数组recn+1记录当前搜索路径上的每个结点所放置的数字； 数组usedn+1记录当前搜索路径上已经被使用过的数字；,2020/9/26,计算机算法设计与分析,18,用递归回溯法求N数全排列问题,Try(s) 做挑选候选者的准备； while (未成功且还有候选者) 挑选下一个候选者next； if (next可接受) 记录next； if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; return 成功与否,先回顾递归回溯法的一般形式：,2020/9/26,计算机算法设计与分析,19,用递归回溯法求N数全排列问题,Try(s) 做挑选候选者的准备； while (未成功且还有候选者) 挑选下一个候选者next； if (next可接受) 记录next； if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; return 成功与否,s为准备放置数字的位数,候选者为数字1到n。,j = 0; q = 0;,令数字从j = 0开始；q=0表示未成功。,数字不到n就还有候选者,(!q ,若数字没有使用过，便可接受,(Safe(j) ,Record (s,j);,(s = = n) q = 1; output( rec );,不成功，清掉该数字。,(!q) Move-Off(s, j); ,q ,recs=j; usedj=1;,(usedj=0) ,(!q) recs=0; usedj=0; ,n个位置都放完就成功了,记下该位置的数字,2020/9/26,计算机算法设计与分析,20,递归求全排列的主程序,N-Arrange( ) int recn + 1, usedn + 1; for (i = 1, i= n; i+) reci=0; usedi=0; try(1); ,从第一行开始递归,2020/9/26,计算机算法设计与分析,21,N数全排列问题的迭代程序,先看看迭代回溯法的一般形式：,Backtrack(Tree T) unfinish = true; L.Push(T.root); while (unfinish | L) a = L.Pop( ); if (a is the last mark) backastep( ); else if (a is good) record(a); if (a is goal) unfinish = false; output( ); else if (a has sons) L.Push-Sons(a) else move-off(a);,迭代从第一个位置开始，将数字1n和-1压入栈中，这里-1作为末尾标记。,i = 1; L.Push(1, 2, , n, -1);,a是末尾标记则回溯。,(a = = -1) backastep;,回溯需要做什么？,回溯需要退回一个位置，即i ；同时删除该位置的原纪录。,i ; a = reci; Move-Off(i, a); ,如果safe(a)则放下数字a。,(Safe(a) Record(i, a);,如果到了第n位，则成功。,(i = = n),当i n时，则必定有后继。无需考虑此情况。,i+; L.Push(1, 2, , n, -1);,2020/9/26,计算机算法设计与分析,22,N数全排列问题的迭代程序,Backtrack(Tree T) unfinish = true; i = 1; L.Push(1, 2, , n,-1); while (unfinish | L) a = L.Pop( ); if (a = = -1) i ; a = reci; reci=0;useda=0; else if (useda=0) reci=a; useda=1; if (i = = n) unfinish = false; output(rec); else i+; L.Push(1, 2, , n, -1); ,2020/9/26,计算机算法设计与分析,23,迭代求全排列主程序,N-Queens(n) int recn + 1, usedn + 1; for (j = 1, j n + 1; j+) recj = 0; usedj =0; Backtrack(n, rec); ,2020/9/26,计算机算法设计与分析,24,N数全排列问题的时间复杂性,对于规模为n的全排列而言,该算法的时间复杂度也就是搜索的结点总数。 为简单起见，只考虑访问可扩展结点的时间。 将根结点所在层次标为0层，其余依次为1,2,n层。则每层的可扩展结点数目依次为：n, n(n-1), n(n-1)(n-2), n(n-1)2, n!，设总的结点数目为S(n)，则有 S(n)= n!/(k!)，故 2n!S(n)3n!故时间复杂度为O(n!)。,2020/9/26,计算机算法设计与分析,25,N后问题,要求在一个nn的棋盘上放置n个皇后，使得她们彼此不受攻击。 按照国际象棋的规则，一个皇后可以攻击与之同一行或同一列或同一斜线上的任何棋子。 因此，N后问题等价于：要求在一个nn的棋盘上放置n个皇后，使得任意两个皇后不得在同一行或同一列或同一斜线上。,2020/9/26,计算机算法设计与分析,26,八皇后问题,先建立一个8*8格的棋盘，在棋盘的第一行的任意位置安放第一只皇后。 紧接着，我们就来放第二行，第二行的安放就要受一些限制了，因为与第一行的皇后在同一列或同一对角线的位置上是不能安放皇后的，接下来是第三行， 或许我们会遇到这种情况：在摆到某一行的时候，无论皇后摆放在什么位置，她都会被其它行的皇后吃掉，这时就必须要回溯，将前面的皇后重新摆放，,2020/9/26,计算机算法设计与分析,27,八皇后的一个可行解,2020/9/26,计算机算法设计与分析,28,用递归回溯法求N后问题,Try(s) 做挑选候选者的准备； while (未成功且还有候选者) 挑选下一个候选者next； if (next可接受) 记录next； if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; return 成功与否,先回顾递归回溯法的一般形式：,2020/9/26,计算机算法设计与分析,29,用递归回溯法求N后问题,Try(s) 做挑选候选者的准备； while (未成功且还有候选者) 挑选下一个候选者next； if (next可接受) 记录next； if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; return 成功与否,s为准备放置后的行数,候选者为1到n列。,j = 0; q = 0;,令列标记j = 0；q表示未成功。,列数不到n就还有候选者,(!q ,各后都安全，便可接受,(Safe(s, j) ,记下该行后的位置(列数),Record(s, j);,n行后都放完就成功了,(s = = n) q = 1; output( );,不成功，删去后在该行的位置。,(!q) Move-Off(s, j); ,q ,2020/9/26,计算机算法设计与分析,30,求解N后问题中的数据表示,数组Bn表示棋盘。若Bi=j，1i, jn，表示棋盘的第i行第j列上有皇后。 数组Cj=1表示第j列上无皇后，1jn。,数组Dk=1表示第k条下行()对角线上无皇后。,2020/9/26,计算机算法设计与分析,31,求解N后问题中的数据表示,数组Bn表示棋盘。若Bi = j，1i, jn，表示棋盘的第i行第j列上有皇后。 数组Cj = 1表示第j列上无皇后，1jn。,数组Dk = 1表示第k条下行()对角线上无皇后。,数组Uk = 1表示第k条上行()对角线上无皇后。,2020/9/26,计算机算法设计与分析,32,求解N后问题中的子程序,Record(s, j) k = s j + n 1; Bs = j; Cj = 0; Ds + j 1 = 0; Uk = 0; ,Move-Off(s, j) k = s j + n 1; Bs = 0; Cj = 1; Ds + j 1 = 1; Uk = 1; ,Safe(s, j) k = s j + n 1; if (Cj ,2020/9/26,计算机算法设计与分析,33,求解N后问题的主程序,N-Queens( ) int Bn + 1, Cn + 1, D2n, U2n; for (j = 1, j n + 1; j+) Bj = 0; Cj = 1; U2j = 1; U2j 1 = 1; D2j = 1; D2j 1 = 1; try(1); output(B); ,从第一行开始递归,2020/9/26,计算机算法设计与分析,34,N后问题的迭代程序,先看看迭代回溯法的一般形式：,Backtrack(Tree T) unfinish = true; L.Push(T.root); while (unfinish | L) a = L.Pop( ); if (a is the last mark) backastep( ); else if (a is good) record(a); if (a is goal) unfinish = false; output( ); else if (a has sons) L.Push-Sons(a) else move-off(a);,迭代从第一行开始，将第一行的1n列和0压入栈中，这里0作为末尾标记。,i = 1; L.Push(1, 2, , n, 0);,a是末尾标记则回溯。,(a = = 0) backastep;,回溯需要做什么？,回溯需要退回一行，即i ；同时删除该行的原纪录。,i ; a = Bi; Move-Off(i, a); ,如果safe(i, a)，则放下后。,(Safe(i, a) Record(i, a);,如果到了第n行，则成功。,(i = = n),当行i n时，则必定有后继。无需考虑此情况。,i+; L.Push(1, 2, , n, 0);,2020/9/26,计算机算法设计与分析,35,N后问题的迭代程序,Backtrack(Tree T) unfinish = true; i = 1; L.Push(1, 2, , n); while (unfinish | L) a = L.Pop( ); if (a = = 0) i ; a = Bi; Move-Off(i, a); else if (Safe(i, a) Record(i, a); if (i = = n) unfinish = false; output(B); else i+; L.Push(1, 2, , n, 0); ,2020/9/26,计算机算法设计与分析,36,迭代回溯解N后问题的主程序,N-Queens(n) int Bn + 1, Cn + 1, D2n, U2n; for (j = 1, j n + 1; j+) Bj = 0; Cj = 1; U2j = 1; U2j 1 = 1; D2j = 1; D2j 1 = 1; Backtrack(n, B); ,2020/9/26,计算机算法设计与分析,37,N后问题的时间复杂性,如果只要找出N后问题的一个解，那么这是一个求路径的问题。 求路径：只需要找到一条路径便可以得到解。设每个状态有k个后继，其搜索树为K叉树，其结点总数为kn+11，遍历的时间为O(kn)，这里n为找到解的路径长度。 N后问题的路径深度为n，可选择的后继有n个，所以时间复杂性为O(nn)。,2020/9/26,计算机算法设计与分析,38,旅行售货员问题,TSP：某售货员到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条路线，经过每个城市一遍最后回到驻地的路线，使得总的路程(或总旅费)最小。 设G=(V, E)是一个带权图。图中各边的费用(权值)为正。图中一条周游路线是包括V中所有顶点的回路。一条周游路线的费用是该路线上所有边的费用之和。所谓旅行售货员问题就是要在图G中找出一条最小费用的周游路线。,2020/9/26,计算机算法设计与分析,39,Try(s) 做挑选候选者的准备； while (未成功且还有候选者) 挑选下一个候选者next； if (next可接受) 记录next； if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; return 成功与否,线路上的第s个结点,这里只需依次考 察n1个结点，即 for (i=2; i=n; i+) 下一个候选就是i,结点i尚未在路线中且总耗费值不大。,考虑TSP的递归回溯算法,就是将结点i放入路线中并修改耗费值,s = = n,若新线路更好，就用新线路取代老线路。,这里无所谓成功与否，因为每一条周游路线都要进行比较。,2020/9/26,计算机算法设计与分析,40,TSP的递归回溯算法,Try(s) for (i = 2; i = n; i+) if (Accept(i) Record(s, i)； if (s = = n) if (better) TakeNewPath( ) ; else Try(s+1); Move-off(s, i) return ,2020/9/26,计算机算法设计与分析,41,求解TSP的数据结构,用数组Cnn存放n个城市间的费用值。 用数组Pn记录已经找到的费用最小的周游路线，C为其相应的费用， C初值为。 用数组Nn记录目前正在寻找的周游路线，NC为其相应的费用； 如果NC+CNn1小于C，则路线N更佳，于是P = N，C = NC+CNn1。 如果结点next不是N中已有的结点，且C大于 NC+CNinext，则结点next是可接受的。,2020/9/26,计算机算法设计与分析,42,TSP的递归程序Try,Try(s) for (i = 2; i = n; i+) if (Accept(i) Record(s, i)； if (s = = n) if (better) TakeNewPath( ) ; else Try(s+1); Move-off(s, i) return ,(C NC+CNsi ,2020/9/26,计算机算法设计与分析,43,Try中的子程序,Record(s, i); NC = NC + CNsi; Ti = 0; Ns = i; ,Move-off(s, i); NC = NC CNsi; Ti = 1; Ns = 0;,TakeNewPath( ) for (i=1; i=n; i+) Pi = Ni; C = NC + CNs1;,2020/9/26,计算机算法设计与分析,44,递归回溯求TSP的主程序,TSP(n, Cnn) for (i = 1; i = n; i+) Ni=0; Pi = 0; Ti = 1 NC = 0；C = ; N1=1; T1 = 0; Try(1); Output(P)； ,2020/9/26,计算机算法设计与分析,45,考虑TSP的迭代程序,为了便于迭代程序中回溯的判断，我们将城市结点编号为1 n，用编号0作为末尾的标记。 先回顾一下采用末尾标记的迭代回溯法：,2020/9/26,计算机算法设计与分析,46,考虑TSP的迭代程序,Backtrack(Tree T) unfinish = true; L.Push(T.root); while (unfinish | L) a = L.Pop( ); if (a is the last mark) backastep( ); else if (a is good) Record(a); if (a is goal) unfinish = false; output( ); else if (a has sons) L.Push-Sons(a) else Move-off(a);,要比较所有路径，无需此句,L ) ,初始化后压入除1外的n-1个结点。,N1 = 1; j = 1; L.Push-Sons(2,n,0);,末尾标记为0。,(a = = 0) backastep( );,删除第j个结点，然后j .,Move-off(Nj1, Nj); j ;,a不在路线中且新增后的费用仍低。,(Ta,(j = = n ) if (C NC+Ca1),TakeNewPath( ); Move-off(Nj, a);,else j+; L.Push-Sons(2,n,0),2020/9/26,计算机算法设计与分析,47,TSP的迭代回溯,Backtrack(n, C) j = 1; Nj = 1; L.Push-Sons(2,n,0); while (L) a = L.Pop( ); if (a = = 0) Move-off(Nj1, Nj); j ; else if (Ta L.Push-Sons(2,n,0),2020/9/26,计算机算法设计与分析,48,Backtrack中的子程序,Record(Nj,a); NC = NC + CNja; Ta = 0; Nj+1 = a; ,Move-off(Nj,a); NC = NC CNja; Ta = 1; Nj+1 = 0;,TakeNewPath( ) for (i=1; i=n; i+) Pi = Ni; C = NC + CNj1;,2020/9/26,计算机算法设计与分析,49,迭代回溯求TSP的主程序,TSP(n, Cnn) for (i = 1; i = n; i+) Ni=0; Pi = 0; Ti = 1 NC = 0；C = ; N1=1; T1 = 0; Backtrack(n, C); Output(P)； ,2020/9/26,计算机算法设计与分析,50,求解TSP的时间复杂性,显然TSP是一个求排列的问题。 求排列：确定n个元素的满足某种性质的排列。其搜索树称为排列树，通常有n!个叶结点，因此遍历排列树需要时间为O(n!)。 所以TSP问题的时间复杂性为O(n!),2020/9/26,计算机算法设计与分析,51,0-1背包问题,给定n个物品和一个背包。物品i的重量为wi，价值为vi，背包容量为c。问如何选择装入背包中的物品，使得装入背包的物品的价值最大？,在装入背包时，每种物品i只有两种选择，装入或者不装入，既不能装入多次，也不能只装入一部分。因此，此问题称为0-1背包问题。,如果在装入背包时，物品可以切割，即可以只装入一部分，这种情况下的问题称为背包问题。,2020/9/26,计算机算法设计与分析,52,用回溯法解0-1背包问题,类似于旅行售货员问题，用一个数组Pn存放目前取得的最优解，用变量V表示其价值；再用一个数组Nn来产生新的解，用变量NV表示其价值，用变量W表示其重量。如果新解更优，则替代原来的最优解，否则就丢弃新解。然后回溯寻找下一个新解。 为此，我们先回顾一下回溯法的一般递归算法：,2020/9/26,计算机算法设计与分析,53,用回溯法解0-1背包问题,Try(s) 做挑选候选者的准备； while (未成功且还有候选者) 挑选下一个候选者next； if (next可接受) 记录next； if (满足成功条件) 成功并输出结果 else Try(s+1); if (不成功) 删去next的记录; return 成功与否,考察的第s个物品,物体s可放入背包中；,将s放入背包中并修改权重与容量；,s = = n,这里无论成功与否都要继续考察,“记录”的 逆操作,2020/9/26,计算机算法设计与分析,54,用回溯法解0-1背包问题,Try(s) for (i = 0; i 2; i+) if (Accept(i) Record(s, i)； if (s = = n) if ( better ) TakeNewChoice( ); else Try(s+1); Move-off(s, i); return ,(W+ws*i = C) ,(NV V),2020/9/26,计算机算法设计与分析,55,0-1背包问题中的几个子程序,Record(s, i) Ns = i; W=W + ws*i; NV = NV + vs*i;,Move-off(s, i)Ns = 0; W = W ws*i; NV = NV vs*i;,TakeNewChoice( ) for (i=1; i=n; i+) Pi = Ni; V = NV;,2020/9/26,计算机算法设计与分析,56,0-1背包问题的主程序,Bag(n, C, wn, vn) for (i=1; i=n; i+) Ni=0; Pi = 0; Ti = 1; NV = 0, W = 0; V = 0; Try(1); Output(P); ,2020/9/26,计算机算法设计与分析,57,考虑0-1背包问题的迭代实现,先看看回溯法的一般的迭代形式：,Backtrack(Tree T) unfinish = true; L.Push(T.root); while (unfinish | L) a = L.Pop( ); if (a is the last mark) backastep( ); else if (a is good) Record(a); if (a is goal) unfinish = false; output( ); else if (a has sons) L.Push-Sons(a) else Move-off(a);,(L) ,j = 1; L.Push(1, 0, 1);,(a = = 1) backastep( );,Move-off(j, Nj); j ;,(W+wj*a = C) Record(j, a);,( j = = n ),if (V NV) TakeNewChoice( );,else j+; L.Push(1, 0, 1);,2020/9/26,计算机算法设计与分析,58,0-1背包问题的迭代实现,Backtrack(Tree T) j = 1; L.Push(1, 0, 1); while (L) a = L.Pop( ); if (a = = 1) Move-off(j, Nj); j ; else if (W+wj*a = C) Record(a); if (j = = n ) if (V NV) TakeNewChoice( ); else j+; L.Push(1, 0, 1); ,2020/9/26,计算机算法设计与分析,59,0-1背包问题的时间复杂性,显然0-1背包问题是一个求子集的问题。 求子集：从n个元素的集合S中找出满足某个性质子集。其搜索树称为子集树，是棵二叉树，通常有2n个叶结点，遍历的时间为O(2n) 。 0-1背包问题的时间复杂性为O(2n)。,2020/9/26,计算机算法设计与分析,60,求排列、求子集、求路径,求排列：确定n个元素的满足某种性质的排列。其搜索树称为排列树，通常有n!个叶结点，因此遍历排列树需要时间为O(n!)。 求子集：从n个元素的集合S中找出满足某个性质子集。其搜索树称为子集树，是棵二叉树，通常有2n个叶结点，遍历的时间为O(2n) 。 求路径：只需要找到一条路径便可以得到解。设每个状态有k个后继，其搜索树为K叉树，其结点总数为kn+11，遍历的时间为O(kn)，这里n为找到解的路径长度。,2020/9/26,计算机算法设计与分析,61,回溯法小结,回溯法是一种通用的算法，实为深度优先的搜索方法。 回溯法可以递归实现，也可以迭代实现。 回溯法通常求解三类问题： (1)求排列：时间复杂性为O(f(n)n!)； (2)求子集：时间复杂性为O(f(n)2n)； (3)求路径：时间复杂性为O(f(n)kn)。 这里f(n)为处理一个结点的时间复杂性。,