回溯法设计的运用和发展.ppt

《回溯法设计的运用和发展.ppt》由会员分享，可在线阅读，更多相关《回溯法设计的运用和发展.ppt（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系算法设计与分析算法设计与分析 第五讲第五讲 回溯法回溯法 教教 师师:屈屈 喜喜 龙龙 5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系基本内容基本内容 1）了解回溯法的基本思路及回）了解回溯法的基本思路及回溯法的基本要素溯法的基本要素 2）掌握）掌握23个用回溯法求解的程个用回溯法求解的程序实现方法序实现方法3）回溯法的优点与缺点总结）回溯法的优点与缺点总结5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系用计算机求解问题问题空间现实求解过程实际解状态空间对象的定义机器

2、求解过程算法与程序的设计机内解5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系计算机求解的过程在状态空间寻找机内解可以看成是从初始状态在状态空间寻找机内解可以看成是从初始状态出发搜索目标状态出发搜索目标状态(解所在的状态解所在的状态)的过程。的过程。状态空间初始状态目标状态搜索n搜索的过程可描述为：搜索的过程可描述为：S0S1Sn，其中其中S0为初态，为初态，Sn为终态。或者说为终态。或者说(S0)且且(Sn)，这里这里称为初始条件，称为初始条件，称为终止条件。称为终止条件。5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系求解是状

3、态空间的搜索求解的过程可以描述为对状态空间的搜索求解的过程可以描述为对状态空间的搜索S0S11S12S1k Sn1SniSnm其中其中S0为初始状为初始状态，不妨设态，不妨设Sni为为终止状态终止状态S0Snin于是问题的求解就是通过搜索寻找出一条从初于是问题的求解就是通过搜索寻找出一条从初始状态始状态S0到终止状态到终止状态Sni的路径。的路径。5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系几种搜索方法状态空间的搜索实际上是一种树/DAG的搜索，常用的方法有：n广度优先的搜索广度优先的搜索n深度优先的搜索深度优先的搜索n启发式的搜索启发式的搜索从初始状态开始

4、，逐层地进行搜索。从初始状态开始，逐个分枝地进行搜索。从初始状态开始，每次选择最有可能达到终止状态的结点进行搜索。5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系三种搜索的优劣之处一般来说，三种搜索方法各有优劣之处：一般来说，三种搜索方法各有优劣之处：广度优先搜索的优点是一定能找到解；缺点是广度优先搜索的优点是一定能找到解；缺点是空间复杂性和时间复杂性都大。空间复杂性和时间复杂性都大。深度优先搜索的优点是空间复杂性和时间复杂深度优先搜索的优点是空间复杂性和时间复杂性较小；缺点是不一定能找到解。性较小；缺点是不一定能找到解。启发式搜索的是最好优先的搜索，优点是一般

5、启发式搜索的是最好优先的搜索，优点是一般来说能较快地找到解，即其时间复杂性更小；来说能较快地找到解，即其时间复杂性更小；缺点是需要设计一个评价函数，并且评价函数缺点是需要设计一个评价函数，并且评价函数的优劣决定了启发式搜索的优劣。的优劣决定了启发式搜索的优劣。5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系三种搜索的不同之处 树的三种搜索方法的不同就在于它们对表L使用了不同控制方式：nL是一个队列nL是一个栈nL的元素按照某方式排序n广度优先搜索n深度优先搜索n启发式搜索其中，深度优先搜索就是回溯法。其中，深度优先搜索就是回溯法。5/27/2023湖南工程学院湖

6、南工程学院 计算机科学与技术系计算机科学与技术系什么是回溯法什么是回溯法回溯法实际是回溯法实际是穷举算法穷举算法，按问题某种变化趋势，按问题某种变化趋势穷举下去，如某状态的变化用完还没有得到最穷举下去，如某状态的变化用完还没有得到最优解，则返回上一种状态继续穷举。回溯法有优解，则返回上一种状态继续穷举。回溯法有“通用的解题法通用的解题法”之称，其采用了一种之称，其采用了一种“走不走不通就掉头通就掉头”思想作为其控制结构，用它可以求思想作为其控制结构，用它可以求出问题的所有解和任意解。出问题的所有解和任意解。它的应用很广泛，很多算法都用到回溯法，例它的应用很广泛，很多算法都用到回溯法，例如，图的

7、深度优先算法，最短路径算法，骑士如，图的深度优先算法，最短路径算法，骑士巡游算法，八皇后问题，巡游算法，八皇后问题，N重循环等都用到回溯重循环等都用到回溯法，当然其中还使用了其他策略。法，当然其中还使用了其他策略。5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系回溯法的一般形式Try(s)做挑选候选者的准备；做挑选候选者的准备；while(未成功且还有候选者未成功且还有候选者)挑选下一个候选者挑选下一个候选者next；if (next可接受可接受)记录记录next；if(满足成功条件满足成功条件)成功并输出结果成功并输出结果 else Try(s+1);if(不

8、成功不成功)删去删去next的记录的记录;return 成功与否成功与否5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系解空间树(Solution Space Tree)start?dead enddead end?dead enddead end?success!dead end5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系解空间的组织(Tree Organization Of Solution Space)任何时候任何时候,在构造问题解的时候在构造问题解的时候,都包含做都包含做出一系列的决策出一系列的决策,如果我们将做出的决

9、策画如果我们将做出的决策画出来出来,这个图就象一棵树这个图就象一棵树.建立一个树型结建立一个树型结构构,使得树叶对应解空间的一个解使得树叶对应解空间的一个解,而内部而内部节点的一个分支节点的一个分支,对应一个决策对应一个决策,这样这样,便可便可以将解空间组织为一棵解空间树以将解空间组织为一棵解空间树.回溯法可以很容易地被用来搜索一个集合回溯法可以很容易地被用来搜索一个集合的所有子集合或是排列的所有子集合或是排列.5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系当我们要解决的问题是要求一个使问题最当我们要解决的问题是要求一个使问题最优的优的n个元素的子集个元素的子

10、集,问题的解空间常可以问题的解空间常可以组织成一棵子集树组织成一棵子集树构造所有的子集构造所有的子集n个元素的集合有多少个子集个元素的集合有多少个子集?如果每个如果每个Si的大小是的大小是k,对每个对每个xiSi,共共有有kn 个子集个子集子集树子集树5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系子集树(Subtree)5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系货箱装载问题问题问题给定给定n个个货箱货箱,货箱货箱i重为重为wi.船可以装载的船可以装载的货箱货箱总重量为总重量为W.货箱货箱装载问题是在不使船翻的前提下装载装载

11、问题是在不使船翻的前提下装载尽可能多的货箱尽可能多的货箱.解空间解空间假设解可以由向量假设解可以由向量(x1,x2,xn)表示表示,xi0,1,xi=1表示货箱表示货箱i被装上船被装上船,xi=0表示货箱表示货箱i不装上船不装上船.5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系货箱装载问题可以形式地描述如下货箱装载问题可以形式地描述如下:解空间树解空间树有有2n个叶子的子集树个叶子的子集树在第在第j层层，节点的展开由节点的展开由xj+1的值决定的值决定.5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系Subtree:n=410

12、x2010 x1x3x41湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系约束函数约束函数令令cw(i)表示到第表示到第i层的当前重量层的当前重量,记为记为则约束函数为则约束函数为剪枝剪枝若若，则停止搜索第，则停止搜索第i层及其下面的层及其下面的层层,否则，继续搜索否则，继续搜索.5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系对 n=4,w=8,6,2,3,W=12进行回溯1x1101x20 x4x38148101,0,1,0C(t)活动节点死节点101310湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系回溯递归版本Backtra

13、ck(t)1 if(tn)then 2 if(cwbestw)then bestwcw3 return4 else 5if(C(t)W)then 6 cwcw+wt7 Backtrack(t+1)8 cwcw-wt9 Backtrack(t+1)5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系改进的回溯算法改进的回溯算法利用限界函数利用限界函数其中其中,r(j)表示剩余货箱的总重量表示剩余货箱的总重量剪枝剪枝若若,则停止搜索第则停止搜索第i 层及其下面层及其下面的层的层,否则，继续搜索否则，继续搜索.其中其中,bestw表示目表示目前为止所得到的最佳重量前为止所

14、得到的最佳重量5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系对 n=4,w=8,6,2,3,W=12进行回溯1x1101x20/19x4x38/1914/198/1310/13113/13010/13Bestw=1008/11111/1100Bestw=118/80/11C(t)/B(t)湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系0-1 背包问题问题问题给定给定n个物品个物品,物品物品i重重wi，价值，价值vi，背，背包可以承受的物品的总重最大为包可以承受的物品的总重最大为W.0-1背包问题的目的是要选择一个物品的背包问题的目的是要选择一个

15、物品的子集，使其总重量子集，使其总重量W而价值最大而价值最大.解空间解空间假设解可以由向量假设解可以由向量(x1,x2,xn)表示表示,xi0,1,xi=1表示物品表示物品i被放进背包被放进背包,xi=0表示物品表示物品i不被放进背包不被放进背包.5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系0-1背包问题可以被形式地描述成如下形式背包问题可以被形式地描述成如下形式:使得使得解空间树解空间树有有2n个叶子节点的子集树个叶子节点的子集树解空间第解空间第j层的成员由层的成员由xj的值进行分割的值进行分割.5/27/2023湖南工程学院湖南工程学院 计算机科学与技术

16、系计算机科学与技术系子集树:n=410 x2010 x1x3x41湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系 约束函数约束函数令令cw(i)表示目前到第表示目前到第i层的总重量层的总重量,记为记为则约束函数为则约束函数为剪枝剪枝若若，则停止搜索第，则停止搜索第i层及其下面的层，层及其下面的层，否则，继续搜索否则，继续搜索.5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系界限函数界限函数在这里在这里,cv(i)表示目前到第表示目前到第i层的价值层的价值,r(i)表示剩余物品的总价值表示剩余物品的总价值,记为记为,剪枝剪枝若若,则停止搜索第则停止

17、搜索第i层和下面的层和下面的层，否则，继续搜索层，否则，继续搜索.在此在此,bestv表示目前表示目前所得到的最好价值所得到的最好价值5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系r(i)越大,搜索的分支越多.我们是否可以剪掉更多的分支呢?答案是可以.具体地说,我们可以构造如下的更好的界限函数:首先,提前将物品以单位重量价值递减的顺序进行排列,记为 考虑第 i层,背包的剩余空间为 W-cw(i),用贪心策略把剩余的物品放进背包，直到第k件物品放不进去.则，5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系r(i)计算得越精确,则

18、r(i)的值比原始 r(i)的值越小,因此可以剪掉更多的枝.例如,给定一个例子:n=4,c=7,v=9,10,7,4,w=3,5,2,1,t则 v/w=3,2,3.5,4.依据 v/w对物品进行排序对物品进行排序,则得到一个新的例子:n=4,c=7,v=4,7,9,10,w=1,2,3,5.则 v/w=4,3.5,3,2.5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系n=4,W=7,v=4,7,9,10,w=1,2,3,5 v/w=4,3.5,3,2.1x110 x2x4x301,1,1,0C(t)/B(t)0/221/223/2220101/1900/203

19、/196/206/22湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系考虑0-1背包问题的迭代实现先看看回溯法的一般的迭代形式：nBacktrack(Tree T)n unfinish=true;L.Push(T.root);n while(unfinish|L)n a=L.Pop();n if(a is the last mark)backastep();nelse if(a is good)Record(a);n if(a is goal)unfinish=false;output();n else if(a has sons)L.Push-Sons(a)n else Mov

20、e-off(a);要比较所有组合，无需此句。(L)从物品1开始，压入物品1的两种选择。j=1;L.Push(1,0,1);用1作末尾标记 。(a=1)backastep();回溯：删除相关记录，并退回一步。Move-off(j,Nj);j;只要容量没有超过就可以选(W+wj*a=C)Record(j,a);j=n。(j=n)若新的组合更好，则选取新组合。if(V NV)TakeNewChoice();只要没选购就可继续选，故必定有后继。else j+;L.Push(1,0,1);5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系用回溯法解0-1背包问题类似于旅行售

21、货员问题，用一个数组Pn存放目前取得的最优解，用变量V表示其价值；再用一个数组Nn来产生新的解，用变量NV表示其价值，用变量W表示其重量。如果新解更优，则替代原来的最优解，否则就丢弃新解。然后回溯寻找下一个新解。为此，我们先回顾一下回溯法的一般递归算法：5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系用回溯法解0-1背包问题Try(s)做挑选候选者的准备；while(未成功且还有候选者)挑选下一个候选者next；if (next可接受)记录next；if(满足成功条件)成功并输出结果 else Try(s+1);if(不成功)删去next的记录;return 成

22、功与否考察的第s个物品只需考两种情况，选或不选，即for(i=0;i2;i+)下个候选就是i。物体s可放入背包中；将s放入背包中并修改权重与容量；s=n这里无论成功与否都要继续考察“记录”的逆操作5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系用回溯法解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 V)5/27/2023湖南工程学院湖南工程学院 计算机

23、科学与技术系计算机科学与技术系0-1背包问题中的几个子程序Record(s,i)Ns=i;W=W+ws*i;NV=NV+vs*i;nMove-off(s,i)Ns=0;W=W ws*i;NV=NV vs*i;nTakeNewChoice()n for(i=1;i=n;i+)n Pi=Ni;V=NV;5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系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);5/27/2023湖南工程学院湖南工程学院 计算机

24、科学与技术系计算机科学与技术系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);5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系0-1背包问题的时间复杂性显然显然0-1背包问题是一个求子集的问题。背包问题是一个求子集的问题。求子集：从求子集：从n个元素的集合个元素的集合S中找出满

25、足某中找出满足某个性质子集。其搜索树称为子集树，是棵个性质子集。其搜索树称为子集树，是棵二叉树，通常有二叉树，通常有2n个叶结点，遍历的时间为个叶结点，遍历的时间为O(2n)。0-1背包问题的时间复杂性为背包问题的时间复杂性为O(2n)。5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系N后问题要求在一个要求在一个nn的棋盘上放置的棋盘上放置n个皇后，使得她们个皇后，使得她们彼此不受攻击。彼此不受攻击。按照国际象棋的规则，一个皇后可以攻击与之同按照国际象棋的规则，一个皇后可以攻击与之同一行或同一列或同一斜线上的任何棋子。一行或同一列或同一斜线上的任何棋子。因此，因

26、此，N后问题等价于：要求在一个后问题等价于：要求在一个nn的棋盘上的棋盘上放置放置n个皇后，使得任意两个皇后不得在同一行或个皇后，使得任意两个皇后不得在同一行或同一列或同一斜线上。同一列或同一斜线上。5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系n 皇后问题例如,n=45/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系用递归回溯法求N后问题Try(s)做挑选候选者的准备；做挑选候选者的准备；while(未成功且还有候选者未成功且还有候选者)挑选下一个候选者挑选下一个候选者next；if (next可接受可接受)记录记录next；i

27、f(满足成功条件满足成功条件)成功并输出结果成功并输出结果 else Try(s+1);if(不成功不成功)删去删去next的记录的记录;return 成功与否成功与否 5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系用递归回溯法求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表示未成

28、功。列数不到n就还有候选者(!q&j 0 do4xk xk+15 whilexk=n and!place(k)do6 xk xk+1 /找到第k个皇后不以前面皇后冲突的位置 7 if xk=n then8if k=n then sum sum+1/得到一个解9 else k k+1 /否则继续往下寻找下一个皇后的位置10 xk 011 else k k-1 /对第k个皇后已经搜索完最后一个位置，回溯5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系Place(k)1 for j1 to k-1 do2if|k-j|=|xj-xk|or xj=xk then3ret

29、urn false4 elsereturn true5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系求解N后问题中的子程序Record(s,j)k=s j+n 1;Bs=j;Cj=0;Ds+j 1=0;Uk=0;nMove-Off(s,j)k=s j+n 1;Bs=0;Cj=1;Ds+j 1=1;Uk=1;nSafe(s,j)k=s j+n 1;if(Cj&Uk&Ds+j 1)return true else return false;5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系求解N后问题的主程序N-Queens()int

30、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);将数组Bn,Cn,U2n和D2n都赋予初值。从第一行开始递归5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系N后问题的迭代程序先看看迭代回溯法的一般形式：nBacktrack(Tree T)n unfinish=true;L.Push(T.root);n while(unfinish|L)n a=L.Pop();n if(a is the last mark)backastep();n

31、 if(a is good)record(a);n if(a is goal)unfinish=false;output();n else if(a has sons)L.Push-Sons(a)n 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);如果到了

32、第n行，则成功。(i=n)当行i n时，则必定有后继。无需考虑此情况。i+;L.Push(1,2,n,0);5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系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);if(Safe(i,a)Record(i,a);if(i=n)unfinish=false;output(B);else i+;L.Push(1,2,n,0);5/27/2023湖南工程

33、学院湖南工程学院 计算机科学与技术系计算机科学与技术系迭代回溯解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);5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系N后问题的时间复杂性如果只要找出N后问题的一个解，那么这是一个求路径的问题。求路径：只需要找到一条路径便可以得到解。设每个状态有k个后继，其搜索树为K叉树，其结点总数为kn+11，遍历的时间为O(kn)，这里n为找到解的路径长度。N后

34、问题的路径深度为n，可选择的后继有n个，所以时间复杂性为O(nn)。5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系求排列、求子集、求路径求排列：确定求排列：确定n个元素的满足某种性质的排列。其个元素的满足某种性质的排列。其搜索树称为排列树，通常有搜索树称为排列树，通常有n!个叶结点，因此遍个叶结点，因此遍历排列树需要时间为历排列树需要时间为O(n!)。求子集：从求子集：从n个元素的集合个元素的集合S中找出满足某个性质中找出满足某个性质子集。其搜索树称为子集树，是棵二叉树，通常子集。其搜索树称为子集树，是棵二叉树，通常有有2n个叶结点，遍历的时间为个叶结点，遍历

35、的时间为O(2n)。求路径：只需要找到一条路径便可以得到解。设求路径：只需要找到一条路径便可以得到解。设每个状态有每个状态有k个后继，其搜索树为个后继，其搜索树为K叉树，其结点叉树，其结点总数为总数为kn+11，遍历的时间为，遍历的时间为O(kn)，这里，这里n为找为找到解的路径长度。到解的路径长度。5/27/2023湖南工程学院湖南工程学院 计算机科学与技术系计算机科学与技术系回溯法小结回溯法是一种通用的算法，实为深度优先的搜索回溯法是一种通用的算法，实为深度优先的搜索方法。方法。回溯法可以回溯法可以递归实现递归实现，也可以，也可以迭代实现迭代实现。回溯法通常求解三类问题：回溯法通常求解三类问题：(1)求排列：时间复杂性为求排列：时间复杂性为O(f(n)n!)；(2)求子集：时间复杂性为求子集：时间复杂性为O(f(n)2n)；(3)求路径：时间复杂性为求路径：时间复杂性为O(f(n)kn)。这里这里f(n)为处理一个结点的时间复杂性。为处理一个结点的时间复杂性。5/27/2023