■结点分支判定条件: 满足约東条件--分支扩张解向量 不满足约束条件,回溯到该结点的父结点 结点状态:动态生成 种: a尚未访问 b正在访问该结点为根的子树(活动结点、扩展 结点) c该结点为根的子树遍历完成 存储:当前路径 回溯算法 11
回溯算法 11 结点分支判定条件： 满足约束条件---分支扩张解向量 不满足约束条件，回溯到该结点的父结点 结点状态：动态生成 三种： a 尚未访问 b 正在访问该结点为根的子树（活动结点、扩展 结点） c 该结点为根的子树遍历完成 存储：当前路径
原理描述一回溯法的基本思想 基本思想: (1)针对所给问题,定义问题的解空间; (2)确定易于搜索的解空间结构 (3)以深度优先方式搜索解空间,并在搜索过程中 用剪枝函数避免无效搜索 常用剪枝函数 用约束函数在扩展结点处剪去不满足约束的子树; n对于优化问题,还可以用限界函数( Bounding Function)处死那些实际上不可能产生所需解的活 结点,也就是剪去得不到最优解的子树 递归回溯vs迭代回溯 回溯算法
回溯算法 12 原理描述—回溯法的基本思想 基本思想： (1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构； (3)以深度优先方式搜索解空间，并在搜索过程中 用剪枝函数避免无效搜索。 常用剪枝函数 用约束函数在扩展结点处剪去不满足约束的子树； 对于优化问题，还可以用限界函数(Bounding Function)处死那些实际上不可能产生所需解的活 结点，也就是剪去得不到最优解的子树。 递归回溯 vs 迭代回溯
方式一:递归回溯 void backtrack( int t)t if ( t>=n)output( x i //t>n时,算法已经搜索到叶结点 else for( inti=f(n, t;i<=g(n, t;i++)t //f0和g(:当前扩展点子树待处理的起点与终点 x[t]= h(i)i 设置x[]所涉及的标记; //hO表示当前扩展点处x[t]的第个可选值 if constraint(t)&& bound(t)) // constraint0是当前扩展结点处的约束函数; // bound是当前扩展结点处的限界函数 backtrack( t+1 F 回溯,抹去X[k]涉及的标记; } 回溯算法
回溯算法 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]涉及的标记； } }
递归回溯算法解释 constraint(返回的值为true时,在当前扩展结点处x[ot 1]取值满足问题的约束条件;否则不满足约束,可剪掉相 应的子树 bound返回的值为true时,在当前扩展结点处x[o:t-1]取 值未使目标函数越界,还需由 backtrack(t+1)对其相应的 子树进一步搜索;否则,剪掉相应的子树 执行了算法的for循环后,已搜索遍当前扩展结点的所有子 树。 backtrack(t执行完毕,返回t-1层继续执行 当t=0时,若已测试完x[O]的所有可选值,外层调用全部结 束。 显然这一过程是按深度优先方式进行的 调用一次 backtrack(0即可完成整个回溯搜索过程 回溯算法 14
回溯算法 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)即可完成整个回溯搜索过程
方式二:迭代回溯 void iterative Backtrack int i= 1i while〔t>=0){ if (f(n,t)<=g(n, t)) (int i=f(n, t;k<=g(n, t);i++ x[t]= h(; 设置x[t]所涉及的标记 if( constraint( t)&& bound( t)t if solution(t)) output(x)i lise t++i aise i t 回溯,抹去Xk涉及的标记; } 回溯算法
回溯算法 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]涉及的标记； } } }