回溯法（back track method）也称为试探法，是蛮力法的改进。在包含问题的所有可能解空间中，从根节点处罚，按照深度优先策略进行搜索，对于解空间树的某个节点，如果该节点满足问题的约束条件，则进入该子树继续进行搜索，否则将以该节点为根节点进行剪枝。回溯法常常可以避免搜索所有可能解，适用于组合较数较大的问题。
采用回溯法解决0/1背包问题。
【问题描述】：
例如，对于n=3的0/1背包问题，三个物品的重量为{20, 15, 10}，价值为{20, 30, 25}，背包容量为25，从图8.2所示的解空间树的根结点开始搜索，搜索过程如下。
从物品一号开始，分为两种情况，如果将物品一放入到背包中，或者将物品一不放入背包中，于是节点1的两个分支 2 和9 ， 分支2表示将物品一放到背包中，从节点1到达节点9表示将物品一不放入背包中。同理，依次类推。
这样我们就可以用树的形式展示出各种路径，再分别计算每种方案价值，从而得到最优解。
【C代码】：
int BackTrack(int i)
{
if(i>n-1){
if(bestP<cp){
for (int k=0;k<n;k++) X[k]=cx[k];//存储最优路径
bestP=cp;
}
return bestP;
}
if(cw+a[i].w<=C){ //进入左子树
cw=cw+a[i].w;
cp=cp+a[i].p;
cx[a[i].sign]=1; //装入背包
BackTrack(i+1);
cw=cw-a[i].w;
cp=cp-a[i].p; //回溯，进入右子树
}
cx[a[i].sign]=0; //不装入背包
BackTrack(i+1);
return bestP;
}
int KnapSack3(int n,goods a[],int C,int x[])
{
for(int i=0;i<n;i++)
{
x[i]=0;
a[i].sign=i;
}
sort(a,a+n,m);//将各物品按单位重量价值降序排列
BackTrack(0);
return bestP;
}
利用回溯法解决图的找色问题。
【问题描述】：
给定无向连通图G=(V, E)和正整数m，求最小的整数m，使得用m种颜色对G中的顶点着色，使得任意两个相邻顶点着色不同。
【步骤】：
回溯法求解图的着色问题，首先把所有的定点颜色初始化为0，然后依次为每个顶点着色。在图着色对应的解空间树中，如果从根节点到当前节点对应一个部分解，也就是颜色指派都没有冲突，则在当前节点对应一个部分解，也就是所有的颜色指派都没有冲突，则在当前节点处选择第一颗子树继续搜索，也就是为下一个顶点着色1，否则，对当前子树的兄弟子树继续搜索，也就是为当前顶点着下一个颜色如果所有m种颜色都已尝试过且都发生冲突，则回溯到当前节点的父节点处，上一个顶点的颜色被改变，依次类推。
【例题】：
如下无向图所示，为A，B，C，D，E，分别给每个点着色，着三种颜色 1,2,3。并且相邻的颜色不相同。请问A，B，C，D，E分别着哪种颜色？
利用回溯方法求解解空间，解空间树如下图所示：
【解题说明】：
节点1到2我们给顶点A着色 第一种颜色，从节点2开始我们给无向图的B点着色，节点2到节点3我们给B着色1；当我们给B着色1，出现错误，因为A和B相邻，A已经着色1了，所以B不能再着色1。于是我们回溯到根节点，节点2，增加新的分支，节点2到节点4我们给B着色2，此时不会出现任何的冲突。
我们继续给无向图C点着色，节点4到节点5表示给C着色1，出现冲突回溯到根节点4；节点4到节点6，表示给C着色2，同样会出现冲突，回溯到根节点；节点4到节点7表示给C着色3，不会出现冲突，这样就可以接着给无向图D点着色。
给D着色1，不会出现冲突，这样接着给E着色。因为D已经着色1了，再给E着色1出现冲突；给E着色2出现冲突；给E着色3出现冲突；树中的节点8到11 12 13 分别表示这三种情况。都会出现冲突，这样回溯到根节点7。
根节点7到10表示给D着色3，不会产生冲突。继续给E着色，给E着色1，进行验证，不产生冲突，这样我们就找到了一个合适的解。
图中剪枝的部分为黄色节点的部分，是产生冲突的解。所以最终无向图点ABCDE点的解围为{1,2,3,3,1}。
【C代码部分】：
void GraphColor(int n, int c[ ][ ], int m)
//所有数组下标从1开始
{
for (i=1; i<=n; i++ ) //将数组color[n]初始化为0
color[i]=0;
k=1;
while (k>=1)
{
color[k]=color[k]+1;
while (color[k]<=m)
if Ok(k) break;
else color[k]=color[k]+1; //搜索下一个颜色
if (color[k]<=m && k= =n) //求解完毕，输出解
{
for (i=1; i<=n; i++)
cout<<color[i];
return;
}
else if (color[k]<=m && k<n)
k=k+1; //处理下一个顶点
else {
color[k]=0;
k=k-1; //回溯
}
}
}
bool Ok(int k) //判断顶点k的着色是否发生冲突
{
for (i=1; i<k; i++)
if (c[k][i]= =1 && color[i]= =color[k])
return false;
return true;
}
本节完毕，下一节分支限界算法。