第5章 算法设计基本方法2.ppt

2020/1/29南京信息工程大学,计算机与软件学院 闫雷鸣,第5 章算法设计基本方法2,南京信息工程大学,2020/1/29,例：0-1背包问题,设有3种物品，背包容量40公斤。物品1的重量30公斤，价值150元；物品2的重量20公斤，价值80元；物品3的重量10公斤，价值70元。,南京信息工程大学,2020/1/29,0-1背包问题的解空间（状态树）,能优化吗？,南京信息工程大学,2020/1/29,5.2 回溯法,“通用解题法”，是带优化的穷举法。 按深度优先策略，从根结点出发搜索解空间树。 对任意结点，先判断该结点是否包含问题的解。 若肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯； 否则，进入该子树，继续按深度优先搜索策略搜索。 解为叶子结点 这种以深度优先方式系统搜索问题解的算法称为回溯法，它适用于求解组合数较大的问题,南京信息工程大学,2020/1/29,回溯法,在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造； 回溯法求问题的所有解时，要回溯到根，且根结点的所有子树都被搜索遍才结束。 在它求问题的一个解时，只要搜索到问题的一个解就结束。,南京信息工程大学,2020/1/29,回溯法,回溯法的使用 1、确定问题状态结构； 2、分析问题状态空间树； 3、确定深度搜索与回溯规则； 4、确定解状态判别规则；,南京信息工程大学,2020/1/29,回溯法的算法框架,5.2.1 问题的解空间,5.2.2 回溯法的基本思想,5.2.3 递归回溯,5.2.4 迭代回溯,5.2.5 示例,南京信息工程大学,2020/1/29,复杂问题常常有很多的可能解，这些可能解构成了问题的解空间。解空间也就是进行穷举的搜索空间，所以，解空间中应该包括所有的可能解。确定正确的解空间很重要，如果没有确定正确的解空间就开始搜索，可能会增加很多重复解，或者根本就搜索不到正确的解。,5.2.1 问题的解空间,南京信息工程大学,2020/1/29,对于任何一个问题，可能解的表示方式和它相应的解释隐含了解空间及其大小。 例如，对于有n个物品的0/1背包问题，其可能解的表示方式可以有以下两种： （1）可能解由一个不等长向量组成，当物品i(1in)装入背包时，解向量中包含分量i，否则，解向量中不包含分量i，当n=3时，其解空间是： ( ), (1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2, 3) （2）可能解由一个等长向量x1, x2, , xn组成，其中xi=1(1in)表示物品i装入背包，xi=0表示物品i没有装入背包，当n=3时，其解空间是： (0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1) ,南京信息工程大学,2020/1/29,为了用回溯法求解一个具有n个输入的问题，一般情况下，将其可能解表示为满足某个约束条件的等长向量X=(x1, x2, , xn)，其中分量xi (1in)的取值范围是某个有限集合Si=ai1, ai2, , airi，所有可能的解向量构成了问题的解空间。,南京信息工程大学,2020/1/29,问题的解空间一般用解空间树（Solution Space Trees,也称状态空间树）的方式组织，树的根结点位于第1层，表示搜索的初始状态，第2层的结点表示对解向量的第一个分量做出选择后到达的状态，第1层到第2层的边上标出对第一个分量选择的结果，依此类推，从树的根结点到叶子结点的路径就构成了解空间的一个可能解。,南京信息工程大学,2020/1/29,对于n=3的0/1背包问题，其解空间树如下图所示，树中的8个叶子结点分别代表该问题的8个可能解。 （依编号顺序搜索）,南京信息工程大学,2020/1/29,5.2.2 回溯法的基本思想,从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。 先判断结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，即判断该结点是否包含问题的（最优）解。 如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）； 否则，进入以该结点为根的子树，继续按照深度优先策略搜索。,南京信息工程大学,2020/1/29,例如，对于n=3的0/1背包问题，三个物品的重量为20, 15, 10，价值为20, 30, 25，背包容量为25，从下图所示的解空间树的根结点开始搜索，搜索过程如下（依编号顺序）：,不可行解,南京信息工程大学,2020/1/29,回溯法的搜索过程涉及的结点（称为搜索空间）只是整个解空间树的一部分，在搜索过程中，通常采用两种策略避免无效搜索： （1）用约束条件剪去得不到可行解的子树； （2）用目标函数剪去得不到最优解的子树。 这两类函数统称为剪枝函数（Pruning Function）。 需要注意的是，问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构，只需要存储从根结点到当前结点的路径。,南京信息工程大学,2020/1/29,回溯法的求解过程,由于问题的解向量X=(x1, x2, , xn)中的每个分量xi(1in)都属于一个有限集合Si=ai1, ai2, , airi，因此，回溯法可以按某种顺序（例如字典序）依次考察。 初始时，令解向量X为空，从根结点出发，选择S1的第一个元素作为解向量X的第一个分量，即x1= a11; 如果X=(x1)是问题的部分解，则继续扩展解向量X，选择S2的第一个元素作为解向量X的第2个分量; 否则，选择S1的下一个元素作为解向量X的第一个分量，即x1= a12。 依此类推，一般情况下，如果X=(x1, x2, , xi)是问题的部分解，则选择Si+1的第一个元素作为解向量X的第i+1个分量时，有下面三种情况：,南京信息工程大学,2020/1/29,（1）如果是最终解，则输出这个解。如果问题只希望得到一个解，则结束搜索，否则继续搜索其他解； （2）如果是问题的部分解，则继续构造解向量的下一个分量； （3）如果既不是问题的部分解也不是问题的最终解，则存在下面两种情况： 如果xi+1= ai1,k不是集合Si1的最后一个元素，则令xi+1= ai1,k1，即选择Si+1的下一个元素作为解向量X的第i+1个分量； 如果xi+1= ai1,k是集合Si1的最后一个元素，就回溯到X=(x1, x2, , xi)，选择Si的下一个元素作为解向量X的第i个分量，假设xi= aik，如果aik不是集合Si的最后一个元素，则令xi= ai,k1；否则，就继续回溯到X=(x1, x2, , xi1)；,南京信息工程大学,2020/1/29,回溯法的三个基本步骤 1）定义问题的解空间 2）确定易于搜索的解空间结构 3）深度优先搜索解空间，并在搜索过程中用剪枝函数避免无效搜索,南京信息工程大学,2020/1/29,5.2.3 递归回溯,回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。,void backtrack (int t) if (tn) output(x); else for (int i=f(n, t); i=g(n, t); i+) xt=h(i); if (constraint(t) ,t，当前结点在解空间树中的深度，控制递归深度； n，解空间树的高度； f(n, t)和g(n, t)是未搜索过的子树起始编号和终止编号。,南京信息工程大学,2020/1/29,5.2.4 迭代回溯,采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。,void iterativeBacktrack () int t=1; while (t0) if (f(n, t)=g(n, t) for (int i=f(n, t); i=g(n, t); i+) xt=h(i); if (constraint(t) /回溯 ,南京信息工程大学,2020/1/29,5.2.5 回溯法示例1,子集和数问题 问题 给定由n个不同正数组成的集合W=wi，和正数M，求W中所有和等于M的子集的集合； 问题状态 可以设想，W中的每个数有选取和不选取两种可能，W的一个子集即为一个问题状态，可以表述为对每个元素选取或不选取的一个组合。 问题状态空间树 由空集开始，依次对每个元素进行选取和不选取两种选择，就可以得到W的全部子集，选取过程即可构成一棵状态空间树；,南京信息工程大学,2020/1/29,如：设W=1,5,12,14，则状态空间树如下：,南京信息工程大学,2020/1/29,子集和数问题,按照回溯法思想，从状态树的根结点出发，做深度优先搜索； 为便于计算，将W中的正数按从小到大排序； 当在某一状态A下，依次尝试加入和不加入正数wi， 若A+wiM，则可停止对该结点的搜索； 若A+ (wiwn)M，则也可停止对该结点的搜索；,南京信息工程大学,2020/1/29,子集和数问题,算法如下： 设置辅助向量Ai，记录wi是否被选入； SW表示W的剩余和，SA表示选入项的总和； 初始化Ai = -1，表示未被处理过， SW= Wi， SA=0； 从w0开始，进行深度优先搜索： 检查是否得解以及是否需要继续对该结点进行搜索，如果需要，则 如果Ai为-1（未被处理过），则尝试不选入wi： 置Ai = 0，即：不选入wi； SW -= wi; A+i = -1; 如果Ai为0（未被选入），则尝试选入wi： 置Ai = 1，即： 选入wi； SA += wi; A+i = -1; 如果Ai为1（已被选入），则退回上一项： Ai = -1; SW += wi; SA -= wi; -i;,南京信息工程大学,2020/1/29,回溯法分析,约束集D性质：若 (x1xi)满足D中所有约束(条件)，则其子集(x1xj) jj也不能满足D中，不必再继续搜索问题的解。 回溯求解的效率在很大程度上依赖于：产生局部解(x1xk)的时间；计算约束所需的时间；满足局部约束的解的个数； 通常可以应用重排原理，先搜索分支较少的局部解，在约束不满足时，可以裁剪去较多的搜索分支，从而提高搜索效率。,南京信息工程大学,2020/1/29,示例2：0-1背包问题,给定n个物品和一个背包。设物品i（1in）的重量为wi，其价值为vi，背包最大承重量为Max。问，应该如何选择物品装入背包，才能使背包内物品的总价值最大？选择物品i时，要么全部装入，要么不装入，不能只装入物品i的一部分。,南京信息工程大学,2020/1/29,算法基本思想,如果到达叶子，返回最优解opt；否则， 试探左子树：选取物品i，计算tw，tv；递归，取下一个物品； 回溯，舍去物品i，重新计算tw，tv； 试探右子树：递归，取下一个物品；,南京信息工程大学,2020/1/29,剪枝,约束条件 目标函数 设当前结点i，取该物品，则扩展左子树；舍去该物品，则扩展其右子树 若当前重量tw+wiMax，剪枝，跳过左子树 若当前价值+剩余物品的总价值当前最优价值bestv，则剪枝，跳过右子树,南京信息工程大学,2020/1/29,bestv=tv,iN 如果已到达叶子,T,F,tw+wiMax不超重,tvbestv,T,T,F,F,xi=1; 选取i,扩展左子树, 计算tw，tv,递归BackKnap，试探下一物品i+1,回溯，xi=0舍去i，计算tw，tv,剩余价值+tvbestv,扩展右子树：,递归BackKnap，试探下一物品,return bestv;,opt=x;,舍去,T,F,左子树,右子树,回溯,算法BackKnap,南京信息工程大学,2020/1/29,bestv=tv,iN 如果已到达叶子,T,F,tw+wiMax不超重,tvbestv,T,T,F,F,xi=1; 选取i,扩展左子树, 计算tw，tv,递归BackKnap，试探下一物品i+1,回溯，xi=0舍去i，计算tw，tv,剩余价值+tvbestv,扩展右子树：,递归BackKnap，试探下一物品,return bestv;,opt=x;,舍去,T,F,左子树,右子树,回溯,算法BackKnap(x, opt, tw, tv, i),tv=tv+vi; tw=tw+wi;,BackKnap(x, opt, tw, tv, i+1);,xi=0; tw=tw-wi; tv=tv-vi;,BackKnap(x, opt, tw, tv, i+1);,南京信息工程大学,2020/1/29,bestv=tv,iN,T,F,tw+wiMax,tvbestv,T,T,F,F,xi=1;,tv=tv+vi; tw=tw+wi;,BackKnap(x, opt, tw, tv, i+1);,xi=0; tw=tw-wi; tv=tv-vi;,Bound(i+1)bestv,xi=0;/可不写,BackKnap(x, opt, tw, tv, i+1);,return bestv;,opt=x;,xi=0;,T,F,左子树,右子树,算法BackKnap(x, opt, tw, tv, i),回溯,南京信息工程大学,2020/1/29,0-1背包问题,解空间：子集树 约束条件： 上界函数： Bound（）将剩余物品的价值依次相加，得到右子树最大价值的上界。,int Bound(int i, int tv) / 计算子树价值上界 int vleft = tv; / 依次计算剩余价值之和 for (int j=i; jN; j+) vleft +=vj; return vleft ; ,思考： 能优化吗？,南京信息工程大学,2020/1/29,0-1背包问题,解空间：子集树 约束条件： 上界函数： 更好方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是右子树中价值的上界。,int Bound(int i, int tw, int tv) / 计算子树价值上界 int wleft = Max - tw; / 剩余容量 int vleft = tv; / 以物品单位重量价值递减序装入物品 while (i N ,南京信息工程大学,2020/1/29,0-1背包问题,int Backtrack ( int x, int opt, int tw, int tv,int i ) if (i N) / 到达叶结点 if ( tvbestv )/ 若当前方案的价值更高 bestv = tv; for (int j=0; j bestv) backtrack(x, opt, tw, tv, i + 1); / 进入右子树 return bestv ; ,复杂度分析 计算上界需要O(n)时间，在最坏情况下有O(2n)个右子女结点需要计算上界，故解0-1背包问题的回溯算法backtrack所需的计算时间为O(n2n)。 注：回溯法最坏时间复杂度仍然与穷举法相同。,南京信息工程大学,2020/1/29,例如：n=3,背包容量C=30, w=16, 15, 15, v=45, 25, 25，当前价值V,南京信息工程大学,2020/1/29,思考：怎样化递归为迭代算法,设标志数组flagN： 扩展左子树后，令flagi=1；（进栈） 扩展右子树后，令flagi=2； 左、右子树的情况都处理过，令flagi=3； 回溯时，令flagi=0。（退栈） 当i=N-1时回溯； flagi=3时回溯；i-,南京信息工程大学,2020/1/29,迭代回溯,回溯法的一个非递归迭代过程。,void iterativeBacktrack () int t=1; while (t0) if (f(n, t)=g(n, t) for (int i=f(n, t); i=g(n, t); i+) xt=h(i); if (constraint(t) /回溯 ,南京信息工程大学,2020/1/29,while (i=0) if ( Constraint(i) /end while,部分迭代代码,南京信息工程大学,2020/1/29,课堂练习,（教材P98 例4.4） 输出n个自然数1n的全排列 （教材P99 例4.5） 不重复且无遗漏地产生集合s=1,2,n的全部r子集（s的r个互不相同的元素构成的子集）,南京信息工程大学,2020/1/29,例如：输出1n的全排列，递归表达如下,void f(int k) /已经具备X0Xk-1, 函数目的：求解Xk int i; if(k-1=n) /找到问题的一个解 for(i=0;in;i+) coutXi“ ”; /输出解向量 else for(i=1;in+1;i+) /候选集为1n中没有用过的数 if(!usedi) /usedi=0表示i没有使用过 Xk=i; usedi=1; /i已经使用过 f(k+1); /递归求Xk+1 uesei=0; /f(k+1)结束表示树中第k层子树遍历完 /*即X1Xk确定为某种组合的所有可能排列结果都已出，例如1,2,3,4,1,2,4,3即为x1,x2确定为1,2的所有可能排列结果，所以f(k+1)结束后，会在X1Xk-1不变的情况下，看看除了i以外Xk还有没有其它可用的值*/,南京信息工程大学,2020/1/29,非递归的算法过程如下,void f1( void ) k=1;from=1; i=1; while(k0) for( ;in+1;i+) if(!usedi /*回溯的处理，让第Xk的取值范围变为in，实际上就是Xk+1n */ ,南京信息工程大学,2020/1/29,提醒,13周开始，逢单周（13、15、17） 周二78节继续在Z304上课 补课：5月25日（14周周三）34节，ZN203 上机调整：,南京信息工程大学,2020/1/29,复习 回溯法,回溯法的构成要素 1）解空间树 2）深度优先搜索 3）设法避免搜索无用的分支： 剪枝函数,南京信息工程大学,2020/1/29,走不通，退回去，换条路重走回溯 关键是，设法提前知道走不通,南京信息工程大学,2020/1/29,复习 回溯法的基本思想,从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。 先判断结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，即判断该结点是否包含问题的（最优）解。 如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）； 否则，进入以该结点为根的子树，继续按照深度优先策略搜索。,南京信息工程大学,2020/1/29,复习 回溯法,两种策略避免无效搜索： （1）用约束条件剪去得不到可行解的子树； （2）用目标函数剪去得不到最优解的子树。 这两类函数统称为剪枝函数（Pruning Function）。,南京信息工程大学,2020/1/29,例如，背包问题,约束条件：不能大于包的载重量 若选中该物品超重， 剪枝（舍弃左子树） 目标函数：价值最大 若剩下的物品价值（边界）与当前选中的物品价值总和目前方案的最大价值， 剪枝（舍弃右子树）（剪枝是什么？） 剪枝就是啥也不干,南京信息工程大学,2020/1/29,应用回溯法的三个基本步骤,1）定义问题的解空间 2）确定易于搜索的解空间结构 3）找到剪枝函数（约束、边界），深度优先搜索解空间,南京信息工程大学,2020/1/29,递归回溯,一般情况下用递归方法实现回溯法。,void backtrack (int t) if (tn) output(x); /递归结束条件 else for (int i=f(n, t); i=g(n, t); i+) xt=h(i); if (constraint(t) ,t，当前结点在解空间树中的深度，控制递归深度； n，解空间树的高度； f(n, t)和g(n, t)是未搜索过的子树起始编号和终止编号。,南京信息工程大学,2020/1/29,n后问题,在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。,南京信息工程大学,2020/1/29,为了简化问题，下面讨论四皇后问题。 四皇后问题的解空间树是一棵完全4叉树，树的根结点表示搜索的初始状态，从根结点到第2层结点对应皇后1在棋盘中第1行的可能摆放位置，从第2层结点到第3层结点对应皇后2在棋盘中第2行的可能摆放位置，依此类推。,南京信息工程大学,2020/1/29,4-皇后问题解空间的树结构中，皇后1放在第1列上，若皇后2在第2列上，则皇后2立即被杀死。,南京信息工程大学,2020/1/29,南京信息工程大学,2020/1/29,南京信息工程大学,2020/1/29,再回溯到结点1, 找到了一个4-皇后问题的可行解。,南京信息工程大学,2020/1/29,回溯法求解4皇后问题的搜索过程,南京信息工程大学,2020/1/29,8-皇后问题,8-皇后问题实际上很容易一般化为n-皇后问题，即要求找出一个n*n棋盘上放置n个皇后并使其不能互相攻击的所有方案。 令(x1,x2,xn)表示一个解，由于没有两个皇后可以放入同一列，因此所有的xi将是互不相同的。 那么关键是应如何去测试两个皇后是否在同一条斜角线上,南京信息工程大学,2020/1/29,1 2 3 4 5 6 7 8,1 2 3 4 5 6 7 8,由于解向量之间不能相同，所以解空间的大小由88个元组减少到8!个元组。上图中的解表示为一个8-元组即（4，6，8，2，7，1，3，5）。,南京信息工程大学,2020/1/29,8-皇后问题,如果用二维数组A(1:n,1:n)的下标来标记每个皇后的位置. 同一条斜角线上由左上方到右下方每个元素有相同的“行-列”值 由右上方到左下方的有相同的“行+列”值。,南京信息工程大学,2020/1/29,8-皇后问题,假设有两个皇后被放置在(i，j)和(k，l)位置上，那么根据以上所述，仅当 i j = k - l 或 i + j = k + l 时，它们才在同一条斜角线上。,南京信息工程大学,2020/1/29,将这两个等式分别变换成 j - l = i - k 或 j - l = k - i 因此，当且仅当 |j- l| = |i-k| 时（即两个皇后所在位置的行差距等于列差距时），两个皇后在同一条斜角线上。,南京信息工程大学,2020/1/29,假设有两个皇后被放置在(i，j)和(k，l)位置上 约束条件1：不能放在同一列 jl 约束条件2：不能放在同一斜角线 |j- l| |i-k|,南京信息工程大学,2020/1/29,算法：可以放置一个新皇后吗？,Procedure PLACE(k) /如果一个皇后能放在第k行和X(k)列，则返回true，否则返回false。X是一个全局数组，进入此过程时已置入了k个值。ABS(r)过程返回r的绝对值/ 数组 Xk; integer i,k; i1 while ( ik ) if ( Xi=Xk or ABS(Xi-Xk)=ABS(i-k) ) return (false) ii+1 return (true) End PLACE,判断是否有其它的皇后与之在同一列或同一斜对角线上,南京信息工程大学,2020/1/29,递归回溯：,n后问题,bool Queen:Place(int k) for (int i=1;ik;i+) if ( (abs(i-k)=abs(xi-xk) | (xi=xk) ) return false; return true; ,南京信息工程大学,2020/1/29,递归回溯：,n后问题,void Queen:Backtrack(int t) if (tn) sum+; else for (int i=1;i=n;i+) xt=i; if (Place(t) Backtrack(t+1); ,南京信息工程大学,2020/1/29,迭代回溯：,n后问题,void Queen:Backtrack(int t) x1=0; int k=1; while (k0) xk+=1; while ( (xk=n) ,南京信息工程大学,2020/1/29,马跳棋盘（骑士游历）,n×n的棋盘，马（骑士）从棋盘某格开始，按照“马走日”规则走过每格恰好一次，走完棋盘所有的格，求移动路线。 “日字”：先垂直或水平移动2格，再水平（垂直）走一格。,南京信息工程大学,2020/1/29,南京信息工程大学,2020/1/29,讨论,怎么解决？,南京信息工程大学,2020/1/29,首先，怎样描述？ 1.坐标 骑士位置（x，y） 棋盘范围1, N 或者0, N-1,南京信息工程大学,2020/1/29,2.“马走日”的表示 8个位置 (x+2, y+1) (x+1, y+2) (x-1, y+2 ) (x-2, y+1) (x-2, y-1 ) (x-1, y-2) (x+1, y-2) (x+2, y-1),南京信息工程大学,2020/1/29,3.怎样知道某位置已经 “走过了”？ 设标志位 若没走过，flagxy=0； 若走过了，flagxy0；,南京信息工程大学,2020/1/29,4.怎样描述一个可行的路线？ 用一个数组记录，与棋盘位置对应 若在第i步走到位置(x, y) flagxy=i,南京信息工程大学,2020/1/29,第二，从哪个位置开始走？ (1, 1) 按什么顺序走？怎样取“下一个”位置 深度优先遍历 简单的，穷举8个位置,南京信息工程大学,2020/1/29,接下来干什么？ 第三，穷举 如果某一步可继续走下去，就试探着走下去且考虑下一步的走法，若走不通则返回，考虑另选一个位置,南京信息工程大学,2020/1/29,第四，怎样避免无效的搜索？ 约束函数 棋盘n×n，数组下标范围0, N-1 0xN， 并且0yN 并且，没走过， flagxy=0,南京信息工程大学,2020/1/29,应用回溯法的三个基本步骤,1）定义问题的解空间 2）确定易于搜索的解空间结构 3）找到剪枝函数（约束、边界），深度优先搜索解空间,南京信息工程大学,2020/1/29,解的形式 二维数组flag,南京信息工程大学,2020/1/29,procedure trynextstep(i) begin 选择准备； repeat 个位置中选一个； if 选择可接受 then begin 记录移动情况； if 棋盘未遍历完 then begin trynextstep(i+1) ； if 试探不成功 then 删去以前的记录 回溯 end end until ( 移动成功 ) or ( 再无别的选择 ) end ；,南京信息工程大学,2020/1/29,小结,子集和数与0-1背包问题的解都是子集树 n皇后问题的解是排列树 回溯还可解决迷宫问题、旅行商问题等,南京信息工程大学,2020/1/29,提醒,13周开始，逢单周（13、15、17） 周二78节继续在Z304上课 补课：5月25日（14周周三）34节，ZN203 上机：,