目录
思维导图
追溯法的基本步骤
基本思想
递归追溯
重复回溯
子集树和数组树
应用示例
思维导图
追溯法的基本步骤
一般分为三个步骤
)针对给定的问题，定义问题的解空间
)确定易搜索解空间结构
)3)用深度优先搜索方式搜索解空间，在搜索中用剪枝函数避免无效搜索(边界函数和制约条件)
在基本思想理解空间的组织结构确定后，回溯法从起始节点(根节点)出发，对整个解空间进行深度优先搜索。 该开始节点成为活动节点，同时成为当前的扩展节点。 在当前扩展节点中，搜索在深度方向上移动到新节点。 这个新节点成为新的活节点，成为现在的扩展节点。 如果在现在的扩展节点中不能再向纵深方向移动的话，现在的扩展节点就会成为死节点。 此时，返回至最近一个活动节点，该活动节点为当前扩展节点。 回溯法就是这样递归地搜索解空间，直到找到要求的解或者解空间中没有活着的节点为止。
基于递归回溯法的解空间深度优先搜索一般可以用递归函数来实现：
这里，形式参数t表示递归深度，即当前扩展节点在解空间树中的深度。 n用于控制递归深度，在tn时，算法已经搜索了叶节点。 此时，记录或输出由output(x )得到的可执行解x。 在算法Backtrack的for循环中，f(n，t )和g ) n，t )分别表示在当前扩展节点中未被搜索的子树的起始编号和结束编号。 h(I )表示当前扩展节点中x(t )的第I个选项值。 constraint(t )和Bound(t ) t表示当前扩展节点上的约束和边界函数。 如果constraint(t )返回值为true，则当前扩展节点中的x(1:t )可取值满足问题的制约条件，否则不满足问题的制约条件，可以切去相应的子树。 如果bound(t )返回值为true，则在当前扩展节点中x(1:t )的值没有越过目标函数，因此backtrack ) t1 )需要进一步搜索对应的子树。 否则，当前扩展节点的x[1:t]的值能够越过目标函数，并截取对应的子树。 执行算法的for循环后，搜索了当前扩展节点的所有未搜索的子树。 backtrack(t )运行完成，返回t-1层并继续运行，继续查找尚未测试的x ) t-1 )的值。 如果t=1，则测试x[1]的所有选项值后，所有外部调用都将终止。 很明显，这个搜索过程是以深度优先进行的。 调用一次backtrack(1)即可完成整个回溯搜索过程。
回溯也可以采用树的非递归深度优先遍历算法，将回溯法表示为非递归迭代过程。
当部分集合树和并树给定的问题是从n个要素的集合s中找到满足某一性质的部分集合时，将对应的解空间树称为部分集合树。 例如，对应n个物品的0-1背包问题的解空间树是子集树。 这样的子集树通常有2￣n个叶节点，其节点总个数为2￣(n1 )-1。 遍历子集树的算法需要o(2^n )的计算时间。
给定的问题是决定n个要素满足某一性质的数组时，将对应的解空间树称为数组树。 林荫道上通常有n！ 叶子的节点。 因此，遍历数组树需要o(n )！ 的计算时间。 例如旅行销售员问题的解空间树是数组树。
正在呼叫b
acktrack(1)执行回溯搜索前，先将变量数组x初始化为单位排列(1,2,…, n)。 应用举例这里列举几个例子理解一下回溯算法
1.n后问题
（1）问题描述
在n*n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于，在n*n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
（2）算法设计思想
需要借助全局变量记录此时第i个皇后在第几列，和一个记录解的个数。从第一个皇后（k=1）开始，如果k>n说明到叶节点即找到了一个可行解，输出，然后回退继续找。如果k<n，从第一列开始判断这个皇后放的位置合不合适，如果都不合适，剪枝，回退；如果合适，继续往下找。如果回退到根节点，即退出程序，算法结束。
回溯算法代码描述可如下：
bool check(int k){for(int i=1;i<k;i++){if((abs(k-i)==abs(p[k]-p[i]))||p[k]==p[i])return false;}return true;}void find(int k){if(k>n){sum++; printanswer();}else{for(int i=1;i<=n;i++){p[k]=i;if(check(k)){find(k+1);}}}}解决n后问题的非递归迭代回溯法如下：
bool check(int k){for(int i=1;i<k;i++){if((abs(k-i)==abs(p[k]-p[i]))||p[k]==p[i])return false;}return true;}void find(int k){p[k]=0;while(k>0){p[k]+=1;//从第一列开始找 while(p[k]<=n&&(!check(k)))//剪枝 p[k]+=1; if(p[k]<=n){ if(k==n){//找到可行解，输出 sum++; printanswer(); } else{ k++; p[k]=0; } } else k--;//不满足，返回上一层 }}2.0-1背包问题
（1）算法描述：
首先将输入的数据按性价比进行排序（从小到大，按单位重量），这里利用结构体（结构体里有序号，价值，重量，单位价值）在排序的时候比较好排。从第一个物品(a=1)开始放，如果a>n即找到一条分支的叶节点，取到最优价值，然后把此时记录的最优方案输出（用一个数组，装入背包此时对应的点为1）。如果a<n，则判断装入此时的物品背包是否在承重范围内，在的话标记为1，临时记录的价值和重量加上此物品的价值和重量，继续往后找。如果重量超背包承重，回退，考虑右子树，如果后面的预算比当前记录的最优价值还大，可以继续，如果小，剪枝，再往后找。
（2）回溯算法可描述如下：（核心代码—）
bool bound(int i){int w=bw;int v=bv;while(w+s[i].wi<=weight&&i<=n){w+=s[i].wi;v+=s[i].vi;i++;}if(i<=n){v+=(weight-w)*s[i].wi;}if(v>bestv){return true;}return false;}void find(int a){ if(a>n){ bestv=bv; for(int i=1;i<=n;i++){//找到最优方案，存入装入方案 b[i]=x[i]; } print(); return; } if(bw+s[a].wi<=weight){ x[s[a].id]=1; bv+=s[a].vi; bw+=s[a].wi; find(a+1); bv-=s[a].vi; bw-=s[a].wi; x[s[a].id]=0; } if(bound(a+1)){ x[s[a].id]=0; find(a+1); }}3.图的m着色问题
（1）问题描述
给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法，使G中每条边的2个顶点着有不同颜色?这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。
（2）算法设计
算法设计思想：利用回溯法，如果当前节点k>n说明到了叶节点，即可以输出一种解决方案，如果不是，则在非叶节点。此时利用记录数组p[k]来记录k点着色，判断是否符合条件，即判断与此点相邻的边得点的着色是否和本点的着色相同，相同话剪枝，不相同则继续往后找。
关键代码如下
bool bound(int x){for(int i=1;i<=n;i++){if(graph[i][x]==1&&p[i]==p[x])//如果两个边相连并且颜色一样 return false;}return true;}void find(int x){if(x>n){sum++;print();}else{for(int i=1;i<=m;i++){p[x]=i;if(bound(x)){find(x+1);}p[x]=0;}}}4.旅行售货员问题（TSP）
（1）算法描述
算法设计思想：
从第一个城市出发，即直接从找第二个城市开始，利用回溯法的排列树。刚开始利用记录当前最优的数组记录每一个城市的编号，如果此时k==n，说明找到了叶子节点，如果此时记录的x[n]城市与1号城市相连并且成本比当前记录的最优值小，则更新最优解，如果k<n，从k开始往后找，如果此时x[k]与x[k-1]所记录的城市相连并且成本想加比记录的当前最优小，记录，往后找，否则剪枝并且在当前成本减去刚才加入的，x[k]恢复原值。
关键代码如下：
void find(int k){if(k==n){//走到最后一个城市 if(a[x[n]][1]!=0&&(now+a[x[n]][1]<bst)){//如果第n个城市和第一个城市想通并且成本小于此时存的最优成本 bst=now+a[x[n]][1];for(int i=1;i<=n;i++){b[i]=x[i];//记录最优 }}}else{for(int i=k;i<=n;i++){//从本城市开始 if(a[x[k-1]][x[i]]&&now+a[x[k-1]][x[i]]<bst){ //如果和上一个记录的城市相连并且成本小于当前记录的最优成本 swap(x[k],x[i]);now+=a[x[k-1]][x[k]];find(k+1);now-=a[x[k-1]][x[k]];swap(x[k],x[i]);}}}}