回溯法,按照百度百科的介绍,是指一种选优的搜索法,按照选优条件向前搜索,以达到目标,但当搜索到某一步时发现原先的选择并不优或者不能达到目标,则退回上一步重新选择,这种走不通就退回重新选择再走的方法就是回溯法。
可用回溯法求解的问题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个子网格的编排如下所示:
0 | 1 | 2 |
3 | 4 | 5 |
6 | 7 | 8 |
对于用于标识元素在大的9*9网格中位置的变量i和j,有0<=i,j<=8,为了获取(i,j)元素在哪个小子网格中,我们做如下处理
i | i/3 | j | j/3 |
0 | 0 | 0 | 0 |
1 | 0 | 1 | 0 |
2 | 0 | 2 | 0 |
3 | 1 | 3 | 1 |
4 | 1 | 4 | 1 |
5 | 1 | 5 | 1 |
6 | 2 | 6 | 2 |
7 | 2 | 7 | 2 |
8 | 2 | 8 | 2 |
假设k为小的3*3子网格的序号,则我们根据下面的关系可以得到(i,j)与k的关系
i/3 | j/3 | k |
0 | 0 | 0 |
0 | 1 | 1 |
0 | 2 | 2 |
1 | 0 | 3 |
1 | 1 | 4 |
1 | 2 | 5 |
2 | 0 | 6 |
2 | 1 | 7 |
2 | 2 | 8 |
我们可以容易得到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