直观分析一搜索代价 时间代价 空间树共有65个结点,24个叶结点,但在搜索过 程中,只遍历了16个结点,其中2个叶结点 如果要找所有解的话,则还要继续搜索下去 空间代价 与树的高度有关,而不是和树的总结点数有关 回溯算法中,并不需要真正创建一个解空间树
26 直观分析—搜索代价 ◼ 时间代价 ◼ 空间树共有65个结点，24个叶结点，但在搜索过 程中，只遍历了16个结点，其中2个叶结点 ◼ 如果要找所有解的话，则还要继续搜索下去 ◼ 空间代价 ◼ 与树的高度有关，而不是和树的总结点数有关 ◼ 回溯算法中，并不需要真正创建一个解空间树
原理描述一问题的解空间 ■问题的解向量:回溯法希望一个问题的 解能够表示成一个n元式(x1x2xXn)的 形式 显约束:对分量x1的取值限定。 ■隐约束:为满足问题的解而对不同分量 之间施加的约束。 ■解空间:对于问题的一个实例,解向量 满足显式约束条件的所有多元组,构成 了该实例的一个解空间
27 原理描述—问题的解空间 ◼ 问题的解向量：回溯法希望一个问题的 解能够表示成一个n元式(x1 ,x2 ,…,xn )的 形式。 ◼ 显约束：对分量xi的取值限定。 ◼ 隐约束：为满足问题的解而对不同分量 之间施加的约束。 ◼ 解空间：对于问题的一个实例，解向量 满足显式约束条件的所有多元组，构成 了该实例的一个解空间
原理描述一生成问题状态的基本方法 扩展结点:一个正在产生儿子的结点称为扩展结点 活结点:一个自身已生成但其儿子还没有全部生成的结 点称做活结点 死结点:一个所有儿子已经产生的结点称做死结点 问题状态生成法: 深度优先:如果对一个扩展结点R,一且产生了它的一个儿子 c,就把C当做新的扩展结点。在完成对子树C(以C为根的子 树)的穷尽搜索之后,将R重新变成扩展结点,继续生成R的 下一个儿子(如果存在)——回溯法 宽度优先:在一个扩展结点变成死结点之前,它一直是扩展 结点——分支定界法
28 原理描述—生成问题状态的基本方法 ◼ 扩展结点:一个正在产生儿子的结点称为扩展结点 ◼ 活结点:一个自身已生成但其儿子还没有全部生成的结 点称做活结点 ◼ 死结点:一个所有儿子已经产生的结点称做死结点 ◼ 问题状态生成法： ◼ 深度优先：如果对一个扩展结点R，一旦产生了它的一个儿子 C，就把C当做新的扩展结点。在完成对子树C（以C为根的子 树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的 下一个儿子（如果存在）——回溯法 ◼ 宽度优先：在一个扩展结点变成死结点之前，它一直是扩展 结点——分支定界法
原理描述一回溯法的基本思想 基本思想: ■(1)针对所给问题,定义问题的解空间; (2)确定易于搜索的解空间结构; ■(3)以深度优先方式搜索解空间,并在搜索过程中 用剪枝函数避免无效搜索。 常用剪枝函数 用约束函数在扩展结点处剪去不满足约束的子树; 对于优化问题,还可以用限界函数( Bounding Function)处死那些实际上不可能产生所需解的活 结点,也就是剪去得不到最优解的子树。 ■递归回溯vs迭代回溯
29 原理描述—回溯法的基本思想 ◼ 基本思想： ◼ (1) 针对所给问题，定义问题的解空间； ◼ (2) 确定易于搜索的解空间结构； ◼ (3) 以深度优先方式搜索解空间，并在搜索过程中 用剪枝函数避免无效搜索。 ◼ 常用剪枝函数 ◼ 用约束函数在扩展结点处剪去不满足约束的子树； ◼ 对于优化问题，还可以用限界函数(Bounding Function)处死那些实际上不可能产生所需解的活 结点，也就是剪去得不到最优解的子树。 ◼ 递归回溯 vs 迭代回溯
方式一:递归回溯 void backtrack( int t)t if( t>=output( x i //t>n时,算法已经搜索到叶结点 else for( int i=f(n t;i<=g(n, t;i++t //f0和gO:当前扩展点子树待处理的起点与终点 xt]=h(i)i 设置x[t所涉及的标记; //h(表示当前扩展点处x[t的第个可选值 if( constraint( t)&& bound(tD // constraint是当前扩展结点处的约束函数 // bound是当前扩展结点处的限界函数 backtrack( t+1 ) i 回溯,抹去X[k]涉及的标记; } }
30 方式一：递归回溯 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]涉及的标记； } }