北京大学：《数据结构与算法》课程教学资源（实习讲义）回溯（Backtracking）基本原理

认识“回溯” 感性认识—皇后问题 解空间树 搜索过程 回溯( Backtracking)基本原理 直观分析 原理描述 2007年9月26日 ■总体步骤 搜索过程 张铭 实现方式 方式一:递归回溯 方式二:选代回溯 效率分析 八皇后问题 八皇后问题的一个解图示 问题描述:在国际象棋的8*8格棋盘上放置8 个皇后,使任意两个皇后不在同一行上,不在 同一列上,不在同一条斜角线上。 设第1个皇后放在第一行的x1位置,第个皇后 lQ对应的向量 放在第行的x位置,则八皇后问题的一个解可 Q 以表示为一个向量(x1,X2y…X)显然 (4,6,8,2,71,3,5) x1x2y…x8是(1,2灬8)的一个排列;所有可 能的向量(可能解)有8!个 回滴算法 衡算法 四皇后问题及其解空间树 解空间树 解表示成一个4维向量, (放量列号 中的每一个结点确定所求解问题的一个问题状态 搜索空间:4又树(排列树) 由根结点到其它结点的所有路径则确定了这个问题的 状态空间( state space 答案状态( answer states)是这样的一些解状态s 题的一个解(即,它满足隐式约束条件) 解空间的树结构称为状态空间树( state space tree) 00的明的9的的的的

回溯算法 1 回溯(Backtracking)基本原理 2007年9月26日 张铭 回溯算法 2 认识“回溯” „ 感性认识——皇后问题 „ 解空间树 „ 搜索过程 „ 直观分析 „ 原理描述 „ 总体步骤 „ 搜索过程 „ 实现方式 „ 方式一：递归回溯 „ 方式二：迭代回溯 „ 效率分析 回溯算法 3 八皇后问题 „ 问题描述：在国际象棋的8*8格棋盘上放置8 个皇后，使任意两个皇后不在同一行上，不在 同一列上，不在同一条斜角线上。 „ 设第1个皇后放在第一行的x1位置，第i个皇后 放在第i行的xi 位置，则八皇后问题的一个解可 以表示为一个向量(x1,x2,...,x8);显然 x1,x2,...x8是(1,2,...,8)的一个排列；所有可 能的向量（可能解）有8!个 回溯算法 4 八皇后问题的一个解图示 Q Q Q Q Q Q Q Q 对应的向量： (4,6,8,2,7,1,3,5) 回溯算法 5 四皇后问题及其解空间树 1 2 4 3 5 6 7 4 3 9 8 10 11 12 2 4 4 2 3 14 13 15 16 17 2 3 3 2 4 X1=1 18 20 19 21 22 23 3 4 4 3 1 25 24 26 27 28 1 4 4 1 3 30 29 31 32 33 1 3 3 1 4 2 34 36 35 37 38 39 2 4 4 2 1 41 40 42 43 44 1 4 4 1 2 46 45 47 48 49 1 2 2 1 4 3 50 52 51 53 54 55 2 3 3 2 1 57 56 58 59 60 1 3 3 1 2 62 61 63 64 65 1 2 2 1 3 4 X2=2 X3=3 X4=4 Q Q Q Q „ 解表示成一个4维向量， （放置列号） „ 搜索空间：4叉树（排列树） 回溯算法 6 解空间树 „ 树中的每一个结点确定所求解问题的一个问题状态 （problem states）。 „ 由根结点到其它结点的所有路径则确定了这个问题的 状态空间（state space）。 „ 解状态（solution states）是这样一些问题状态S， 对于这些问题状态，由根到S的那条路径确定了这解空 间中的一个元组。 „ 答案状态（answer states）是这样的一些解状态S， 对于这些解状态而言，由根到S的这条路径确定了这问 题的一个解（即，它满足隐式约束条件）。 „ 解空间的树结构称为状态空间树（state space tree）

四皇后问题的解空间树 直观分析一搜索代价 四皇后问题的状态空间树上共有24个叶 时间代价 结点(4)就是问题的所有可能解 空间树共有65个结点,24个叶结点,但在搜紫过 树的内部结点代表问题的部分解;例如 程中,只遍历了16个绪点,其中2个叶结点 36为部分解(x1X2X3)=(312) 如果要找所有解的话,则还要繼续搜紫下去 ■结点的编号是按DFs( Deep First ■空间代价 Search)方式排列的,其实也就是按回 与树的高度有关,而不是和树的总结点数有关 溯方式遍历搜索的次序 回溯算法中,并不需要真正创建一个解空间树 原理描述一问题的解空间 原理描述一生成问题状态的基本方法 ■问题的解向量:回溯法希望一个问题的 扩展结点:个正在产生儿子的结点称为扩展结点 解能够表示成一个n元式(x1x2y…Xn)的 活结点:一个自身已生成但其儿子还没有全部生成的结 形式。 点称做活结点 显约束:对分量x的取值限定 死结点:一个所有儿子已经产生的结点称做死结点 问题状态生成法 ■隐约束:为满足问题的解而对不同分量 间施加的约束。 c,就把c当做新的扩展结点。在完成对子树c(以c为根的子 ■解空间:对于问题的一个实例,解向量 满足显式约束条件的所有多元组,构成 宽度优先:在一个扩展结点变成死结点之前,它一直是扩晨 站点—分支定界法 了该实例的一个解空间。 回滴算法 原理描述一回溯法的基本思想 结点分支判定条件: 基本思想: 满足约束条件-分支扩张解向量 (1)针对所给问题,定义问题的解空间 不满足约束条件,回溯到该结点的父结点 (2)确定易于搜家的解空间结构 ■结点状态:动态生成 )以源度优先方式搜索解空间,并在搜索过程中 三种: 常用剪枝函数 a尚未访问 用约束函数在扩展结点处剪去不满足约束的子树; b正在访问该结点为根的子树(活动结点、扩展 结点) c该结点为根的子树遍历完成 ■递归回溯vs选代回溯 存储:当前路径

回溯算法 7 四皇后问题的解空间树 „ 四皇后问题的状态空间树上共有24个叶 结点(4!),就是问题的所有可能解， „ 树的内部结点代表问题的部分解；例如 36为部分解(x1,x2,x3)=(3,1,2) „ 结点的编号是按DFS（Deep First Search)方式排列的，其实也就是按回 溯方式遍历搜索的次序 回溯算法 8 直观分析—搜索代价 „ 时间代价 „ 空间树共有65个结点，24个叶结点，但在搜索过 程中，只遍历了16个结点，其中2个叶结点 „ 如果要找所有解的话，则还要继续搜索下去 „ 空间代价 „ 与树的高度有关，而不是和树的总结点数有关 „ 回溯算法中，并不需要真正创建一个解空间树 回溯算法 9 原理描述—问题的解空间 „ 问题的解向量：回溯法希望一个问题的 解能够表示成一个n元式(x1,x2,…,xn)的 形式。 „ 显约束：对分量xi 的取值限定。 „ 隐约束：为满足问题的解而对不同分量 之间施加的约束。 „ 解空间：对于问题的一个实例，解向量 满足显式约束条件的所有多元组，构成 了该实例的一个解空间。 回溯算法 10 原理描述—生成问题状态的基本方法 „ 扩展结点:一个正在产生儿子的结点称为扩展结点 „ 活结点:一个自身已生成但其儿子还没有全部生成的结 点称做活结点 „ 死结点:一个所有儿子已经产生的结点称做死结点 „ 问题状态生成法： „ 深度优先：如果对一个扩展结点R，一旦产生了它的一个儿子 C，就把C当做新的扩展结点。在完成对子树C（以C为根的子 树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的 下一个儿子（如果存在）——回溯法 „ 宽度优先：在一个扩展结点变成死结点之前，它一直是扩展 结点——分支定界法 回溯算法 11 „ 结点分支判定条件： 满足约束条件---分支扩张解向量 不满足约束条件，回溯到该结点的父结点 „ 结点状态：动态生成 三种： a 尚未访问 b 正在访问该结点为根的子树（活动结点、扩展 结点） c 该结点为根的子树遍历完成 „ 存储：当前路径 回溯算法 12 原理描述—回溯法的基本思想 „ 基本思想： „ (1)针对所给问题，定义问题的解空间； „ (2)确定易于搜索的解空间结构； „ (3)以深度优先方式搜索解空间，并在搜索过程中 用剪枝函数避免无效搜索。 „ 常用剪枝函数 „ 用约束函数在扩展结点处剪去不满足约束的子树； „ 对于优化问题，还可以用限界函数(Bounding Function)处死那些实际上不可能产生所需解的活 结点，也就是剪去得不到最优解的子树。 „ 递归回溯 vs 迭代回溯

方式一:递归回溯 递归回溯算法解释 取减定還的猿数件定聚句對 x[O:t- /tn时,算法已经到叶结点 在当前扩展结点 for( inti=f(n, t);i<=g(n, t); i++) /f和gO:当前扩晨点子拥特处的超点与络点 子树进一步搜索;否则,剪摊相应的子树 设x[切]所涉及的标记 //hO表示当前扩晨点处x[]的第个可选值 撕口5法的(6款后完早,意号灌续摸的所有子 t=0时,若已测试完x[O]的所有可选值,外层调用全部结 // constraint0是当前扩晨结点处的的束画敷 / bound是当前扩展鳍点处的限界函最 显然这一过程是技深度优先方式进行的 调用一次 backtrack(0)即可完成整个回溯搜索过程 回易,抹去Xk]涉及的标记 方式二:迭代回溯 效率分析一时间 ■回溯算法的效率很大程度上依赖于以下 if (f(n, t)<=g(n, t)) 因素 for( int inf(n, t;i<=g(n, t): i++)< 产生一个x[k]的时间 设x[t所涉及的标记 满足显约束x[k]的个数 计算约束函数 constraint(的时间代价 计算限界函数 bound的时间代价 满足约束函数和限界函数约束的所有x[k]的 个数 回着,抹去Xk涉及的标记 回滴算法 提高时间效率的策略 效率分析一空间 好的约束函数能显著的减少所生成的结点数 空间代价 往往计算量大—折哀问 如果要把整个树存储下来的话,那空间代价 ■搜寰树的结构 是谅人的 “排原理”可提高效 用回溯算法解的问恿的可能解空间一般都很大 结点少的分支优先 即相应的可能解空间树非常巨大。 搜案策略 在回溯算法中,并不需要真正创建一个空间 根据树分支设计优先策略 结点少的分支优先 解多的分支优先 树的深度优先搜索策略的空间代价一般为最 利用搜索树的对称性剪裁子树 长路径的长度 分解为子问题

回溯算法 13 方式一：递归回溯 void backtrack( int t ) { if ( t>=n ) output( x ); //t>n时，算法已经搜索到叶结点 else for ( int i = f( n, t ); i =0 ) { if ( f( n, t ) <= g( n, t ) ) for ( int i=f( n, t ); i<=g( n, t ) ; i++ ) { x[t] = h(i); 设置x[t]所涉及的标记; if ( constraint( t ) && bound( t ) ) { if ( solution(t) ) output(x); else t++; } } else { t - -; 回溯，抹去X[k]涉及的标记； } } } 回溯算法 16 效率分析—时间 „ 回溯算法的效率很大程度上依赖于以下 因素 „ 产生一个x[k]的时间 „ 满足显约束x[k]的个数 „ 计算约束函数constraint()的时间代价 „ 计算限界函数bound()的时间代价 „ 满足约束函数和限界函数约束的所有x[k]的 个数 回溯算法 17 提高时间效率的策略 „ 约束函数 „ 好的约束函数能显著的减少所生成的结点数 „ 往往计算量大——折衷问题 „ 搜索树的结构 „ “重排原理”可提高效率 „ 结点少的分支优先 „ 搜索策略 „ 根据树分支设计优先策略 „ 结点少的分支优先 „ 解多的分支优先 „ 利用搜索树的对称性剪裁子树 „ 分解为子问题 回溯算法 18 效率分析—空间 „ 空间代价 „ 如果要把整个树存储下来的话，那空间代价 是惊人的 „ 用回溯算法解的问题的可能解空间一般都很大， 即相应的可能解空间树非常巨大。 „ 在回溯算法中，并不需要真正创建一个空间 树 „ 树的深度优先搜索策略的空间代价一般为最 长路径的长度

实战训练:背包问题 构造解空间树 从n个物品中选取若干物品装载容量为M b1背包问题的一个解可以表示为一个n维向量 的背包;已知:第个物品的重量是w价 (X0Xy…xn-1)x=0或着1(i=01…n-1) 全部可能解有2n个 值是pi=0.n-1),且每个物品是无 可以采用下图所示的状态空间树 分割的。求:最优装载方案,即总重 量小于M,总价值最大 ■0-1背包问题,物品不允许切割 ⑤⑤6③d①④①66DQ 0-1背包问题状态树示例 搜索过程分析 ≌{12,1 {86,4,3},B=13 约束条件 搜空网:子集判,2个树叶 xP取最大值, 首先判断所有物品的重量和是否小于M 则按物品的价值置量比从大测小排列 在状态空间的任意一个部分解(xox1y…xk-1)处,应 当前部分解的总量 ·当前问慝状态下,繼深入搜可能找到比目前已知解的总 10手可行解:x0x1x1=,重:1: 斗引 子:可切割背包问题 Constraint和 bound函数 已知有n种物品和一个可容纳c重量的背 constraint()函数—实现简单 包,每种物品的重量为W假定物品的 bound函数 一部分放入背包会得到vx的效益。其中 好的 bound函数可以大大降低算法的复杂性 0≤x≤1v>0.采用怎样的装包方法才 会使装入背包物品的总效益最大呢? 在算法中设量一个变量bp,用来记录已搜宗到的解 状态空间结点〔叶结点)的最大值,初始值为0 ■非0-1,可以切割 每到达一个活动结点部分解,就调用 bound() 标函数 n约束条件 k≤C 0≤X≤L,H>0,W>0C>0

回溯算法 19 实战训练：背包问题 „ 从n个物品中选取若干物品装载容量为M 的背包；已知：第i个物品的重量是wi ,价 值是 pi ,(i=0...n-1) ，且每个物品是无 法分割的。求：最优装载方案，即总重 量小于M，总价值最大。 „ 0-1背包问题，物品不允许切割 回溯算法 20 构造解空间树 „ 0-1背包问题的一个解可以表示为一个n维向量 (x0,x1,...,xn-1), xi =0或着1,(i=0,1,...,n-1) „ 全部可能解有2n个 „ 可以采用下图所示的状态空间树 1 X0=0 2 3 4 5 6 8 1 1 X1=0 13 7 9 0 0 12 15 0 1 10 11 16 1 14 20 0 0 1 1 17 18 19 21 0 1 22 24 1 1 0 23 27 0 0 26 28 0 1 25 29 30 1 0 31 1 1 X2=0 X3=0 1 1 回溯算法 21 0-1背包问题状态树示例 „ V={12,11,9,8}, W={8,6,4,3}, B=13 „ 结点：向量（子集的部分特征向量） „ 搜索空间：子集树, 个树叶 对应于可行解： x0=0, x1=1, x2=1, x3=1. 重量：13，价值：28 对应于可行解： x0=1, x1=0, x2=1, x3=0. 重量：12，价值：21 2 n 2 n 回溯算法 22 搜索过程分析 „ 约束条件 „ „ 取最大值， „ 首先判断所有物品的重量和是否小于M； „ 如果是，则解为(1,1,...1)，算法终止 „ 否则按物品的价值重量比从大到小排列 „ 在状态空间的任意一个部分解(x0,x1,...xk-1)处，应 该有以下两个判定指标： „ 当前部分解的总重量 „ 当前问题状态下，继续深入搜索可能找到比目前已知解的总 价值更大的解 1 0 n i i i x p − ∑ = 1 0 n i i i x w M − = ∑ ≤ 回溯算法 23 引子：可切割背包问题 „ 已知有n种物品和一个可容纳c重量的背 包，每种物品i的重量为wi 。假定物品i的 一部分放入背包会得到vi xi 的效益。其中 0≤xi ≤1,vi >0 . 采用怎样的装包方法才 会使装入背包物品的总效益最大呢？ „ 非0-1，可以切割 „ 目标函数 „ 约束条件 1 max n i i i V X = ∑ 1 0 1, 0, 0, 0 n i i i ii i WX C XVWC = ⎧ ⎪ ≤ ⎨ ⎪ ⎩ ≤≤ > > > ∑ 回溯算法 24 Constraint和bound函数 „ constraint( )函数——实现简单 „ bound()函数 „ 好的bound()函数可以大大降低算法的复杂性 „ 在算法中设置一个变量bp，用来记录已搜索到的解 状态空间结点（叶结点）的最大值，初始值为0 „ 每到达一个活动结点i(部分解), 就调用bound(i)

bound函数的计算方法 回溯算法_ knApsack头 ■得到当前结点出发可以达到的可能的最大价值 float btKnapsack(int n, int X[l, float W[, float float M) 从当前部分解(x0x1…x1)开始,采用贪心法计 算一般背包问题的策略,允许最后一个物品被分割 CW=OF Cp=0; 后加入背包,从而得到从结点出发的子树中可以达 for (int i=O;i bpt cktrack(+1XWPM);//前进,搜囊 bp cpi CW-= W[]; /回溯,消除标记 for(int j=OF; jb){//不取物品 X[i]=0 return; track(i+1,xW,P,M);∥/前进,搜索 回滴算法 限界函数 bound() 时间复杂度分析 取决于 btsorto, bound; backtrack(三个函 float bound ( int i, float w[], float P[[ float cr=M-CW: float b= btsorto一般为o(nlgn)只执行一次 /cw是运行过程中部分解的总重量,cp是总价值 Bound为o(n)在大多数 backtrack调用中 while((i< n)&&(W[]<= cr))I cr-= W[]; 搜索递归函数 backtrack的时间复杂度由递 b += P[] 归调用的次数决定 /直至背包中剩余容量无法装下下 数坏舞歪銘点题之与态空的树地点数 /允许分割,以求得上界(贪心法 调用 backtrack的代价就是执行 bound的 return b }

回溯算法 25 bound()函数的计算方法 „ 得到当前结点出发可以达到的可能的最大价值 „ 从当前部分解(x0,x1,...,xk-1)开始，采用贪心法计 算一般背包问题的策略，允许最后一个物品被分割 后加入背包，从而得到从结点i出发的子树中可以达 到的总价值的上界。 „ 如果这个上界小于当前的bp值，说明该子树不 可能包含最优解，就可以被“剪枝”，则将这个 部分解结点变为死结点 回溯算法 26 回溯算法—btKnapsack头 float btKnapsack(int n, int X[], float W[],float P[],float M) { cw=0; cp=0; for (int i=0;i=n) { if (cp > bp) { bp = cp; for (int j=0; j bp) { // 不取物品i X[i] = 0; backtrack(i+1, X, W, P, M); // 前进，搜索 } } 回溯算法 29 限界函数:bound(i) float bound(int i, float W[], float P[]) { float cr = M - cw; float b = cp; //cw是运行过程中部分解的总重量，cp是总价值 while (( i < n ) && (W[i] <= cr)) { cr -= W[i]; b += P[i]; i++; } //直至背包中剩余容量无法装下下一个物品 //允许分割，以求得上界（贪心法） if (i < n) b += P[i] * cr / W[i]; return b; } 回溯算法 30 时间复杂度分析 取决于btSort(),bound();backtrack()三个函 数 „ btSort()一般为O(nlogn),只执行一次 „ Bound()为O(n)在大多数backtrack()调用中 bound()被调用一次 „ 搜索递归函数backtrack()的时间复杂度由递 归调用的次数决定 „ 最坏情形的调用次数恰恰与状态空间的树结点数一 致，并且结点数2^(n+1)-1 „ 每次调用backtrack()的代价就是执行bound()的 代价O(n)

空间复杂度分析 运行数据 主要由两个因素决定, 已知 算法的输入,输出和运行中的临时数据 nn=8,M=110 占用空间显然为on W=(111212333434555) ■递归过程所用的栈空间, P=(11213133435355,65) 由于递归调用是不断调用和退出的过程,递 归层数不可能超过状态空间树的高度n,而 每一层调用占用的空间为常数,故空间代价 最终结果:11101100 maxvalue 159 运行实例分析 耳 这个问题的状态 有511个结点,其中 256个叶结点(可能解 实际搜索最优解只涉及到27结点,其中4个叶 结点 行,即当某结点的左子树搜结束,转到其右 子结点时 (其中15次展开)。 幽 没有必要两个分支都判断 右分支剪比左分支效果好(仅左,需要330) 理种中 解为结点44bp=159,(11101100) 更大的例子 的 基本回溯小结 回濒适应于求解组合搜索问题(组合优化问题 O, MAX WEIGHT= 解示般用树表示 7160387}73467505}{816577} 解向量,解的过程是不断扩充解向量的过程 320475》1103828 180,1198} 回溯口诀 37973160}22925940》{18351807}{7734208 能进则进,不能进则换,不能换则退 回溯条件 搜索问题--约束条件 增需: 97151个蜡点 ■优化问题一的束条件+限界函数 算法复杂性 適历搜树的时间,最坏情况为指数 空间代价小

回溯算法 31 空间复杂度分析 主要由两个因素决定， „ 算法的输入，输出和运行中的临时数据 占用空间显然为O(n) „ 递归过程所用的栈空间， „ 由于递归调用是不断调用和退出的过程，递 归层数不可能超过状态空间树的高度n，而 每一层调用占用的空间为常数，故空间代价 为O(n) 回溯算法 32 运行数据 已知 „ n=8, M=110, „ W=(1,11,21,23,33,43,45,55), „ P=(11,21,31,33,43,53,55,65) 回溯算法 33 0 0 1 89 139 6 56 96 5 33 63 4 12 32 3 1 11 2 89 139 164.7 14 89 139 163.8 18 89 139 139 20 „ n=8, M=110 „ W=(1,11,21,23,33,43,45,55) „ P=(11,21,31,33,43,53,55,65) 编号为全序DFS周游完全二叉树 紫色值为超重剪左支 蓝色为估计BP值 99 149 162 26 99 149 22 56 96 162.4 21 99 149 149 28 56 96 161.6 29 101 151 30 101 151 151 32 66 106 37 33 63 160.2 36 66 106 159.8 45 109 159 159 44 109 159 42 109 159 38 66 106 158 49 33 63 157.6 52 35 65 68 12 32 159.8 67 68 108 69 68 108 157.6 81 68 108 159.3 77 35 65 157.1 84 12 32 154.9 99 1 11 157.4 130 0 0 155.1 257 最终结果： 11101100 maxValue = 159 56 96 159.8 33 56 96 96 35 132 134 144 144 154 156 111 154 164 111 111 113 回溯算法 34 运行实例分析 „ 这个问题的状态空间树有511个结点，其中 256个叶结点（可能解） „ 实际搜索最优解只涉及到27结点，其中4个叶 结点 „ 计算限界函数bound()只是在每次回溯时进 行，即当某结点的左子树搜索结束，转到其右 子结点时，计算bound()值，共需计算23次 （其中15次展开）。 „ 没有必要两个分支都判断 „ 右分支剪比左分支效果好（仅左，需要330） „ 解为结点44, bp=159, (11101100) 回溯算法 35 更大的例子 n =20, MAX_WEIGHT = 20000 WV wv[20] = { {52,7946},{7160,387},{7346,7505},{816,577}, {961,6021},{5262,8278},{4163,931},{1003,9738}, {7914,1683},{320,475},{1103,8280},{6180,1198}, {1334,2791},{5812,2608},{6930,5515},{4451,9602}, {3797,3160}, {2292,5940},{1835,1807},{773,4208} }; „ 总2097151个结点 „ 剪左：121049 „ 剪右：34 „ maxValue: 65188, 回溯算法 36 基本回溯小结 „ 回溯适应于求解组合搜索问题(组合优化问题) „ 解空间一般用树表示 „ 解的表示 „ 解向量，解的过程是不断扩充解向量的过程 „ 回溯口诀 „ 能进则进，不能进则换，不能换则退 „ 回溯条件 „ 搜索问题---约束条件 „ 优化问题---约束条件+限界函数 „ 算法复杂性 „ 遍历搜索树的时间，最坏情况为指数 „ 空间代价小

高级回溯讨论 估计回溯算法的平均效率 确定子结点的排列规则 计数搜索树中平均遍历的结点 子集树和排列树 Monte carlo方法 装载问题(01背包)问厦都是子集树 1.从根开始,随机选择一条路经,直到不能分 皇后问题与旅行售货员问题是排列树 依次对x赋值 估计回溯算法的平均效率 的值是从当时的5中随机选取,直到向量不能 张为止 判断是否满足多米诺性质 2.假定搜索树的其他|5-1个分支与以上随机选 ■搜索策略-深度优先 出的路径一样,计数搜索树的点数。 确定每个结点能够分支的约束条件 3.重复步骤1和2,将结点数进行概率平均 ■确定存储搜索路径的数据结构 算法 计算结点数 Monte carlo m为本次取样结点总数,k为层数,八为本层分支数 n2为上层分支数,为树的层数 2. for i 1 to t do ∥取样次数 m=1;r2=1;k=1 While k:1+4X1+4X2=13 假设4抽样测试:case11次,case21次,cse32次,平均为16 设尺(x1,2,…,)为真表示向量<x1,x2,…,加中个皇 解空间的蝻点败为17 后放量在彼此不能攻击的位 M+1)→尺Ⅺ,…,冰)0<k<n

回溯算法 37 高级回溯讨论 „ 确定子结点的排列规则 „ 子集树和排列树 „ 装载问题(0-1背包)问题都是子集树 „ 皇后问题与旅行售货员问题是排列树 „ 估计回溯算法的平均效率 „ 判断是否满足多米诺性质 „ 搜索策略----深度优先 „ 确定每个结点能够分支的约束条件 „ 确定存储搜索路径的数据结构 回溯算法 38 估计回溯算法的平均效率 „ 计数搜索树中平均遍历的结点 „ Monte Carlo方法： 1．从根开始，随机选择一条路经，直到不能分 支为止, 即从x1,x2,…, 依次对xi赋值，每个xi 的值是从当时的Si中随机选取，直到向量不能 扩张为止 2．假定搜索树的其他|Si|-1个分支与以上随机选 出的路径一样，计数搜索树的点数。 3．重复步骤1和2，将结点数进行概率平均。 回溯算法 39 算法 Monte Carlo 1.sum = 0 2.for i = 1 to t do //取样次数 t 3. m = Estimate(n) //m为本次结总数 4. sum+= m 5.sum /= t 回溯算法 40 计算结点数 m为本次取样结点总数，k 为层数，r1为本层分支数, r2为上层分支数，n为树的层数 Estimate(n) 1. m=1;r2=1;k=1 2. While k：1+4+4×2+4×2 = 21 case2．:：4×3+1=17 case3．：1+4×1+4×2=13 假设4次抽样测试：case1 1次，case2 1次，case3 2次，平均为16 解空间的结点数为17 回溯算法 42 必要条件—多米诺性质 „ n皇后问题 „ 设P(x1, x2, …, xi) 为真, 表示向量中i个皇 后放置在彼此不能攻击的位置 P(x1 , x2 ,..., xk+1 ) → P(x1 , x2 ,..., xk ) 0 < k < n

多米诺性质?求不等式的整数解 影响算法效率的因素 5x+4x,-x≤101≤×≤3,=1 1.最坏情况下的时间W(m)=(风(m)(m) n)每个结点时间,m)结点个数 促左边小事芋过是足米在簽 2.影响回朔算法效率的因素 搜索树的结构 分支情况:分支均匀否 的深度 分布深度 约束条件的判断:计算筒单 分支限界技术 实现方法 与回溯法的比较 求解目标、搜索方式、扩展结点的扩展方式、存储 ■队列式(FIFO)分支限界法 空间的要求不同 活动结点组织成队列,按FIFo原则选取下 对解空间树的搜索存储结点的数结点存储特性常用应用 一个结点为当前扩展结点 ■优先队列式分支限界法 被条件的所有解 活动结点组织成优先队列,按队列中规定 的结点优先级选取优先级最高的下一个结 分支限界广度优先成 队列、优先队部个点只有找出足的 点成为当前扩展结点,通常用堆来实现 最小消耗〔最大效列 盐)优先搜 点的机会 装载问题 用回溯法求解 约束函数:设cW为已装重量,如cw N个待装载的货物[w1w2,wn],船的载重量为 C,求装载哪些货物使得装的货物最重且不超过c w()>c1则杀死该子结点 限界函数:设 besty为当前最优装船重量, Max>wx 设为r剩余货箱的总重量, 如cwW+r<= best则停止产生该结点及其 子结点。 andx∈{O,}

回溯算法 43 多米诺性质？求不等式的整数解 , 1≤xi≤3, i=1,2,3 P(x1, …, xk) : 意味将x1,x2,…,xk代入原不等式的相应部分 使得左边小于等于10，是否满足多米诺性质？ 5 4 10 1 2 3 x + x − x ≤ 回溯算法 44 影响算法效率的因素 1. 最坏情况下的时间W(n)=(p(n) f(n)) 其中p(n)每个结点时间，f(n)结点个数 2. 影响回朔算法效率的因素 „ 搜索树的结构 分支情况：分支均匀否 树的深度 对称程度：对称适合裁减 „ 解的分布 在不同子树中分布多少是否均匀 分布深度 „ 约束条件的判断：计算简单 回溯算法 45 分支限界技术 „ 与回溯法的比较 求解目标、搜索方式、扩展结点的扩展方式、存储 空间的要求不同 找出满足约束 条件的一个解 或特定意义下 的最优解 每个结点只有 一次成为活结 点的机会 队列、优先队 列 广度优先或 最小消耗（最大效 益）优先搜索 分支限界 找出满足约束 条件的所有解 活结点的所有 可行子结点被 遍历后才被从 栈中弹出 回溯 深度优先 堆栈 存储结点的数 结点存储特性 常用应用 据结构 对解空间树的搜索 方式 方法 回溯算法 46 实现方法 „ 队列式（FIFO）分支限界法 活动结点组织成队列，按FIFO原则选取下 一个结点为当前扩展结点 „ 优先队列式分支限界法 活动结点组织成优先队列，按队列中规定 的结点优先级选取优先级最高的下一个结 点成为当前扩展结点，通常用堆来实现 回溯算法 47 装载问题 „ N个待装载的货物[w1,w2,…,wn]，船的载重量为 C，求装载哪些货物使得装的货物最重且不超过C。 1 n i i i Max w x = ∑ 1 { } 1 0,1 , 1 n i i i i w x c and x i n = ∑ ≤ ∈ ≤≤ 回溯算法 48 用回溯法求解 „ 约束函数：设cw为已装重量，如cw＋ w(i)>c1则杀死该子 结点。 „ 限界函数：设bestw为当前最优装船重量， 设为 r剩余货箱的总重量， 如cw+r<=bestw,则停止产生该结点及其 子结点

回溯法求解 template g (int i) template (>n){/在叶结点上 class Loading friend MaxLoading(T[, T, int); /检查子树 privat r-=w[] void maxLoading(int i); if(cw+w[] best)∥/尝试x[i=0 /当前装载的重量 m axLoading(i+1) /目前最优装载的重量 } m=4,W=[8,6,2,3],c=12 搜索前进到第一个叶结点(的右孩子 besty被置为10。回溯到E,然后向下移 动到K的左孩子此时 best被更新为11 n我们没有移动到K的右孩子,因为在右孩子 结点cW=8,r=0 到结点A。同样,不必移动到右孩子C,因 为在C点cW=0,r=11且cW+r≤ best =[8,6,2,3],c=12 回滴算法 分支限界法 分支限界法 队列式分支限界法 函数 EnQueue用于将活动结点加入到队列中。 Q用于存放活动结点表,Q中用EW表示每个活 动结点所相应的当前载重量,当EW=-1时 Void EnQueue( queue &Q, Type wt, 表示队列已到达解空间树同一层结点的尾 Type best int i, int n) if(i==n)//该结点为叶结点,不再扩展 if( wt best)best wt; else Q. Add( wt i

回溯算法 49 回溯法求解 template class Loading { friend MaxLoading(T [], T, int); p r i v a t e : void maxLoading(int i); int n; // 货箱数目 T *w, // 货箱重量数组 c, // 第一艘船的容量 cw, // 当前装载的重量 bestw; // 目前最优装载的重量 } ; 回溯算法 50 template void Loading::maxLoading(int i) { // 从第i 层结点搜索 if (i > n) {// 在叶结点上 bestw = cw; r e t u r n ; } // 检查子树 r -= w[i]; if (cw + w[i] bestw) //尝试x[i] = 0 m a x L o a d i n g ( i + 1 ) ; r += w[i]; } 回溯算法 51 „ n= 4，w= [ 8 , 6 , 2 , 3 ]，c = 12 。 „ 搜索前进到第一个叶结点（J的右孩子）。 bestw 被置为10。回溯到E，然后向下移 动到K的左孩子此时bestw被更新为11。 „ 我们没有移动到K的右孩子，因为在右孩子 结点cw=8，r=0，cw+r≤bestw。回溯 到结点A。同样，不必移动到右孩子C，因 为在C点cw=0，r=11且cw+r≤bestw。 回溯算法 52 w= [ 8 , 6 , 2 , 3 ]，c = 12 cw=0 r=19 1 cw=8 r=11 0 1 1 0 0 cw=8 r=5 cw=10 r=3 bestw=10 cw=8 r=3 cw=11 r=0 bestw=11 0 cw=0 r=11 cw+r Void EnQueue( Queue &Q, Type wt, Type & bestw, int i, int n) { if( i == n ){ //该结点为叶结点 ，不再扩展 if( wt > bestw ) bestw = wt; } else Q.Add( wt ); }

“ F一 所要考察的层 /右儿子结点总是可以的 EnQueue(Q, Ew, best, i, n ;//x0=0 if( QIsEmpty o)return 蜻点尾部标志 Q Delete(Ew) 8,6,2,3],c=12 优先队列式分支限界法解装载问题 搜索顺序 优先级定义为从根结点到活动结点相应 影响回溯时间代价的因素 路径上的载重量再加上剩余货物的重量 搜索空间大小 ■活动结点存储在最大值堆中 搜索树的结构和解的分布 分支定界的方法充分利用了搜索树的结构 和解的分布更快的找到解 能否改变搜索空间的大小呢? 不同的搜索空间 背包问题 ■同样的搜索问题,采取不同的搜索顺序 若干个大小有限制的背包,若干物品的 将会有不同的搜索空间 质量总和和这些包的总容量相同,问这 搜索顺序影响搜索树的结构,不同的搜 些包能否将这些物品全部装走? 索顺序导致剪枝在不同的时候发生 两个背包容量都是5,4个物品的重量分 ■搜索顺序决定剪枝的效果 别是4,3,2 n物品同上,如果有三个背包,容量分别 是6

回溯算法 55 Template Type MaxLoading( Type w[], Type c, int n ) { Queue Q; //活动结点队列 Q.Add(-1); //同层结点尾标志 int i = 1; //当前扩展结点所要考察的层 Type Ew = 0; //扩展结点所相应的载重量 Type bestw = 0; // 当前最优载重量 while(true) { //搜索子空间树 //检查左儿子结点 if( Ew + w[i] <=c ) //x[i] = 1 EnQueue(Q, Ew+w[i], bestw, i, n ); //右儿子结点总是可以的 EnQueue(Q, Ew, bestw, i, n ); //x[i] = 0 Q.Delete(Ew); //取下一扩展结点 if (Ew == -1){ //同层结点尾 if( Q.IsEmpty() ) return bestw; Q.Add(-1); //同层结点尾部标志 Q.Delete(Ew); //取下一扩张结点 i++; //进入了下一层 } } 回溯算法 56 „ w= [ 8 , 6 , 2 , 3 ]，c = 12 J -1 A 1 0 B B C C -1 0 D D E F E F 10 G H 回溯算法 57 优先队列式分支限界法解装载问题 „ 优先级定义为从根结点到活动结点相应 路径上的载重量再加上剩余货物的重量 „ 活动结点存储在最大值堆中 回溯算法 58 搜索顺序 „ 影响回溯时间代价的因素 „ 搜索空间大小 „ 搜索树的结构和解的分布 „ 分支定界的方法充分利用了搜索树的结构 和解的分布更快的找到解 „ 能否改变搜索空间的大小呢？ 回溯算法 59 不同的搜索空间 „ 同样的搜索问题，采取不同的搜索顺序 将会有不同的搜索空间 „ 搜索顺序影响搜索树的结构，不同的搜 索顺序导致剪枝在不同的时候发生 „ 搜索顺序决定剪枝的效果 回溯算法 60 背包问题 „ 若干个大小有限制的背包，若干物品的 质量总和和这些包的总容量相同，问这 些包能否将这些物品全部装走？ „ 两个背包容量都是5，4个物品的重量分 别是4，3，2，1 „ 物品同上，如果有三个背包，容量分别 是6，2，2呢？