回溯法：有通用解题法 之称，能够系统的搜索一个问题的全部解和任一解，是一个既带有系统性，又带有跳跃性的搜索算法。算法
算法基本思想：函数
肯定解空间后spa
从开始节点出发，以深度优先的方式搜索整个解空间。code
若是当前扩展结点不能再向纵深方向移动，当前节点为死节点。此时，应该往回移动至最近的一个活节点处。，并是这个或节点成为当前节点的扩展结点。blog
提升算法方式（剪枝函数）：递归
1 用约束函数在扩展结点出剪去不知足约束的子树class
2 用限界函数剪去得不到最优解的子树。扩展
回溯法解题步骤：搜索
1 定义问题的解空间集合
2 肯定易于搜索的解空间结构
3 以深度优先方式搜索解空间，并在搜索过程当中用剪枝函数避免无效搜索。
递归回溯：
void Backtrack(int t) { if(t>n) Output(x); else for(int i=f(n,t);i<=(g,t);i++) { x[t] = h(i); if(Constraint(t) && Bound(t)) Backtrack(t+1); } }
子集树：
当全部的问题是从n个元素的集合S中找出知足某种性质的子集时，相应的解空间树称为子集树。
伪码为：
void Backtrack(int t) { if(t>n) Output(x); else for(int i=f(n,t);i<=(g,t);i++) { x[t] = h(i); if(Constraint(t) && Bound(t)) Backtrack(t+1); } }
排列树：
当所给的问题是肯定n个元素知足某种性质的排列时，相应的解空间树称为排列数。
伪码为：
void Backtrack(int t) { if(t>n) Output(x); else for(int i=f(n,t);i<=(g,t);i++) { Swap(x[t],x[i]); if(Constraint(t) && Bound(t)) { Backtrack(t+1); } Swap(x[t],x[i]); } }