回溯法Java语言

1、算法思考，初步思路：构建二维int或者short型数组，内存中模拟棋盘chessrc=0表示：r行c列没有皇后，chessrc=1表示：r行c列位置有一个皇后从第一行第一列开始逐行摆放皇后依题意每行只能有一个皇后，遂逐行摆放，每行一个皇后即可摆放后立即调用一个验证函数（传递整个棋盘的数据），验证合理性，安全则摆放下一个，不安全则尝试摆放这一行的下一个位置，直至摆到棋盘边界当这一行所有位置都无法保证皇后安全时，需要回退到上一行，清除上一行的摆放记录，并且在上一行尝试摆放下一位置的皇后（回溯算法的核心）当摆放到最后一行，并且调用验证函数确定安全后，累积数自增1，表示有一个解成功算出验证函数中，需要

2、扫描当前摆放皇后的左上，中上，右上方向是否有其他皇后，有的话存在危险，没有则表示安全，并不需要考虑当前位置棋盘下方的安全性，因为下面的皇后还没有摆放回溯算法的天然实现是使用编译器的递归函数，但是其性能令人遗憾下面我们使用上面的思路初步实现8皇后的问题解法，并且将所有解法打印出来，供我们验证正确性import java.util.Date;/* * 在88格的国际象棋上摆放八个皇后，使其不能互相攻击， * 即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 * 下面使用递归方法解决 * author * */public class EightQu

3、een private static final short N=8; /使用常量来定义，方便之后解N皇后问题 private static int count=0; /结果计数器 public static void main(String args) Date begin =new Date(); /初始化棋盘，全部置0 short chess=new shortNN; for(int i=0;iN;i+) for(int j=0;jN;j+) chessij=0; putQueenAtRow(chess,0); Date end =new Date(); System.out.print

4、ln(解决 +N+ 皇后问题，用时： +String.valueOf(end.getTime()-begin.getTime()+ 毫秒，计算结果：+count); private static void putQueenAtRow(short chess, int row) /* * 递归终止判断：如果row=N，则说明已经成功摆放了8个皇后 * 输出结果，终止递归 */ if(row=N) count+; System.out.println(第 + count + 种解：); for(int i=0;iN;i+) for(int j=0;jN;j+) System.out.print(c

5、hessij+ ); System.out.println(); return; short chessTemp=chess.clone(); /* * 向这一行的每一个位置尝试排放皇后 * 然后检测状态，如果安全则继续执行递归函数摆放下一行皇后 */ for(int i=0;iN;i+) /摆放这一行的皇后，之前要清掉所有这一行摆放的记录，防止污染棋盘 for(int j=0;j=0) if(chessrow-stepcol=1) /中上 return false; if(col-step=0 & chessrow-stepcol-step=1) /左上 return false; if(c

6、ol+stepN & chessrow-stepcol+step=1) /右上 return false; step+; return true; 输出结果：需要打印棋盘时，耗时34毫秒，再看一看不需要打印棋盘时的性能：耗时2毫秒，性能感觉还可以。你以为到这儿就结束了吗？高潮还没开始，下面我们来看看这种算法解决9、10、11.15皇后问题的性能稍微变动一下代码，循环打印出各个解的结果，如下图所示：当我开始尝试解决16皇后问题时，发现时间复杂度已经超出我的心里预期，最终没让它继续执行下去。上网一查N皇后的国际记录，已经有科研单位给出了25皇后的计算结果，耗时暂未可知我们的程序跑16皇后已经无能为

7、力，跑15皇后已经捉襟见肘（87秒）中国的一些算法高手能在100秒内跑16皇后，可见上面的算法效率只能说一般，辣么，该如何改进呢？我们发现二维棋盘数据在内存中浪费严重，全是0和1的组成，同时每次递归时使用JAVA的clone函数克隆一个新的棋盘，消耗进一步扩大，这里面一定有改进的方案。我们考虑将二维数组使用一维数组代替，将一维数组的下标数据利用起来，模仿棋盘结构，如chessR=C时，表示棋盘上R行C列有一个皇后这样程序的空间效率会得到迅速提高，同时二维数据改变成一维数据后的遍历过程也会大为缩减，时间效率有所提高，下面贴出代码：import java.util.Date;public clas

8、s EightQueen2 private static final short K=15; /使用常量来定义，方便之后解N皇后问题 private static int count=0; /结果计数器 private static short N=0; public static void main(String args) for(N=9;N=K;N+) Date begin =new Date(); /* * 初始化棋盘，使用一维数组存放棋盘信息 * chessn=X:表示第n行X列有一个皇后 */ short chess=new shortN; for(int i=0;iN;i+) c

9、hessi=0; putQueenAtRow(chess,(short)0); Date end =new Date(); System.out.println(解决 +N+ 皇后问题，用时： +String.valueOf(end.getTime()-begin.getTime()+ 毫秒，计算结果：+count); private static void putQueenAtRow(short chess, short row) /* * 递归终止判断：如果row=N，则说明已经成功摆放了8个皇后 * 输出结果，终止递归 */ if(row=N) count+;/ System.out.p

10、rintln(第 + count + 种解：);/ for(int i=0;iN;i+)/ for(int j=0;jN;j+)/ System.out.print(chessij+ );/ / System.out.println();/ return; short chessTemp=chess.clone(); /* * 向这一行的每一个位置尝试排放皇后 * 然后检测状态，如果安全则继续执行递归函数摆放下一行皇后 */ for(short i=0;i=0;i-) if(chessi=col) /中上 return false; if(chessi=col-step) /左上 return

11、 false; if(chessi=col+step) /右上 return false; step+; return true; 运算结果：可以看到所有结果的耗时缩短了一倍有余，这无疑是一次算法的进步辣么，还有改进空间吗？答案必然是肯定的，对于算法，我们越是精益求精，我们的能力就越强大，我们越是浅尝辄止，我们的进步就越慢。下一篇博客我们来继续改进这个问题的算法，摒弃编译器自带的递归回溯，自己手写回溯过程，相信效率会进一步提高，最终在可控范围内将16皇后问题解出来。8皇后以及N皇后算法探究，回溯算法的JAVA实现，递归方案是使用递归方法实现回溯算法的，在第一次使用二维矩阵的情况下，又做了一次改

12、一维的优化但是算法效率仍然差强人意，因为使用递归函数的缘故下面提供另一种回溯算法的实现，使用数据结构”栈“来模拟，递归函数的手工实现，因为我们知道计算机在处理递归时的本质就是栈时间复杂度是一样的，空间复杂度因为自定义了class，有所上升经过测试其性能甚至低于上篇博客的递归实现权当是使用数据结构”栈“，解决15皇后的代码如下：package com.newflypig.eightqueen;import java.util.Date;import java.util.Stack;/* * 使用数据结构“栈”，模拟递归函数 * 实现非递归方案的回溯算法 * author newflydd189.

13、cn * Time: 2015年12月31日 下午6:13:05 */public class EightQueen3 private static final short N=15; public static void main(String args) Date begin =new Date(); long count=0; /* * 初始化栈和棋盘，并向栈中压入第一张初始化的棋盘 */ Stack stack=new Stack(); short chessData=new shortN; for(short i=1;iN寻找第一个合法解，如果row达到边界count+1，否则pus

14、h进栈 */ Chess chessTemp=chess.clone(); if(chessTemp.moveRow() while(chessTemp.moveCol() if( isSafety(chessTemp) ) if( chessTemp.currentRow=N-1 ) count+; continue; else stack.push(chessTemp); continue EMPTY; Date end =new Date(); System.out.println(解决 +N+ 皇后问题，用时： +String.valueOf(end.getTime()-begin.g

15、etTime()+ 毫秒，计算结果：+count); private static boolean isSafety(Chess chess) / 判断中上、左上、右上是否安全 short step = 1; for (short i = (short) (chess.currentRow - 1); i = 0; i-) if (chess.chessi = chess.currentCol) / 中上 return false; if (chess.chessi = chess.currentCol - step) / 左上 return false; if (chess.chessi =

16、 chess.currentCol + step) / 右上 return false; step+; return true; class Chess implements Cloneable public short chess; /棋盘数据 public short currentRow=0; /当前行 public short currentCol=0; /当前列 public boolean visited=false; /是否访问过 public Chess(short chess) this.chess=chess; public boolean moveCol() this.c

17、urrentCol+; if(this.currentCol=chess.length) return false; else this.chesscurrentRow=currentCol; return true; public boolean moveRow() this.currentRow+; if(this.currentRow=chess.length) return false; else return true; public Chess clone() short chessData=this.chess.clone(); Chess chess=new Chess(che

18、ssData); chess.currentCol=-1; chess.currentRow=this.currentRow; chess.visited=false; return chess; 执行结果：研究了递归方法实现回溯，解决N皇后问题，下面我们来探讨一下非递归方案实验结果令人还是有些失望，原来非递归方案的性能并不比递归方案性能高代码如下：package com.newflypig.eightqueen;import java.util.Date;/* * 使用循环控制来实现回溯，解决N皇后 * author * Time : 2016年1月1日 下午9

19、:37:32 */public class EightQueen4 private static short K=15; private static short N=0; private static boolean dead=false; /下方走到了死路 public static void main(String args) for (N = 9; N = K; N+) Date begin = new Date(); dead=false; long count = 0; /* * -2：初始状态，尚未摆放 -1：开始尝试摆放 0到N-1：皇后安全的摆放在这一列的哪一行 */ sho

20、rt chess = new shortN; for (short i = 1; i =N) /* * 摆到边界，清空当前行的摆放记录，标志死路 */ chessrow=-2; dead=true; return false; chessrow=(short) (chessrow+1); return true; private static short getRow(short chess) short row=(short) (N-1); while(chessrow=-2) row-; return row; private static boolean isSafety(short c

21、hess) short row=getRow(chess); short col=chessrow; /判断中上、左上、右上是否安全 short step=1; for(short i=(short) (row-1);i=0;i-) if(chessi=col) /中上 return false; if(chessi=col-step) /左上 return false; if(chessi=col+step) /右上 return false; step+; return true; 程序中定义了全局变量dead死路标志，告诉循环什么时候需要回溯，什么时候需要继续深搜getRow() 函数返

22、回当前最后摆放皇后的行号，每次摆放皇后和判断安全性时都要调用，所以显得性能偏低下面取消了getRow()函数，使用全局变量row来表示已经摆到那一行的皇后了，用一个小小的变量空间换了一部分时间：package com.newflypig.eightqueen;import java.util.Date;/* * 使用循环控制来实现回溯，解决N皇后 * 开辟两个变量控制行和列，避免不必要的计算，空间换时间 * author * Time : 2016年1月1日 下午9:37:32 */public class EightQueen5 private static s

23、hort K=15; private static short N=0; private static boolean dead=false; /下方走到了死路 private static short row=0; public static void main(String args) for (N = 9; N = K; N+) Date begin = new Date(); row=0; dead=false; long count = 0; /* * -2：初始状态，尚未摆放 -1：开始尝试摆放 0到N-1：皇后安全的摆放在这一列的哪一行 */ short chess = new

24、shortN; for (short i = 1; i =N) /* * 摆到边界，清空当前行的摆放记录，标志死路 */ chessrow=-2; row-; dead=true; return false; chessrow=(short) (chessrow+1); return true; private static boolean isSafety(short chess) short col=chessrow; /判断中上、左上、右上是否安全 short step=1; for(short i=(short) (row-1);i=0;i-) if(chessi=col) /中上 r

25、eturn false; if(chessi=col-step) /左上 return false; if(chessi=col+step) /右上 return false; step+; return true; 最终的执行效率为：这跟我们第一篇博客的递归调用的效率：还是有些差距，所以算法届大张旗鼓的所谓“递归影响性能”的说法并不存在，至少在这个问题上有待探讨最后我还想再实现以下多线程解决N皇后的问题因为我发现无论用不用递归，我的N皇后程序跑起来的时候，CPU使用率都在15%以下可能用了JAVA的缘故，虚拟机沙盒有限制，而且是多核的CPU，暂时也没搞明白为什么不能发挥更高的CPU使用率最后

26、我将用多线程再次尝试更高的程序性能，看看能否有突破。接连写了几篇关于8皇后问题的算法研究的博客最终还是觉得回溯算法比较直观，但是效率偏低于是想研究一下JAVA的多线程编程，下面是初次使用多线程编程的计算性能实测首先给一个没有使用多线程编程的例子：12345678910111213141516171819202122publicstaticvoidmain(Stringargs)Datebegin=newDate();longsum=0;inttaskSize=100;for(inti=0;itaskSize;i+)sum+=math(i*);Dateend=newDate();System.o

27、ut.println(用时：+String.valueOf(end.getTime()-begin.getTime()+毫秒，计算结果：+sum);privatestaticlongmath(intn)longsum=0;for(inti=0;in;i+)sum+=i;returnsum;执行效率为24秒，截图如下：下面使用JAVA的ExecutorService，编写带有返回值的多线程代码带有返回值的多线程接口Callable是JAVA1.5之后引入的，完美的解决了多线程编程带有返回值的问题在这之前在JAVA中要使用synchronized 关键字做同步锁，显得相当繁琐，而且极易出错，导致程

28、序死锁现在有了线程池和Callable接口，一切显得相当方便，实现上述计算的代码如下：123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657packagecom.newflypig.eightqueen;importjava.util.ArrayList;importjava.util.Date;importjava.util.List;importjava.util.concurrent.Callable;importjava.util.concurrent.ExecutorService;importjava.util.concurrent.Executors;importjava.util.concurrent.Future;