回溯法是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。 但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

术语

解空间：问题可行解的集合

回溯法：以深度优先的方式 系统搜索问题的解

避免无效搜索
剪枝函数(以下两类函数都是剪枝函数)

1. 约束函数–用约束函数在扩展结点处剪去不满足约束的子树；
   •见0-1背包问题
2. 限界函数–用限界函数剪去得不到最优解的子树；
   •见TSP问题

两种类型的解空间树

子集树

2^n个叶结点 01背包问题

搜索子集树的一般算法
（完全n叉树属于子集树）

//t表示当时搜的深度
//n一般是问题规模，是数组x的长度，诸如背包问题中石块的数量
//x是解集
void backtrack( int t)
{  
       //如果递归到最深层了，就输出结果，找到符合问题的一个解了
       if(t>n) output(x);
       else
            for(int i=0;i<=1;i++)
           //0是左子树，1是右子树
           {
                x[t]=i;
                if(constrain(t)&&bound(t)) backtrack(t+1);
               //如果不符合这一约束的话，函数会接着执行i=1看看是不是能进入backtrack(t+1),如果都不行的话才会回溯回backtrack(t-1)去重新决定x[t-1]这个是不是要改成1
            }
}

排列树

n!个叶结点 TSP旅行商问题

搜索排列树的一般算法

//n是问题的规模
//t是当前搜索的深度
//x是解集
void backtrack( int t)
{  
       //依旧是搜索到最深一层时，输出结果
       if(t>n) output(x);
       else
         //随着搜索的深入，x解集中已被选中的元素数量为t，剩下的可以选择的数量则为n-t
         for(int i=t;i<=n;i++)
         {
             //搜索深度t可以代表当前我们要决定的元素是x[t]
             //t的选择在这里有 t、t+1、t+2...、n这些可以选择
             //因为1、2、..、t-1这些选择已经被选走了
             swap(x[t],x[i]);
             if (constrain(t)&&bound(t))     backtrack(t+1);
             //如果不符合约束条件的话我们需要把x[t]换回来
             swap(x[t],x[i]);
             //然后继续搜索i=t+1这个可不可以，如果直到n都不可以，这时候我们回溯到backtrack(t-1)去重新决定x[t-1]要放什么元素
           }
}

分支限界法的基本策略

(自己的不严谨语言描述版)
同回溯法一样，先构造出解空间，一般是树的数据结构，形成解空间树
同回溯法一样，选取一个结点作为扩展结点，之后与回溯法(深度搜索优先)不同的是，分支限界法在扩展结点处会先遍历其所有的子结点(分支)。然后根据剪枝函数，确定哪些子节点将导致不可行或者非最优解(具体根据题意是要找可行还是找最优解)。将这些子节点剔除，也就是将子节点以及他的分支剪掉。完成之后将剩下的这些子节点构造成当前的活结点表。之后从该表中选取一个结点为当前的扩展，之后继续重复上述过程。

根据从活结点表中选取新的扩展结点的方式不同可以分为
1.队列式FIFO分支限界法 和 2.优先队列式分支限界法 两种不同的分支限界法

其中队列式FIFO分支限界法，将活结点表组织成一个队列，并按队列的先进先出FIFO原则选取下一个结点作为当前扩展结点

优先队列式分支限界法，将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级，选取剩余队列中优先级最高的下一个结点作为当前扩展结点；

和回溯法的异同