浅析回溯算法

 

1、回溯法的基本思想

（1）在确定解空间的组织结构后，回溯法从开始结点（根结点）出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成为当前的扩展结点。

（2）在当前扩展结点处，搜索向纵深方向移至一个新结点。这个新结点成为新的活结点，并成为扩展结点。

（3）如果在当前扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）到最近的活结点处，并使该结点成为当前的扩展结点。

（4）回溯法按上述方式递归地在解空间中搜索，直到找到所要求的解或返回至根结点为止。

2、两种类型的解空间树

子集树：当所给的问题是从n个元素的集合S中找出S满足某种性质的子集时,相应的解空间树被称为子集树。

排列树：当所给问题是确定ｎ个元素满足某种性质的排列时，相应的解空间树被称为排列树。

3、例题分析

（1）背包问题：给定n种物品和1个背包，物品i的重量是wi，其价值为vi，背包的容量为C。要求选择装入背包的物品，使得装入背包中物品的总价值最大。

     分析：从n种物品中选择若干种物品放入背包。加入一个物品，把背包里的物品看成一个集合，则这个集合是含n种物品的集合的子集.所以这是一个子集树的空间树.从物品的角度来看，每一种物品只有两种选择，放入背包或者不放入背包。设有m种物品，所以可以确定有物品的个数（假设m种全放入背包，当然为0其实是没有放入的）。这样的话就是排列树。减枝函数是基于不能超过背包的最大容量来减少搜索次数。

    核心代码：

//回溯搜索解

void search(int n)

{

         int i,j,temp;

         int sum=0;

         if(n==m)

                   return;

         //选择物品

         for(i=0;i<2;i++){

                   temp=remark[n];

                   remark[n]=i;

                   if(!overWeight(n)){//减枝

                            sum=0;

                       for(j=0;j<=n;j++)

                                     sum+=cost[j]*remark[j];

                            if(sum>allValue)

                                     allValue=sum;

                            search(n+1);

                            //注意回溯时返回上一个值

                            remark[n]=temp;

                   }

         }

}

（2）问题描述：1000元购物卷购买m种不同价格的东西，刚好用完1000元的解决方案

     分析：这个题目跟背包问题很相似.采用子集树的解空间树.搜索的时候有两种方式：如这题我是先搜索到叶子结点，判断是否满足要求，然后在回溯到上一个状态继续搜索.这样的话代码里面不需要保存上一个状态的值。上一题我的做法是搜索到一个结点就判断是否满足条件，不满足马上返回。这样的话要保存上一个状态的值。

      核心代码：

//递归寻找符号条件的方案  

void calculate(int index)  

{  

    int i,sum=0;  

    if(index==m){//递归出口  

        for(i=0;i<m;i++)  

            sum+=count[i]*price[i];  

        if(sum==MONEY){//找到一种方案，记录下当时的各类商品个数  

            for(i=0;i<m;i++)  

               remark[k][i]=count[i];  

            k++;  

        }  

        return;  

    }  

    for(i=0;i<=max_count[index];i++){  

        count[index]=i;  

        calculate(index+1);//递归  

    }  

}  

（3）农夫过河问题：有一个农夫，带着一只狼、一只羊、一颗白菜过河。其中农夫不在的时候狼会吃羊，羊会吃白菜。只有一只船，且每次农夫最多只能带一样物品过河。求解决方案。

分析：这个问题是子集树问题，因为我们无法确定要走多少步才能全部过河。用for循环来选一个跟农夫一起过河或农夫单独过河。然后检查当前状态是否安全。不安全则返回.

当搜索完某一个状态的所有下一个状态时回溯.

核心代码：

         //狼单独过河或者选择一个一起过河.i=0表示农夫单独过河

         for(i=0;i<4;i++){

                   if(sign[i]==dir)

                            continue;

                   sign[0]=dir;

        if(i)

                            sign[i]=dir;

                   if(safe()){

                            remark[step][0]=sign[0];

                            remark[step][1]=sign[1];

                            remark[step][2]=sign[2];

                            remark[step++][3]=sign[3];

            dir=dir==0;//注意改变方向

 

                            cross();//递归

 

                            //注意回溯时返回上一个状态变量的值

                            step--;

                            dir=dir==0;

                   }

                   sign[0]=sign[0]==0;

                   if(i)

                            sign[i]=sign[i]==0;

         }

（4）其他例题：

     倒水问题：（每次两个桶互相倒水）

http://touch-2011.iteye.com/admin/blogs/1038893

     马的遍历：（传入的是坐标（i，j））

     http://touch-2011.iteye.com/admin/blogs/1044260

     八皇后问题：

     http://touch-2011.iteye.com/admin/blogs/1038918

     迷宫求解：

     http://touch-2011.iteye.com/admin/blogs/1033585

     青蛙互换位置游戏：

 

 

 

/**
 *  背包问题
 * 
 **/

#include<stdio.h>

#define CAPACITY 30 //背包总容量
#define MAX_NUM  10 //最多输入的物品数量
int weight[MAX_NUM];//物品重量
int cost[MAX_NUM];  //物品价值
int remark[MAX_NUM]={0};//记录各个物品的个数
int allValue=0;
int m; //输入的物品个数

//初始化背包信息
void init()
{
	int i;
	printf("输入物品数量：\n");
	scanf("%d",&m);
	printf("依次输入物品：\n重量   价值\n");
	for(i=0;i<m;i++)
		scanf("%d%d",&weight[i],&cost[i]);
}

//判断是否超重
int overWeight(int n)
{
    int i;
	int sum=0;
	for(i=0;i<=n;i++)
		sum+=remark[i]*weight[i];
	return sum>CAPACITY;
}

//回溯搜索解
void search(int n)
{
	int i,j,temp;
	int sum=0;
	if(n==m)
		return;
	//选择物品
	for(i=0;i<2;i++){
		temp=remark[n];
		remark[n]=i;
		if(!overWeight(n)){//减枝
			sum=0;
    		for(j=0;j<=n;j++)
				sum+=cost[j]*remark[j];
			if(sum>allValue)
				allValue=sum;
			search(n+1);
			//注意回溯时返回上一个值
			remark[n]=temp;
		}
	}
}

void main()
{
	int i;
	init();
	search(0);
	printf("总价值：%-4d\n",allValue);
	printf("物品个数：\n");
	for(i=0;i<m;i++)
		printf("%-4d",remark[i]);
	printf("\n");
}

 

 

 

/**
 *  农夫过河问题
 **/

#include<stdio.h>
#define MAX_STEP  50

//记录农夫、狼、羊、白菜是否过河。为0表示没过河，为1表示已经过河
int sign[4]={0};
//记录各个状态
int remark[MAX_STEP][4]={0,0,0,0};
int step=1;
//指示下一个要走的方向，0表示回来，1表示过河
int dir=1;


//判断当前状态是否安全
int safe()
{
	int i;
	//狼羊单独呆一起
    if(sign[1]==sign[2] && sign[2]!=sign[0])
	     return 0;
	//羊白菜单独呆一起
    if(sign[3]==sign[2] && sign[2]!=sign[0])
		 return 0;
	for(i=0;i<step;i++)
		//这个状态出现过
       if(remark[i][0]==sign[0] && remark[i][1]==sign[1]
		   && remark[i][2]==sign[2] && remark[i][3]==sign[3])
		 return 0;
	return 1;
}

//过河
void cross()
{
	int i;
	//全部过河
    if(remark[step-1][0] && remark[step-1][1]
		&& remark[step-1][2] && remark[step-1][3]){
		for(i=0;i<step-1;i++){
			if(remark[i+1][0]-remark[i][0]>0)
				printf("第%d步：农夫过河  ",i+1);
			else if(remark[i+1][0]-remark[i][0]<0)
				printf("第%d步：农夫回来  ",i+1);
			if(remark[i+1][1]-remark[i][1]>0)
				printf("狼过河  ",i+1);
			else if(remark[i+1][1]-remark[i][1]<0)
				printf("狼回来  ",i+1);
			if(remark[i+1][2]-remark[i][2]>0)
				printf("羊过河  ",i+1);
			else if(remark[i+1][2]-remark[i][2]<0)
				printf("羊回来  ",i+1);
			if(remark[i+1][3]-remark[i][3]>0)
				printf("白菜过河  ",i+1);
			else if(remark[i+1][3]-remark[i][3]<0)
				printf("白菜回来  ",i+1);
			printf("\n");
		}
		printf("finish\n");
		return ;
	}
		 
	//狼单独过河或者选择一个一起过河.i=0表示农夫单独过河
	for(i=0;i<4;i++){
		if(sign[i]==dir)
			continue;
		sign[0]=dir;
        if(i)
			sign[i]=dir;
		if(safe()){
			remark[step][0]=sign[0];
			remark[step][1]=sign[1];
			remark[step][2]=sign[2];
			remark[step++][3]=sign[3];
            dir=dir==0;//注意改变方向

			cross();//递归

			//注意回溯时返回上一个状态变量的值
			step--;
			dir=dir==0;
		}
		sign[0]=sign[0]==0;
		if(i)
			sign[i]=sign[i]==0;
	}
}

void main()
{
	cross();
}