回溯法Java语言

算法思考，初步思路：构建二维int或者short型数组，内存中模拟棋盘chess[r][c]=0表示：r行c列没有皇后，chess[r][c]=1表示：r行c列位置有一个皇后从第一行第一列开始逐行摆放皇后依题意每行只能有一个皇后，遂逐行摆放，每行一个皇后即可摆放后立即调用一个验证函数（传递整个棋盘的数据），验证合理性，安全则摆放下一个，不安全则尝试摆放这一行的下一个位置，直至摆到棋盘边界当这一行所有位置都无法保证皇后安全时，需要回退到上一行，清除上一行的摆放记录，并且在上一行尝试摆放下一位置的皇后（回溯算法的核心）当摆放到最后一行，并且调用验证函数确定安全后，累积数自增1，表示有一个解成功算出验证函数中，需要扫描当前摆放皇后的左上，中上，右上方向是否有其他皇后，有的话存在危险，没有则表示安全，并不需要考虑当前位置棋盘下方的安全性，因为下面的皇后还没有摆放回溯算法的天然实现是使用编译器的递归函数，但是其性能令人遗憾下面我们使用上面的思路初步实现8皇后的问题解法，并且将所有解法打印出来，供我们验证正确性importjava.util.Date;/***在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，*即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。*下面使用递归方法解决*@[e-mail]**/publicclassEightQueen{privatestaticfinalshortN=8;//使用常量来定义，方便之后解N皇后问题privatestaticintcount=0;//结果计数器publicstaticvoidmain(String[]args){Datebegin=newDate();//初始化棋盘，全部置0shortchess[][]=newshort[N][N];for(inti=0;iN;i++){for(intj=0;jN;j++){chess[i][j]=0;}}putQueenAtRow(chess,0);Dateend=newDate();System.out.println(解决+N+皇后问题，用时：+String.valueOf(end.getTime()-begin.getTime())+毫秒，计算结果：+count);}privatestaticvoidputQueenAtRow(short[][]chess,introw){/***递归终止判断：如果row==N，则说明已经成功摆放了8个皇后*输出结果，终止递归*/if(row==N){count++;System.out.println(第+count+种解：);for(inti=0;iN;i++){for(intj=0;jN;j++){System.out.print(chess[i][j]+);}System.out.println();}return;}short[][]chessTemp=chess.clone();/***向这一行的每一个位置尝试排放皇后*然后检测状态，如果安全则继续执行递归函数摆放下一行皇后*/for(inti=0;iN;i++){//摆放这一行的皇后，之前要清掉所有这一行摆放的记录，防止污染棋盘for(intj=0;jN;j++)chessTemp[row][j]=0;chessTemp[row][i]=1;if(isSafety(chessTemp,row,i)){putQueenAtRow(chessTemp,row+1);}}}privatestaticbooleanisSafety(short[][]chess,introw,intcol){//判断中上、左上、右上是否安全intstep=1;while(row-step=0){if(chess[row-step][col]==1)//中上returnfalse;if(col-step=0&&chess[row-step][col-step]==1)//左上returnfalse;if(col+stepN&&chess[row-step][col+step]==1)//右上returnfalse;step++;}returntrue;}}输出结果：需要打印棋盘时，耗时34毫秒，再看一看不需要打印棋盘时的性能：耗时2毫秒，性能感觉还可以。你以为到这儿就结束了吗？高潮还没开始，下面我们来看看这种算法解决9、10、11...15皇后问题的性能稍微变动一下代码，循环打印出各个解的结果，如下图所示：当我开始尝试解决16皇后问题时，发现时间复杂度已经超出我的心里预期，最终没让它继续执行下去。上网一查N皇后的国际记录，已经有科研单位给出了25皇后的计算结果，耗时暂未可知我们的程序跑16皇后已经无能为力，跑15皇后已经捉襟见肘（87秒）中国的一些算法高手能在100秒内跑16皇后，可见上面的算法效率只能说一般，辣么，该如何改进呢？我们发现二维棋盘数据在内存中浪费严重，全是0和1的组成，同时每次递归时使用JAVA的clone函数克隆一个新的棋盘，消耗进一步扩大，这里面一定有改进的方案。我们考虑将二维数组使用一维数组代替，将一维数组的下标数据利用起来，模仿棋盘结构，如chess[R]=C时，表示棋盘上R行C列有一个皇后这样程序的空间效率会得到迅速提高，同时二维数据改变成一维数据后的遍历过程也会大为缩减，时间效率有所提高，下面贴出代码：importjava.util.Date;publicclassEightQueen2{privatestaticfinalshortK=15;//使用常量来定义，方便之后解N皇后问题privatestaticintcount=0;//结果计数器privatestaticshortN=0;publicstaticvoidmain(String[]args){for(N=9;N=K;N++){Datebegin=newDate();/***初始化棋盘，使用一维数组存放棋盘信息*chess[n]=X:表示第n行X列有一个皇后*/shortchess[]=newshort[N];for(inti=0;iN;i++){chess[i]=0;}putQueenAtRow(chess,(short)0);Dateend=newDate();System.out.println(解决+N+皇后问题，用时：+String.valueOf(end.getTime()-begin.getTime())+毫秒，计算结果：+count);}}privatestaticvoidputQueenAtRow(short[]chess,shortrow){/***递归终止判断：如果row==N，则说明已经成功摆放了8个皇后*输出结果，终止递归*/if(row==N){count++;//System.out.println(第+count+种解：);//for(inti=0;iN;i++){//for(intj=0;jN;j++){//System.out.print(chess[i][j]+);//}//System.out.println();//}return;}short[]chessTemp=chess.clone();/***向这一行的每一个位置尝试排放皇后*然后检测状态，如果安全则继续执行递归函数摆放下一行皇后*/for(shorti=0;iN;i++){//摆放这一行的皇后chessTemp[row]=i;if(isSafety(chessTemp,row,i)){putQueenAtRow(chessTemp,(short)(row+1));}}}privatestaticbooleanisSafety(short[]chess,shortrow,shortcol){//判断中上、左上、右上是否安全shortstep=1;for(shorti=(short)(row-1);i=0;i--){if(chess[i]==col)//中上returnfalse;if(chess[i]==col-step)//左上returnfalse;if(chess[i]==col+step)//右上returnfalse;step++;}returntrue;}}运算结果：可以看到所有结果的耗时缩短了一倍有余，这无疑是一次算法的进步辣么，还有改进空间吗？答案必然是肯定的，对于算法，我们越是精益求精，我们的能力就越强大，我们越是浅尝辄止，我们的进步就越慢。下一篇博客我们来继续改进这个问题的算法，摒弃编译器自带的递归回溯，自己手写回溯过程，相信效率会进一步提高，最终在可控范围内将16皇后问题解出来。《8皇后以及N皇后算法探究，回溯算法的JAVA实现，递归方案》是使用递归方法实现回溯算法的，在第一次使用二维矩阵的情况下，又做了一次改一维的优化但是算法效率仍然差强人意，因为使用递归函数的缘故下面提供另一种回溯算法的实现，使用数据结构”栈“来模拟，递归函数的手工实现，因为我们知道计算机在处理递归时的本质就是栈时间复杂度是一样的，空间复杂度因为自定义了class，有所上升经过测试其性能甚至低于上篇博客的递归实现权当是使用数据结构”栈“，解决15皇后的代码如下：packagecom.newflypig.eightqueen;importjava.util.Date;importjava.util.Stack;/***使用数据结构“栈”，模拟递归函数*实现非递归方案的回溯算法*@[e-mail]*Time:2015年12月31日下午6:13:05*/publicclassEightQueen3{privatestaticfinalshortN=15;publicstaticvoidmain(String[]args){Datebegin=newDate();longcount=0;/***初始化栈和棋盘，并向栈中压入第一张初始化的棋盘*/StackChessstack=newStackChess();short[]chessData=newshort[N];for(shorti=1;iN;i++){chessData[i]=-1;//初始化棋盘，所有行没有皇后，赋值-1}ChessinitChess=newChess(chessData);stack.push(initChess);//对栈进行操作，直到栈为空，程序计算完毕EMPTY:while(!stack.isEmpty()){/***访问出口处的棋盘，判断是否访问过*如果没有访问过，访问标志改为true，构建下层数据*如果访问过，尝试对此棋盘col++寻找此行的合法解*寻找直至溢出边界，pop掉，在寻找过程中如果发现合法解：*修改col，访问量状态恢复到false，跳出isEmpty循环去访问他*/Chesschess=stack.peek();if(chess.visited){while(chess.moveCol()){if(isSafety(chess)){chess.visited=false;continueEMPTY;}}stack.pop();}else{chess.visited=true;/***构建下层数据：*构建栈顶元素的克隆，访问状态设为false*row下移一层，如果溢出边界丢弃，这种情况不应该发生*col:0-N寻找第一个合法解，如果row达到边界count+1，否则push进栈*/ChesschessTemp=chess.clone();if(chessTemp.moveRow()){while(chessTemp.moveCol()){if(isSafety(chessTemp)){if(chessTemp.currentRow==N-1){count++;continue;}else{stack.push(chessTemp);continueEMPTY;}}}}}}