回溯法及举例分析

系统管理员 2022-05-16 08:19 139阅读 0赞

回溯法，按照百度百科的介绍，是指一种选优的搜索法，按照选优条件向前搜索，以达到目标，但当搜索到某一步时发现原先的选择并不优或者不能达到目标，则退回上一步重新选择，这种走不通就退回重新选择再走的方法就是回溯法。

可用回溯法求解的问题P一般可以被如下描述：对于已知的由n元组（x1，x2，…，xn）组成的一个状态空间E=\{（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n\}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且 |Si| 有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。

对于许多问题，所给定的约束集D具有完备性，即i元组（x1，x2，…，xi）满足D中仅涉及到x1，x2，…，xi的所有约束意味着j（j<=i）元组（x1，x2，…，xj）一定也满足D中仅涉及到x1，x2，…，xj的所有约束，i=1，2，…，n。换句话说，只要存在0≤j≤n-1，使得（x1，x2，…，xj）违反D中仅涉及到x1，x2，…，xj的约束之一，则以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）一定也违反D中仅涉及到x1，x2，…，xi的一个约束，n≥i≥j。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（x1，x2，…，xj）违反D中仅涉及x1，x2，…，xj的一个约束，就可以肯定，以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）都不会是问题P的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。

使用回溯法的一般步骤：

（1）针对特定问题，确定问题的解空间

（2）确定易于搜索的解空间结构

（3）以深度优先方式搜索解空间，并在搜索过程中用减枝函数避免无效搜索。

下面我们讲述几个使用回溯法的例子。

首先我们先看一个关于象棋的问题，假设我们在一个4\*4的棋盘上有一个马，马的位置为（1,1）点，当然也可以是其它点，我们要求列出所有的从（1,1）出发，最终能够回到起点的所有走法。

下面我们给出实现

package com.application.sample;
    
    //使用回溯思想
    
    public class backtrackingSample1 {
    	static int[][] direction = {
       {-1, -1, -2, -2, 2, 2, 1, 1},{-2, 2, 1, -1, 1, -1, 2, -2}};
    	private int[][] chess;
    	private int x,y;
    	
    	private int total=0;
    	
    	public backtrackingSample1(int x,int y)
    	{
    		this.x=x;
    		this.y=y;
    		this.chess=new int[4][4];
    		chess[x][y]=1;
    	}
    	
    	private void output()
    	{
    //		if(isOneStep())
    //		{
    //			System.out.println("Total:"+this.total);
    //			for(int i=0;i<4;i++)
    //			{
    //				for(int j=0;j<4;j++)
    //				{
    //					System.out.print(chess[i][j]+" ");
    //				}
    //				System.out.println();
    //			}
    //			System.out.println();
    //		}
    		System.out.println("Total:"+this.total);
    		for(int i=0;i<4;i++)
    		{
    			for(int j=0;j<4;j++)
    			{
    				System.out.print(chess[i][j]+" ");
    			}
    			System.out.println();
    		}
    		System.out.println();
    	}
    	
    	public void findway(int posx,int posy,int step)
    	{
    		int px,py;
    		for(int i=0;i<8;i++)
    		{
    			px=posx+direction[0][i];
    			py=posy+direction[1][i];
    			if(px>=0&&px<=3&&py>=0&&py<=3)
    			{
    				if(px==this.x&&py==this.y)
    				{
    					this.total++;
    					this.output();
    				}else if(chess[px][py]==0)
    				{
    					chess[px][py]=step;
    					findway(px,py,step+1);
    					chess[px][py]=0;
    				}
    			}
    		}
    	}
    	
    	public boolean isOneStep()
    	{
    		boolean result=true;
    		for(int i=0;i<4;i++)
    		{
    			for(int j=0;j<4;j++)
    			{
    				if(chess[i][j]>2)
    				{
    					return false;
    				}
    			}
    		}
    		return result;
    	}
    	
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		backtrackingSample1 sample=new backtrackingSample1(1,1);
    		long start=System.currentTimeMillis();
    		sample.findway(1, 1, 2);
    		long end=System.currentTimeMillis();
    		System.out.println("用时："+(end-start)+"毫秒");
    	}
    
    }

运行结果如下所示：

Total:1 0 0 5 2 4 1 0 0 0 0 3 6 0 0 0 0 Total:2 9 12 5 2 4 1 8 11 13 10 3 6 0 7 14 0 ........

Total:369
    0 6 0 0 
    4 1 10 7 
    11 8 5 2 
    0 3 12 9 
    
    Total:370
    0 0 0 0 
    4 1 0 0 
    0 0 5 2 
    6 3 0 0 
    
    用时：78毫秒

接下来我们看另外一个经典的问题九宫格。九宫格就是一个9\*9的网格，而这个网格又可以被分成9个3\*3的子网格，向网格中填入1~9的数字，要求每行，每列以及每个子网格中1-9都只出现一次，即不能有重复数字出现。如下所示，0表示待填入数据的格子

103000509  
002109400  
000704000  
300502006  
060000050  
700803004  
000401000  
009205800  
804000107  
  
我们将9个子网格的编排如下所示：

对于用于标识元素在大的9\*9网格中位置的变量i和j，有0<=i,j<=8，为了获取(i,j)元素在哪个小子网格中，我们做如下处理

假设k为小的3\*3子网格的序号，则我们根据下面的关系可以得到(i,j)与k的关系

我们可以容易得到k=(i/3)\*3+(j/3)；

下面给出java的实现：

package com.application.sample;
    //使用回溯法求解九宫格问题
    import java.util.Scanner;
    public class BackTrackingSample2 {
    	private int[][] table;
    	private boolean[][] rstate;//rstate[i][value]=true表示value在第i行出现过
    	private boolean[][] cstate;//cstate[j][value]=true表示value在第j行出现过
    	private boolean[][] gstate;//gstate[k][value]=true表示value在第k个小网格中出现过
    	private int[] pos;//存放需要填数字的方格位置
    	private int posnum=0;//需要填的格子总数
    	private boolean flag=false;//搜索结束标志
    	
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		BackTrackingSample2 sample=new BackTrackingSample2();
    		sample.searchSolution(1);
    	}
    	
    	public BackTrackingSample2()
    	{
    		table=new int[9][9];
    		rstate=new boolean[9][10];
    		cstate=new boolean[9][10];
    		gstate=new boolean[9][10];
    		pos=new int[81];
    		System.out.println("输入九宫格的数据（使用0表示待填入数据的格子）：");
    		Scanner in=new Scanner(System.in);
    		String array=null;
    		for(int i=0;i<9;i++)
    		{
    			array=in.nextLine();
    			for(int j=0;j<9;j++)
    			{
    				table[i][j]=array.charAt(j)-'0';
    				if(table[i][j]!=0)
    				{
    					rstate[i][table[i][j]]=true;
    					cstate[j][table[i][j]]=true;
    					int k=(i/3)*3+(j/3);
    					gstate[k][table[i][j]]=true;
    				}else
    				{
    					pos[posnum++]=i*9+j;
    				}
    			}
    		}
    		pos[posnum]=-1;
    	}
    	
    	private void output()//输出结果
    	{
    		System.out.println();
    		System.out.println("结果：");
    		for(int i=0;i<9;i++)
    		{
    			for(int j=0;j<9;j++)
    			{
    				System.out.printf("%2d", table[i][j]);
    			}
    			System.out.println();
    		}
    	}
    	
    	public void searchSolution(int n)//搜索处理第n个待填入数据的格子
    	{
    		if(n>this.posnum)//如果所有的格子都处理完了则输出
    		{
    			output();
    			return;
    		}
    		int row=pos[n-1]/9;//获取第n个待处理格子的坐标位置和子网格位置
    		int column=pos[n-1]%9;
    		int k=(row/3)*3+(column/3);
    		for(int i=1;i<=9&&!flag;i++)//遍历，分别用1-9中的数进行试探
    		{
    			if(rstate[row][i]) //判断数组i在格所在的行和列以及子网格中是否出现过
    				continue;
    			if(cstate[column][i])
    				continue;
    			if(gstate[k][i])
    				continue;
    			table[row][column]=i;//填入该数，并设置标志
    			rstate[row][i]=true;
    			cstate[column][i]=true;
    			gstate[k][i]=true;
    			searchSolution(n+1);//回溯
    			table[row][column]=0;//清除标志
    			rstate[row][i]=false;
    			cstate[column][i]=false;
    			gstate[k][i]=false;
    		}
    		
    	}
    
    }

运行结果如下所示：

输入九宫格的数据（使用0表示待填入数据的格子）：
    103000509
    002109400 
    000704000
    300502006 
    060000050
    700803004 
    000401000
    009205800
    804000107
    
    结果：
     1 4 3 6 2 8 5 7 9
     5 7 2 1 3 9 4 6 8
     9 8 6 7 5 4 2 3 1
     3 9 1 5 4 2 7 8 6
     4 6 8 9 1 7 3 5 2
     7 2 5 8 6 3 9 1 4
     2 3 7 4 8 1 6 9 5
     6 1 9 2 7 5 8 4 3
     8 5 4 3 9 6 1 2 7

我们再讲一个比较经典的问题，那就是八皇后问题。什么是八皇后问题呢？八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

Java代码实现如下所示：

package com.application.sample;
    //使用回溯法解决八皇后问题
    
    public class BackTracingSample4 {
    	private boolean[][] table=new boolean[8][8];
    	private int queencount=0;
    	private int total=0;
    	
    	public boolean lineHasQueen(int line)//line列全为false则返回true，否则返回false
    	{
    		for(int i=0;i<8;i++)
    		{
    			if(table[i][line]==true)
    				return true;
    		}
    		return false;
    	}
    	
    	public boolean catercornerHasQueen(int x,int y)//判断对角线方向是否含有皇后，如果有则返回true,否则返回false
    	{
    		int i,j;
    		for(i=x,j=y;i<8&&j<8;i++,j++)
    		{
    			if(table[i][j]==true)
    				return true;
    		}
    		for(i=x,j=y;i>=0&&j>=0;i--,j--)
    		{
    			if(table[i][j]==true)
    				return true;
    		}
    		for(i=x,j=y;i>=0&&j<8;i--,j++)
    		{
    			if(table[i][j]==true)
    				return true;
    		}
    		for(i=x,j=y;i<8&&j>=0;i++,j--)
    		{
    			if(table[i][j]==true)
    				return true;
    		}
    		return false;
    	}
    	
    	public void searchSolution(int line)
    	{
    		if(line==8)
    			return;
    		for(int i=0;i<8;i++)
    		{
    			if((!lineHasQueen(i))&&(!catercornerHasQueen(line,i)))
    			{
    				table[line][i]=true;
    				queencount++;
    				if(queencount==8)
    				{
    					System.out.println();
    					output();
    					table[line][i]=false;
    					queencount--;
    					continue;
    				}
    				searchSolution(line+1);
    				table[line][i]=false;
    				queencount--;
    			}
    		}
    	}
    	
    	public void output()
    	{
    		total++;
    		System.out.println("Total:"+total);
    		for(int i=0;i<8;i++)
    		{
    			for(int j=0;j<8;j++)
    			{
    				if(table[i][j]==true)
    				{
    					System.out.print("1");
    				}else
    				{
    					System.out.print("0");
    				}
    			}
    			System.out.println();
    		}
    		
    	}
    	
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		BackTracingSample4 sample=new BackTracingSample4();
    		sample.searchSolution(0);
    	}
    
    }

运行结果如下所示：

Total:1  
10000000  
00001000  
00000001  
00000100  
00100000  
00000010  
01000000  
00010000

Total:2  
10000000  
00000100  
00000001  
00100000  
00000010  
00010000  
01000000

.............

Total:91  
00000001  
00100000  
10000000  
00000100  
01000000  
00001000  
00000010  
00010000

Total:92  
00000001  
00010000  
10000000  
00100000  
00000100  
01000000  
00000010  
00001000

最后我们来看一个大家基本都见过的题目，那就是上楼梯。对于一个含有n阶的楼梯，如果我们每次只能上一阶或者两阶，问我们总共可以有多少种走法，每种走法怎么走？

对于这个问题，我们很明显也可以使用回溯法进行求解。求解过程如下所示：

package com.application.sample;
    
    public class BackTracingSample5 {
    	private int[] step;	
    	public BackTracingSample5(int n)
    	{
    		step=new int[n+1];
    		step[0]=n;
    	}
    	
    	public void goUp(int level,int n)
    	{
    		if(n>step[0])
    			return;
    		if(n==step[0])
    		{
    			output(level);
    			return;
    		}
    		for(int i=1;i<=2;i++)
    		{
    			step[level+1]=i;
    			goUp(level+1,n+i);
    			step[level+1]=0;
    		}
    	}
    	
    	private void output(int level)
    	{
    		System.out.println("步数："+level);
    		for(int i=1;i<=level;i++)
    		{
    			System.out.print(step[i]+" ");
    		}
    		System.out.println();
    	}
    	
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		BackTracingSample5 sample=new BackTracingSample5(5);
    		sample.goUp(0, 0);
    	}
    
    }

运行结果如下所示：

步数：5  
1 1 1 1 1  
步数：4  
1 1 1 2  
步数：4  
1 1 2 1  
步数：4  
1 2 1 1  
步数：3  
1 2 2  
步数：4  
2 1 1 1  
步数：3  
2 1 2  
步数：3  
2 2 1