北京大学：《数据结构与算法》课程教学资源（实习讲义）回溯（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维向量,<X,x2,8,A4> (放量列号 中的每一个结点确定所求解问题的一个问题状态 搜索空间: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维向量，<x1,x2,x3,x4> （放置列号） „ 搜索空间：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 <= g( n, t ); i++ ) { // f()和g(): 当前扩展点子树待处理的起点与终点 x[t] = h( i ); 设置x[t]所涉及的标记; //h()表示当前扩展点处x[t]的第i个可选值 if ( constraint( t ) && bound( t )) //constraint()是当前扩展结点处的约束函数； //bound()是当前扩展结点处的限界函数 backtrack( t+1 ); 回溯，抹去X[k]涉及的标记； } } 回溯算法 14 递归回溯算法解释 „ constraint()返回的值为true时，在当前扩展结点处x[0:t- 1] 取值满足问题的约束条件；否则不满足约束，可剪掉相 应的子树 „ bound()返回的值为true时，在当前扩展结点处x[0:t-1]取 值未使目标函数越界，还需由backtrack(t+1)对其相应的 子树进一步搜索；否则，剪掉相应的子树 „ 执行了算法的for循环后，已搜索遍当前扩展结点的所有子 树。backtrack(t)执行完毕，返回t-1层继续执行 „ 当t=0时，若已测试完x[0]的所有可选值，外层调用全部结 束。 „ 显然这一过程是按深度优先方式进行的。 „ 调用一次backtrack(0)即可完成整个回溯搜索过程 回溯算法 15 方式二：迭代回溯 void iterativeBacktrack() { int i = 1; while ( t>=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 ,x1 ,…,x k-1>（子集的部分特征向量） „ 搜索空间：子集树, 个树叶 <0,1,1,1> 对应于可行解： x0=0, x1=1, x2=1, x3=1. 重量：13，价值：28 <1,0,1,0> 对应于可行解： 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<n; i++)& 到的总价值的上界 W+=W[ 计算总价值和总盒量 ■如果这个上界小于当前的bp值,说明该子树不 if(cw<=M) return cp;∥/可以 可能包含最优解,就可以被“剪枝”,则将这个 btsort(W, P, n); //按价值量比排序 p=cw= 0; bp=0; 部分解结点变为死结点 backtrack(o,XWPM)∥递归回测 return bp 返回最优解的总价值,同时把最优解放在全局数组Y[中 递归函数: backtrack() void backtrack(int i, int xII, float w[, float /W存储各物品量量 Po, float)t if( cw+ W[]<=Mt /取物品 /已到叶结点,取得当前最大价值,回溯 P是存储各物品价值的数组 if(cp> bpt cktrack(+1XWPM);//前进,搜囊 bp cpi CW-= W[]; /回溯,消除标记 for(int j=OF; j<n; j++) YU= xU] if( bound(i+1,WP)>b){//不取物品 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;i++) { cp += P[i]; cw += W[i]; } // 计算总价值和总重量 if (cw <= M) return cp; // 可以全部装入 btSort(W,P,n); // 按价值重量比排序 cp = cw = 0; bp=0; backtrack(0, X, W, P, M); // 递归回溯 return bp; } 返回最优解的总价值，同时把最优解放在全局数组Y[]中 回溯算法 27 递归函数：backtrack() void backtrack(int i, int X[], float W[], float P[], float M) { //已到叶结点，取得当前最大价值，回溯 if (i>=n) { if (cp > bp) { bp = cp; for (int j=0; j<n; j++) Y[j] = X[j]; } return; } 回溯算法 28 // W存储各物品重量 if ( cw + W[i] <=M) { // 取物品i X[i] = 1; cw += W[i]; cp += P[i]; // P是存储各物品价值的数组 backtrack(i+1, X, W, P, M); // 前进，搜索 cw -= W[i]; // 回溯, 消除标记 cp -= P[i]; } if (bound(i+1, W, P) > 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)