第第5 5章章 回溯法回溯法上海大学计算机学院上海大学计算机学院学习要点与要求学习要点与要求掌握与理解回溯法的掌握与理解回溯法的DFS搜索策略与方法搜索策略与方法（1掌握递归回溯掌握递归回溯（2理解迭代回溯编程技巧理解迭代回溯编程技巧掌握用回溯法解题的算法框架，了解搜索过程掌握用回溯法解题的算法框架，了解搜索过程（1子集树算法框架子集树算法框架（2排列树算法框架排列树算法框架通过学习典型范例，掌握回溯法的设计策略通过学习典型范例，掌握回溯法的设计策略（1装载问题装载问题 （2批处理作业调度批处理作业调度3n后问题后问题（40-1背包问题背包问题 （5最大团问题最大团问题（6图的图的m着色问题着色问题7旅行售货员问题旅行售货员问题 n皇后问题皇后问题 国际象棋中的国际象棋中的“皇后在横向、直向、和斜向都皇后在横向、直向、和斜向都能走步和吃子，问在能走步和吃子，问在nn 格的棋盘上如何摆上格的棋盘上如何摆上n个个皇后而使她们都不能相互吃掉？皇后而使她们都不能相互吃掉？引引 言言穷举法：穷举法： n=4时，有时，有n！=24中情况中情况N皇后搜索过程与多叉树皇后搜索过程与多叉树0x4=412271810513315911614416x2=2x2=4x2=3x3=3x3=4x3=2x3=4 x3=2x3=3x4=3x4=4x4=2x4=3 x4=2x1=1x1=2x1=3x1=41 2 3 4x1x2x3x4迷宫问题迷宫问题演示演示5.1 5.1 回溯法的算法框架回溯法的算法框架问题的解空间1）1. 解向量：问题的解用向量表示解向量：问题的解用向量表示 (x1, x2, , xk) 其中其中k n, n为问题的规模。为问题的规模。 2. 约束条件约束条件 1显式约束：对分量显式约束：对分量xi的取值的明显限定。的取值的明显限定。 2隐式约束：为满足问题的解而对不同分量之隐式约束：为满足问题的解而对不同分量之间施加的约束。间施加的约束。 3. 解空间：对于问题的一个实例，解向量满足显式解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一约束条件的所有多元组，构成了该实例的一个解空间。个解空间。问题的解空间2） 4、状态空间树、状态空间树 用于形象描述解空间的树。用于形象描述解空间的树。 5、目标函数与最优解、目标函数与最优解 1. 目标函数：衡量问题解的目标函数：衡量问题解的“优劣规范。优劣规范。 2. 最优解：使目标函数取极大最优解：使目标函数取极大/小值的解。小值的解。n=3时的时的0-1背包问题用完全二叉树表示的解空间背包问题用完全二叉树表示的解空间搜索状态空间树的两种策略搜索状态空间树的两种策略 1. 以深度优先方式系统搜索问题的解以深度优先方式系统搜索问题的解-回溯法回溯法 2. 以广度优先方式搜索问题的解以广度优先方式搜索问题的解-分支分支-限界法限界法几种搜索过程中涉及的结点：几种搜索过程中涉及的结点：扩展结点：一个正在产生儿子的结点称为扩展结点扩展结点：一个正在产生儿子的结点称为扩展结点活结点：一个自身已生成但其儿子还没有全部生成的节活结点：一个自身已生成但其儿子还没有全部生成的节点称做活结点点称做活结点死结点：一个所有儿子已经产生的结点称做死结点死结点：一个所有儿子已经产生的结点称做死结点回溯法回溯法1.1.基本方法：利用限界函数来避免生成那些实际上基本方法：利用限界函数来避免生成那些实际上不可能产生所需解的活结点，以减少问题的计算不可能产生所需解的活结点，以减少问题的计算量，避免无效搜索。量，避免无效搜索。2.2.限界函数：用于剪枝限界函数：用于剪枝3.3.(1)(1)约束函数：某个满足条件的表达式或关系式。约束函数：某个满足条件的表达式或关系式。4.4. 不真时用于在扩展结点处剪去不满足约束的不真时用于在扩展结点处剪去不满足约束的子树；子树；5.5.(2)(2)限界函数：某个函数表达式或关系式。限界函数：某个函数表达式或关系式。6.6. 不真时，用于剪去得不到最优解的子树。不真时，用于剪去得不到最优解的子树。7.7.回溯法：具有限界函数的深度优先搜索方法回溯法：具有限界函数的深度优先搜索方法回溯法的基本思想回溯法的基本思想1.以深度优先方式搜索解空间。以深度优先方式搜索解空间。2.开始时，根结点为活结点，也是当前的扩展结点。开始时，根结点为活结点，也是当前的扩展结点。3.对扩展结点，寻找儿子结点：对扩展结点，寻找儿子结点：4. 如找到新结点，新结点成为活结点并成为扩展如找到新结点，新结点成为活结点并成为扩展结点。转结点。转3；5. 如找不到新结点，当前结点成为死结点，并回如找不到新结点，当前结点成为死结点，并回退到最近的一个活结点，使它成为扩展结点。转退到最近的一个活结点，使它成为扩展结点。转3；6.搜索继续进行，直到找到所求的解或解空间中已无搜索继续进行，直到找到所求的解或解空间中已无活结点时为止。活结点时为止。n=3n=3时的时的0-10-1背包问题：背包问题：c=30,w=16,15,15,v=45,25,25c=30,w=16,15,15,v=45,25,25 搜索过程举例搜索过程举例-0-1-0-1背包问题背包问题搜索过程举例搜索过程举例旅行商问题旅行商问题TSPG=(V，E)，|V|=n1234301020654总路径数：总路径数：对称情况：对称情况： (n-1)!/2非对称情况：非对称情况：(n-1)!回溯法解题步骤回溯法解题步骤(1)(1)针对所给问题，定义问题的解空间；针对所给问题，定义问题的解空间；(2)(2)确定合适的解空间结构；确定合适的解空间结构；(3)(3)以深度优先方式搜索解空间，并在搜索过程以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索，直到找到所求的中用剪枝函数避免无效搜索，直到找到所求的解或解空间中已无活结点时为止。解或解空间中已无活结点时为止。回溯法形式描述回溯法形式描述-递归算法递归算法void BACKTRACK(int t ) /n为递归深度为递归深度,t为当前深度为当前深度 if （t n前往前往; else while (存在合适的存在合适的xt ) if (x1,xt)是解是解 输出解输出解x1,xt ； BACKTRACK( t + 1 ); 另一种方式另一种方式for(int i=f(n,t);i 0) if (有有xt，满足，满足 约束约束C(x1,x t) &限界限界Bound(x1,xt) if (x1,xt)是问题的一个是问题的一个“解解”) 那么那么 输出解输出解(x1,xt )； else t= t + 1 /“深化深化 ”一步一步 else t= t - 1 ; / “回退一步回退一步 if (f(n,t)=g(n,t) for (int i=f(n,t);i=g(n,t);i+) xt=h(i); if (Constraint(t)&Bound(t) if (solution(t) output(x); else t+; 子集树与排列树子集树与排列树留意：留意：2nn) output(x); else for (int i=0;in) output(x); else for (int i=t;i n) / 到达叶结点到达叶结点 /修正最优值修正最优值 if (cw + wi = c) / 搜索左子树搜索左子树 backtrack(i + 1); /回退回退 backtrack(i + 1); / 搜索右子树搜索右子树 设设cw：是当前载重量：是当前载重量 bestw：当前最优载重量：当前最优载重量约束函数：约束函数： cw + wi cw + wi = c bestw) bestw=cw;cw -= wi;程序程序求最优值求最优值void backtrack (int i) / 搜索第搜索第i层结点层结点 if (i n) / 到达叶结点到达叶结点 if (cwbestw) bestw=cw; /修正最优值修正最优值 return; if (cw + wi = c) / 搜索左子树搜索左子树 cw += wi; backtrack(i + 1); cw -= wi; /回退回退 backtrack(i + 1); / 搜索右子树搜索右子树 设设cw：是当前载重量：是当前载重量 bestw：当前最优载重量：当前最优载重量约束函数：约束函数： cw + wi cw + wi = c bestwvoid backtrack (int i) / 搜索第搜索第i层结点层结点 if (i n) / 到达叶结点到达叶结点 if (cwbestw) bestw=cw; return; r -= wi; if (cw + wi bestw ) / 搜索右子树搜索右子树 backtrack(i + 1); r += wi; r -= wi;cw + r bestwr += wi;void backtrack (int i) / 搜索第搜索第i层结点层结点 if (i n) / 到达叶结点到达叶结点 更新最优解更新最优解bestx,bestw;return; r -= wi; if (cw + wi bestw) xi = 0; / 搜索右子树搜索右子树 backtrack(i + 1); r += wi; 求最优解求最优解记录路径记录路径 if (cwbestw) for(int j=1; j=n; j+)bestxj=xj; bestw=cw;xi = 1;xi = 0;迭代回溯迭代回溯将回溯法表示成非递归的形式将回溯法表示成非递归的形式 算法算法MaxloadingMaxloading所需的计算时间仍为所需的计算时间仍为O(2n)O(2n)。 程序程序 优化：修改递归回溯程序，使所需的计算时间仍优化：修改递归回溯程序，使所需的计算时间仍为为O(2n)O(2n)。ype Maxloading(Type w, Type c, int n, int bestx) /返回最优载重量及解返回最优载重量及解 int i = 1; /当前层当前层, x1:i-1 为当前路径为当前路径 /初始化根结点初始化根结点 int *x = new int n + 1; Type bestw =0, cw =0, r = 0; /当前最优载重量当前最优载重量; 当前载重量当前载重量,剩余集装箱重量剩余集装箱重量 for (int j = 1; j = n; j +) r += wj; /计算集装箱总重量计算集装箱总重量 while (true) /搜索子树搜索子树 while (i = n & cw + wi n)&(bestw cw) for (int j = 1; j = n; j+) bestxj = xj; bestw = cw;else/进入右子树进入右子树 r -= wi; xi = 0; i +; /cw不变不变while (cw + r 0 & !xi) /从右子树返回从右子树返回 r += wi; i -; if (i = 0) delete x; return bestw; /进人右子树进人右子树 xi =0; cw -= wi;i +; 5.3 5.3 批处理作业调度批处理作业调度批处理作业调度问题描述批处理作业调度问题描述给定给定n个作业的集合个作业的集合J=J1,J2,Jn。每个作业必。每个作业必须先由机器须先由机器M1处理，然后由机器处理，然后由机器M2处理。作业处理。作业Ji需要机器需要机器j的处理时间为的处理时间为tji。对于一个确定的作业。对于一个确定的作业调度，设调度，设Fji是作业是作业i在机器在机器j上完成处理的时间。上完成处理的时间。f= 所有作业在机器所有作业在机器M2上完成处理的时间和称为该作上完成处理的时间和称为该作业调度的完成时间和。业调度的完成时间和。 批处理作业调度问题要求对于给定的批处理作业调度问题要求对于给定的批处理作业调度问题要求对于给定的批处理作业调度问题要求对于给定的n n n n个作业，制个作业，制个作业，制个作业，制定最佳作业调度方案，使其完成时间和达到最小。定最佳作业调度方案，使其完成时间和达到最小。定最佳作业调度方案，使其完成时间和达到最小。定最佳作业调度方案，使其完成时间和达到最小。实例实例共有3！=6种调度方案，例tjiM1M2J121J231J323调度123 f=3+6+10=19 调度132 f=3+7+8=18 调度213 f=4+6+10=20 最佳调度方案是最佳调度方案是1,3,2，其完成时间和为，其完成时间和为18。算法设计算法设计设设x1.nx1.n是是n n个作业，解空间为排列树个作业，解空间为排列树需从排列树中找出一个解即作业排列）需从排列树中找出一个解即作业排列）设设bestxbestx是返回的最佳作业调度，是返回的最佳作业调度，bestfbestf是当前是当前最小完成时间最小完成时间12271810513315911614416x1=1x1=3x1=2x2=2x2=3x2=1x2=3 x2=1x2=2x3=3x3=3x3=1x3=2x3=2x3=1算法设计算法设计尝试将尝试将x1x1（取值（取值1 1、2 2、n n先排入作业队列，先排入作业队列，计算完成计算完成x1x1所需的所需的M1M1上的作业时间上的作业时间f11f11，M2M2上上做完所需的时间做完所需的时间f21 f21 。选择一个使。选择一个使f21 f21 最小最小的安排。的安排。假定现在已安排好前假定现在已安排好前i-1i-1个作业，个作业，M1M1、M2M2上作业时上作业时间为间为f1i-1f1i-1、 f2i-1 f2i-1 。现在考虑第现在考虑第i i个作业。在没有安排的作业中任选一个作业。在没有安排的作业中任选一个进行考察，即取个进行考察，即取 xj xj。图示分析图示分析情况1M1M2f2i-1初步安排好前初步安排好前i-1i-1个作业，个作业，作业时间为作业时间为f1i-1f1i-1f1i尝试作尝试作业业xjm1xjm1xjm2xjm2xjf2ij=i,i+1,n依次f2i-1初步安排好前初步安排好前i-1i-1个作业，个作业，作业时间作业时间f1i-1f1i-1f1i尝试作尝试作业业xjm1xjm1xjm2xjm2xjf2ij=i,i+1,n情况2M1M2尚未完成，需等尚未完成，需等已完成，不必等已完成，不必等f2if2i的计算的计算 f1= f1 + mxj1; f1= f1 + mxj1; f2i=(f2i-1f1)? f2i-1:f1) f2i=(f2i-1f1)? f2i-1:f1) +mxj2 +mxj2 对j=i,i+1,n依次尝试算法框架算法框架void backtrack (int i) if (in) output(x); /记录或修正解记录或修正解 else for (int j=i;j n) for (int j = 1; j = n; j+) bestxj = xj; bestf = f; else for (int j = i; j f1)?f2i-1:f1) +mxj2; f+=f2i; if (f bestf) swap(x,i,j); backtrack(i+1); swap(x,i,j); f1-=mxj1; f-=f2i; 有关的变量定义，可用类定义 int n, / 作业数 f1, / 机器1完成处理时间 f, / 完成时间和 bestf; / 当前最优值 int *m; / 各作业所需的处理时间 int *x; / 当前作业调度 int *bestx; / 当前最优作业调度 int *f2; / 机器2完成处理f= 限界函数：限界函数：初始化、调用、算法复杂性初始化、调用、算法复杂性初始作业队列初始作业队列12341234n n，bestf=bestf=无穷大无穷大调用调用Backtrack(1)Backtrack(1)时间复杂性时间复杂性O(n!)O(n!)练习：确定批处理作业最佳作业调度方案，使其练习：确定批处理作业最佳作业调度方案，使其完成时间和达到最小。完成时间和达到最小。tjiM1M2J157J2105J397J4585.5 n后问题n皇后问题描述皇后问题描述在在nn格的棋盘上放置彼此不受攻击的格的棋盘上放置彼此不受攻击的n个皇后。按照国际个皇后。按照国际象棋的规则，皇后可以攻击与它处在同一行或同一列或同一象棋的规则，皇后可以攻击与它处在同一行或同一列或同一斜线上的棋子。斜线上的棋子。n后问题等价于在后问题等价于在nn格的棋盘上放置格的棋盘上放置n个皇个皇后，任何后，任何2个皇后不放在同一行或同一列或同一斜线上。个皇后不放在同一行或同一列或同一斜线上。1 2 3 4 5 6 7 812345678QQQQQQQQ算法分析算法分析1、设定解向量：、设定解向量：(x1, x2, , xn)，采用排列树，采用排列树 2、约束条件、约束条件 （1显式约束：显式约束：xi = 1, 2, , n (i = 1,2, , n) （2隐式约束隐式约束 1) “不同列不同列”：xi xj (i,j = 1, 2, ,n; i j) 2)不处于同一正、反对角线：不处于同一正、反对角线：|i-j|xi-xj|bool place (int k) for (int j=1;jn) sum+; else for (int i=1;i 0) xk = xk + 1; while( (xk = n) &!place(k) /当前位置不合适当前位置不合适 xk= xk + 1; /尝试下一个位置尝试下一个位置 if (xk = n) if (k = n) sum+; else /设置禁止放置皇后的设置禁止放置皇后的“标志标志”； k= k + 1; xk= 0 else k -; 练习：给定练习：给定n，输出，输出几组解几组解这是迭代回溯法的很好例子，这是迭代回溯法的很好例子，应学好应学好统计解数统计解数5.6 0-15.6 0-1背包问题背包问题 算法分析算法分析0-10-1背包问题属于子集选取问题背包问题属于子集选取问题解空间：子集树解空间：子集树可行性约束函数：可行性约束函数：限界函数估计即上界函数，仿一般背包问题）：限界函数估计即上界函数，仿一般背包问题）： 以物品单位重量价值递减序装入物品；整个装不以物品单位重量价值递减序装入物品；整个装不下时，再装该物体的一部分，而把背包装满，求得可能下时，再装该物体的一部分，而把背包装满，求得可能的最大价值。的最大价值。例：例：n=4,c=7,v=9,10,7,4, w=3,5,2,1n=4,c=7,v=9,10,7,4, w=3,5,2,1单位重量价值：单位重量价值：9/3, 10/5, 7/2, 4/19/3, 10/5, 7/2, 4/1降序排列后，先装物品降序排列后，先装物品4 4重重=1=1），再装物品），再装物品3 3重重=2=2），），物品物品1 1重重=3=3），再装物品），再装物品2 2的一部分重的一部分重=1=1），），最大价值最多为最大价值最多为2222。上界或限界函数计算上界或限界函数计算double bound(int i) / 计算上界计算上界 double cleft = c - cw; / 剩余容量剩余容量 double bnd = cp; / cp：当前价值：当前价值 while (i = n & wi = cleft) / 以物品单位重量价值递减序装入物品以物品单位重量价值递减序装入物品 cleft -= wi; bnd += pi; i+; / 背包有空隙时，装满背包背包有空隙时，装满背包 if (i cleft) bnd += pi / wi * cleft; return bnd; 回溯程序回溯程序Backtrackc：背包容量：背包容量 n：物品数：物品数 w：物品重量数组：物品重量数组p：物品价值数组：物品价值数组 cw：当前重量：当前重量 cp：当前价值：当前价值bestp：当前最优价值：当前最优价值 void Backtrack(int i) if (i n) bestp = cp; return; if (cw + wi bestp) / xi = 0，否则剪去右枝，否则剪去右枝 Backtrack(i + 1); 约束函数：约束函数： cw + wi 限界函数：限界函数： Bound(i + 1) 0-10-1背包问题的搜索树背包问题的搜索树在操作时可采取剪枝技术：在操作时可采取剪枝技术： 在在Bound(i + 1) bestp前提下，当前提下，当cp+r n) / 到达叶结点到达叶结点 for (int j = 1; j = n; j+) bestxj = xj; bestn = cn; return; / 检查顶点检查顶点 i 与当前团的连接与当前团的连接 int ok = 1; for (int j = 1; j bestn) / 进入右子树进入右子树 xi = 0; backtrack(i + 1); 12453限界函数限界函数最大团问题复杂性算法改进设想：算法改进设想： 选择合适的搜索顺序，可以使得上界函数更选择合适的搜索顺序，可以使得上界函数更有效地发挥作用。如在搜索之前可将顶点按度有效地发挥作用。如在搜索之前可将顶点按度从小到大排序。这在某种意义上相当于给回溯从小到大排序。这在某种意义上相当于给回溯法加入了启发性。法加入了启发性。复杂度分析复杂度分析 最大团问题的回溯算法最大团问题的回溯算法backtrack所需的计所需的计算时间显然为算时间显然为O(n2n)。5.8 图的图的m着色问题着色问题问题描述问题描述给定无向连通图G和m种不同的颜色。顶点着色：用顶点着色：用m m种颜色为图种颜色为图G G的各顶点着色，每的各顶点着色，每个顶点着一种颜色。每条边的个顶点着一种颜色。每条边的2 2个顶点着不同个顶点着不同颜色。颜色。边着色：用这些颜色为图边着色：用这些颜色为图G G的各边着色，每边的各边着色，每边着一种颜色。与每顶点关联的边着不同颜色。着一种颜色。与每顶点关联的边着不同颜色。面着色：用这些颜色为图面着色：用这些颜色为图G G的各面着色，每个的各面着色，每个面着一种颜色。相邻的面着一种颜色。相邻的2 2个面着不同颜色。个面着不同颜色。顶点着色与面着色71235643421567问题描述问题描述图的图的图的图的mm着色问题：是否有一种着色法使着色问题：是否有一种着色法使着色问题：是否有一种着色法使着色问题：是否有一种着色法使GG中每中每中每中每条边的条边的条边的条边的2 2个顶点着不同颜色。个顶点着不同颜色。个顶点着不同颜色。个顶点着不同颜色。图的图的图的图的 m m可着色优化问题：求一个图的色数可着色优化问题：求一个图的色数可着色优化问题：求一个图的色数可着色优化问题：求一个图的色数mm的的的的问题称为图的问题称为图的问题称为图的问题称为图的mm可着色优化问题。可着色优化问题。可着色优化问题。可着色优化问题。图的四色问题：用至多四种颜色可对一个图进图的四色问题：用至多四种颜色可对一个图进图的四色问题：用至多四种颜色可对一个图进图的四色问题：用至多四种颜色可对一个图进行面着色。（行面着色。（行面着色。（行面着色。（19761976年解决）年解决）年解决）年解决）算法分析解向量：解向量：(x1, x2, , xn)表示顶点表示顶点i所着颜色所着颜色xi 可行性约束函数：顶点可行性约束函数：顶点i与已着色的相邻顶点颜色不重与已着色的相邻顶点颜色不重复。复。void backtrack(int t) if (tn) sum+;输出解输出解 else for (int i=1;i=m;i+) xt=i; if (ok(t) backtrack(t+1); n：图的顶点数：图的顶点数m：可用颜色数：可用颜色数x：当前解：当前解sum：当前已找到的可：当前已找到的可m着色方案数着色方案数bool ok(int k) / 检查颜色可用性检查颜色可用性 for (int j=1;j=n;j+) if (akj & (xj=xk) return false; return true; 跟跟n皇后皇后问题类似问题类似思索：用迭代回溯如何实现？思索：用迭代回溯如何实现？复杂度分析复杂度分析图图m可着色问题的解空间树中内结点个数是可着色问题的解空间树中内结点个数是对于每一个内结点，在最坏情况下，用对于每一个内结点，在最坏情况下，用ok检查当检查当前扩展结点的每一个儿子所相应的颜色可用性需前扩展结点的每一个儿子所相应的颜色可用性需耗时耗时O(mn)。因此，回溯法总的时间耗费是。因此，回溯法总的时间耗费是思索思索 图的图的m着色问题与图的最大团问题有何着色问题与图的最大团问题有何关系，你能否利用这个关系改进最大团关系，你能否利用这个关系改进最大团问题的上界？问题的上界？作业上机实验：实验七上机实验：实验七上机实验：实验七上机实验：实验七 最优装载问题分析题最优装载问题分析题最优装载问题分析题最优装载问题分析题5-15-15-15-1或或或或5-25-25-25-2） 书面作业：书面作业：书面作业：书面作业：分析题分析题分析题分析题5-35-35-35-3写出修改后的程序，加注释）写出修改后的程序，加注释）写出修改后的程序，加注释）写出修改后的程序，加注释）实现题实现题实现题实现题5-45-45-45-4，5-165-165-165-16作简要分析后写程序）作简要分析后写程序）作简要分析后写程序）作简要分析后写程序）实现题实现题实现题实现题5-225-225-225-22，5-235-235-235-23：两个题需写出问题描述中所：两个题需写出问题描述中所：两个题需写出问题描述中所：两个题需写出问题描述中所说的三种函数，写一个程序框架。说的三种函数，写一个程序框架。说的三种函数，写一个程序框架。说的三种函数，写一个程序框架。