2019-04-16

算法

10 分钟读完 (大约 1444 个字)

算法-回溯

概述

　　回溯法有”通用解题法”之美称，是一种比枚举”聪明”的效率更高的搜索技术。回溯在搜索过程中动态地产生问题的解空间，系统地搜索问题的所有解。与枚举相比，回溯法的”聪明”之处在于能适时”回头”，若再往前走不可能得到解，就回溯，退一步另找线路，这样可省去大量的无效操作。因此，回溯与枚举相比，回溯更适合量比较大，候选解比较多的案例求解。

　　回溯法是一种试探求解的方法：通过对问题的归纳分析，找出求解问题的一个线索，沿着这一线索往前试探，若试探成功，即得到解：若试探失败，就逐步往回退，换其他路线再往前试探。因此，回溯法可以形象地概括为＂向前走，碰壁回头＂，这样可大大缩减无效操作，提高搜索效率。

相关例题

　　通过举例来学习和理解应该最有效的方法

1.皇后问题

　　在n*n的的方格棋盘上放置n个皇后，使她们互不攻击，即任意两个皇后不允许处在同一横排，同一纵列，也不允许处在同一与棋盘边框成45°角的斜线上

1.1递归回溯法

import java.util.Scanner;

public class 皇后_回溯_递归回溯法 {  //0表示此位置没有放置皇后 ，1表示已经放置
	static int s,sum=0;
	static int []ar;   //用来存放答案的 数组
	static int [][]arr;  //用二维数组表示棋盘
	public static void main(String args[]){
		Scanner in=new Scanner(System.in);
		s=in.nextInt();
		ar=new int[s];
		arr=new int [s][s];
		for(int i=0;i<s;i++)
			for(int j=0;j<s;j++)
				arr[i][j]=0;
		put(0); //从第一行 开始 放置皇后
		System.out.println(sum);
	}
	public static void put(int n){    //回溯函数
		if(n==s){//当n=s说明所有行上 都已经成功放置皇后。
			for(int k=0;k<s;k++){
				System.out.print(ar[k]+" ");//输出 一个解
			}
			sum++;
			System.out.println();
			return ;//返回上一层
		}
		for(int i=0;i<s;i++){   
			ar[n]=i;  
			if(OkPut(n,i)) arr[n][i]=1;// 尝试在第n行第i列放置皇后，放置成功令arr[n][i]=1
			else continue;
			put(n+1);// 如果放置成功  进入下一行
			arr[n][i]=0;// 回溯的关键， 如果在下一层找不到解，则让此位置变为0（未放置状态）
		}
		return ;
	}
	public static boolean OkPut(int n,int i){ //此函数用来判断第n行第i列能否放下皇后
		for(int t=n-1;t>=0;t--)//判断正上方 是否已经放置皇后
			if(arr[t][i]==1) return false;
		for(int w=n-1,s=i-1;w>=0&&s>=0;w--,s--)  //判断左上方是否放置皇后
			if(arr[w][s]==1) return false;
		for(int z=n-1,x=i+1;z>=0&&x<s;z--,x++) // 判断右上方是否放置皇后
			if(arr[z][x]==1) return false;
		return true;
	}
}

1.2迭代回溯法

import java.util.Scanner;
public class 皇后问题_回溯_迭代回溯法 {
	static int ar[];//存放解
	static int sum=0,n;//解的个数 和规模
	static Scanner in;
	static boolean b;
	public static void main(String args[]){
		in=new Scanner(System.in);
		n=in.nextInt();
		ar=new int[n];
		hui();
		System.out.println(sum);
	}
	public void hui(){//迭代回溯法
		int i=0; ar[i]=0;//初值，相当于棋盘的(0,0)位置
		while(true){
			b=true;//b=true 代表当前位置能放下皇后,false表示不能
			for(int h=i-1;h>=0;h--)//此循环是判断能否放下皇后
				if(ar[i]==ar[h]||Math.abs(ar[i]-ar[h])==i-h) b=false;
            //ar[i]==ar[h]判断上方是否存在皇后, Math.abs(ar[i]-ar[h])==i-h判断左上角和右上角是否存在皇后。 ps：abs(doubls n) 取绝对值
			if(b&&i==n-1){//到达最后一层且 当前位置能放下皇后，输出一个解
				sum++;
				for(int k=0;k<n;k++){
					System.out.print(ar[k]+" ");
				}	
				System.out.println();
			}
			if(i<n-1&&b){//没到最后一层，且能放下皇后，进入下一层相当于递归回溯的put(n+1)
				i++;
				ar[i]=0;	
				continue;
			}
			while(ar[i]==n-1&&i>0){//当前层已达到规模还未找到解且不是第一层，进行回溯
				i--;//进入下一层
			}
			if(ar[i]==n-1&&i==0) break;//如果第一层已到达规模，说明所有解已经尝试完，结束循环
			else ar[i]+=1;//否则当前层数尝试下一个解
		}
	}
}

2.桥本分数式

　　将1，2，3，…，9这九个数字填入下式的9个方格中（数字不能重复），使下面的分数等式成立：

口/口口+口/口口=口/口口

2.1递归回溯法

public class 桥本分数式_递归回溯法 {
	static int [] ar;//存放解的数组
	public static void main(String args[]) {
		ar=new int [9];
		put(0);
	}
	public static void put(int n){//回溯函数
		if(n==9){//当n=9说明9个数字已经全部放入方块中
			if(b(ar)&&ar[0]<ar[3]) pritf(ar);//ar[0]<ar[3]去掉重复解，比如1/26+5/78=4/39和5/78+1/26=4/39为同一个解
			return ;
		}
		for(int i=1;i<10;i++){
			if(is(n,i)) ar[n]=i;//判断第n+1个方块能否放下数字i
			else continue;
			put(n+1);//进入下一层
		}
		return ;
	}
	public static boolean is(int n,int i){
		for(int j=0;j<n;j++){
			if(ar[j]==i) return false;
		}
		return true;
	}
	public static boolean b(int []a){//判断是否满足口/口口+口/口口=口/口口这个式子
		int  a1=a[0]*(a[7]*10+a[8])*(a[4]*10+a[5]);
		int  a2=a[3]*(a[1]*10+a[2])*(a[7]*10+a[8]);
		int  a3=a[6]*(a[1]*10+a[2])*(a[4]*10+a[5]);
		if(a1+a2==a3) return true;
		return false;
	}
	public static void pritf(int []a){//打印函数
		for(int k=0;k<9;k++){
			System.out.print(a[k]+" ");
		}
		System.out.println();
	}
}

2.2迭代回溯法

public class 桥本分数式_迭代回溯法 {
	static int ar[],i,sum=0;
	static boolean b;
	public static void main(String args[]){
		ar=new int [9];
		hui();
		System.out.println(sum);
	}
	public void hui(){//回溯函数
		i=0;ar[i]=1;
		while(true){
			b=true;
			for(int k=i-1;k>=0;k--){
				if(ar[k]==ar[i]) {b=false; break;}//判断前面是否有相同的数
			}
			if(i==8&&b&&ar[0]<ar[3]&&b(ar)){//到达最后一层且数字与前面无重复且ar[0]<ar[3]（除去重复解）且满足题目约束条件
				pritf(ar);//输出解
				sum++;//解+1
			}
			if(i<8&&b){//进入下一层
				i++;
				ar[i]=1;
				continue;
			}
			while(ar[i]==9&&i>0) i--;//当其中一层的值到达9，回溯
			if(ar[i]==9&&i==0) break;//第一层的值到达9，结束
			else ar[i]++;
		}
	}
	public static boolean b(int []a){//判断函数
		int  a1=a[0]*(a[7]*10+a[8])*(a[4]*10+a[5]);
		int  a2=a[3]*(a[1]*10+a[2])*(a[7]*10+a[8]);
		int  a3=a[6]*(a[1]*10+a[2])*(a[4]*10+a[5]);
		if(a1+a2==a3) return true;
		return false;
	}
	public static void pritf(int []a){//打印函数
		for(int k=0;k<9;k++){
			System.out.print(a[k]+" ");
		}
		System.out.println();
	}
}

总结

1.递归回溯法

　　递归设计思路容易，但效率较低。基本上是由一个函数实现，当满足条件则进入下一层。当层数达到条件时，进入判断，满足则找到一个解。

　　关键点在于通过不断调用函数put(int n)进入下一层

基本框架为：

int ar[];//用来存放解
void put(int n){
    if(n==（规模）){//每一层都找到了合适解
        if(（约束条件）){
            printf(（输出一个解）);
        }
        return ;//返回上一层
    }
    for(int k=0;k<(规模);k++){
        if(（约束条件）){//满足约束条件。则找到这一层的解
            ar[n]=k;//赋值
        }else continue;//不满足 则尝试下一个值
        put(n+1);//进入下一层
    }
    return ;//这一层没有找到合适的解，返回下一层
}

2.迭代回溯法

　　相对于递归回溯法来说，迭代回溯法设计思路较为复杂，但效率比递归回溯法高。ps:两个算法的设计模式没有多大的区别，彻底理解递归回溯后，迭代回溯应该没什么问题。

基本框架：

int i=1 ,ar[i]=（元素最初值）;
boolean b;
while(true){
    b=true;
    for(k=i-1;k>=1;k--)
        if(（约束条件1）) b=false;//不合适 ，将b切换为false
    if(b&&i==（规模）&&（约束条件2）) pritf(一个解);
    if(b&&i<（规模）){
        i++;
        ar[i]=（元素最初值）;
        continue;
    }
    while(a[i]==（回溯点）&&i>1) i--;
    if(ar[i]==（规模）&&i==1) break;
    else a[i]+=1;
}

3.自己的想法

　　写到这里应该差不多了，如果能看懂这两个例题应该能基本掌握回溯的思想了(当然，想要真正掌握这些知识是完全不够的)。ps：其实是自己不想写了，累了！