方式一:递归回溯 递归回溯算法解释 取减定還的猿数件定聚句對 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 效率分析—空间 „ 空间代价 „ 如果要把整个树存储下来的话，那空间代价 是惊人的 „ 用回溯算法解的问题的可能解空间一般都很大， 即相应的可能解空间树非常巨大。 „ 在回溯算法中，并不需要真正创建一个空间 树 „ 树的深度优先搜索策略的空间代价一般为最 长路径的长度