回溯法（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;
  }

（八）回溯法