回溯法在包含问题的全部解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。算法搜索至解空间树的任何一个结点时,老是先判断该结点是否确定不包含问题的解,若是确定不包含,则跳过对以该结点为根的子树搜索。不然,进入该子树,继续按深度优先的策略进行搜索。回溯法在用来求问题的全部解时,要回溯到根,且根结点的全部子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时,只要搜索到问题的一个解就可结束。算法
回溯法解问题时,首先应明肯定义问题的解空间。问题的解空间应至少包含问题的一个最优解。一般将问题的解空间组织成树或图的形式。例如,对于n=3的0-1背包问题,其解空间树可用下面的彻底二叉树表示。
框架
回溯法即以这种工做方式递归地在解空间中搜索,直至找到所要求的解或解空间中已无活结点时为止。函数
在用回溯法搜索解空间树时,一般采用两种策略来避免无效搜索,提升回溯法的搜索效率。这两类方法统称为剪枝函数。优化
其一是用约束函数在扩展结点处剪去不知足约束条件的子树;
其二是用限界法剪去不能获得最优解的子树。3d
回溯法是对解空间的深度优先搜索code
void Backtrack(int t) { if(t>n) Output(x); else for(int i=f(n,t);i<=g(n,t);i++) // f(n,t)和g(n,t):在当前扩展结点处未 { x[t]=h(i); //搜索过的子树的起始编号和终止编号 if (Constraint(t)&&Bound(t)) Backtrack(t+1);} } // Constraint(t)和Bound(t):在当前扩展结点处的约束函数和限界函数
当所给的问题是从n个元素的集合S中找出知足某种性质的子集时,相应的解空间树为子集树。这类子集树常有2n个叶结点,其结点个数为2n+1-1。遍历子集树的任何算法均需Ω(2n)的计算时间。
blog
void Backtrack(int t) { if(t>n) Output(x); else for(int i=0;i<=1;i++) { x[t]=i; if(Constraint(t)&&Bound(t)) Backtrack(t+1);} }
当所给问题是肯定n个元素的知足某种性质的排列时,相应的解空间树为排列树。排列树一般有n!各叶结点。所以遍历排列树所需的计算时间须要Ω(n!) 的计算时间。
递归
void Backtrack(int t) { if(t>n) Output(x); else for(int i=t;i<=n;i++) { Swap(x[t],x[i]); if(Constraint(t)&&Bound(t)) Backtrack(t+1); Swap(x[t],x[i]); } }
注:因此剪枝函数须要好好想一想,以到达优化。当解题时,能够先将解空间都描绘出来,再慢慢肯定剪枝函数class