回溯法Java語言

1、算法思考，初步思路：構(gòu)建二維int或者short型數(shù)組，內(nèi)存中模擬棋盤chessrc=0表示：r行c列沒有皇后，chessrc=1表示：r行c列位置有一個皇后從第一行第一列開始逐行擺放皇后依題意每行只能有一個皇后，遂逐行擺放，每行一個皇后即可擺放后立即調(diào)用一個驗證函數(shù)（傳遞整個棋盤的數(shù)據(jù)），驗證合理性，安全則擺放下一個，不安全則嘗試擺放這一行的下一個位置，直至擺到棋盤邊界當(dāng)這一行所有位置都無法保證皇后安全時，需要回退到上一行，清除上一行的擺放記錄，并且在上一行嘗試擺放下一位置的皇后（回溯算法的核心）當(dāng)擺放到最后一行，并且調(diào)用驗證函數(shù)確定安全后，累積數(shù)自增1，表示有一個解成功算出驗證函數(shù)中，需要

2、掃描當(dāng)前擺放皇后的左上，中上，右上方向是否有其他皇后，有的話存在危險，沒有則表示安全，并不需要考慮當(dāng)前位置棋盤下方的安全性，因為下面的皇后還沒有擺放回溯算法的天然實現(xiàn)是使用編譯器的遞歸函數(shù)，但是其性能令人遺憾下面我們使用上面的思路初步實現(xiàn)8皇后的問題解法，并且將所有解法打印出來，供我們驗證正確性import java.util.Date;/* * 在88格的國際象棋上擺放八個皇后，使其不能互相攻擊， * 即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。 * 下面使用遞歸方法解決 * author * */public class EightQu

3、een private static final short N=8; /使用常量來定義，方便之后解N皇后問題 private static int count=0; /結(jié)果計數(shù)器 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()+ 毫秒，計算結(jié)果：+count); private static void putQueenAtRow(short chess, int row) /* * 遞歸終止判斷：如果row=N，則說明已經(jīng)成功擺放了8個皇后 * 輸出結(jié)果，終止遞歸 */ 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(); /* * 向這一行的每一個位置嘗試排放皇后 * 然后檢測狀態(tài)，如果安全則繼續(xù)執(zhí)行遞歸函數(shù)擺放下一行皇后 */ 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; 輸出結(jié)果：需要打印棋盤時，耗時34毫秒，再看一看不需要打印棋盤時的性能：耗時2毫秒，性能感覺還可以。你以為到這兒就結(jié)束了嗎？高潮還沒開始，下面我們來看看這種算法解決9、10、11.15皇后問題的性能稍微變動一下代碼，循環(huán)打印出各個解的結(jié)果，如下圖所示：當(dāng)我開始嘗試解決16皇后問題時，發(fā)現(xiàn)時間復(fù)雜度已經(jīng)超出我的心里預(yù)期，最終沒讓它繼續(xù)執(zhí)行下去。上網(wǎng)一查N皇后的國際記錄，已經(jīng)有科研單位給出了25皇后的計算結(jié)果，耗時暫未可知我們的程序跑16皇后已經(jīng)無能為

7、力，跑15皇后已經(jīng)捉襟見肘（87秒）中國的一些算法高手能在100秒內(nèi)跑16皇后，可見上面的算法效率只能說一般，辣么，該如何改進呢？我們發(fā)現(xiàn)二維棋盤數(shù)據(jù)在內(nèi)存中浪費嚴(yán)重，全是0和1的組成，同時每次遞歸時使用JAVA的clone函數(shù)克隆一個新的棋盤，消耗進一步擴大，這里面一定有改進的方案。我們考慮將二維數(shù)組使用一維數(shù)組代替，將一維數(shù)組的下標(biāo)數(shù)據(jù)利用起來，模仿棋盤結(jié)構(gòu)，如chessR=C時，表示棋盤上R行C列有一個皇后這樣程序的空間效率會得到迅速提高，同時二維數(shù)據(jù)改變成一維數(shù)據(jù)后的遍歷過程也會大為縮減，時間效率有所提高，下面貼出代碼：import java.util.Date;public clas

8、s EightQueen2 private static final short K=15; /使用常量來定義，方便之后解N皇后問題 private static int count=0; /結(jié)果計數(shù)器 private static short N=0; public static void main(String args) for(N=9;N=K;N+) Date begin =new Date(); /* * 初始化棋盤，使用一維數(shù)組存放棋盤信息 * 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()+ 毫秒，計算結(jié)果：+count); private static void putQueenAtRow(short chess, short row) /* * 遞歸終止判斷：如果row=N，則說明已經(jīng)成功擺放了8個皇后 * 輸出結(jié)果，終止遞歸 */ 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(); /* * 向這一行的每一個位置嘗試排放皇后 * 然后檢測狀態(tài)，如果安全則繼續(xù)執(zhí)行遞歸函數(shù)擺放下一行皇后 */ 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; 運算結(jié)果：可以看到所有結(jié)果的耗時縮短了一倍有余，這無疑是一次算法的進步辣么，還有改進空間嗎？答案必然是肯定的，對于算法，我們越是精益求精，我們的能力就越強大，我們越是淺嘗輒止，我們的進步就越慢。下一篇博客我們來繼續(xù)改進這個問題的算法，摒棄編譯器自帶的遞歸回溯，自己手寫回溯過程，相信效率會進一步提高，最終在可控范圍內(nèi)將16皇后問題解出來。8皇后以及N皇后算法探究，回溯算法的JAVA實現(xiàn)，遞歸方案是使用遞歸方法實現(xiàn)回溯算法的，在第一次使用二維矩陣的情況下，又做了一次改

12、一維的優(yōu)化但是算法效率仍然差強人意，因為使用遞歸函數(shù)的緣故下面提供另一種回溯算法的實現(xiàn)，使用數(shù)據(jù)結(jié)構(gòu)”?！皝砟M，遞歸函數(shù)的手工實現(xiàn)，因為我們知道計算機在處理遞歸時的本質(zhì)就是棧時間復(fù)雜度是一樣的，空間復(fù)雜度因為自定義了class，有所上升經(jīng)過測試其性能甚至低于上篇博客的遞歸實現(xiàn)權(quán)當(dāng)是使用數(shù)據(jù)結(jié)構(gòu)”棧“，解決15皇后的代碼如下：package com.newflypig.eightqueen;import java.util.Date;import java.util.Stack;/* * 使用數(shù)據(jù)結(jié)構(gòu)“?！?，模擬遞歸函數(shù) * 實現(xiàn)非遞歸方案的回溯算法 * 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達(dá)到邊界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()+ 毫秒，計算結(jié)果：+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; /棋盤數(shù)據(jù) public short currentRow=0; /當(dāng)前行 public short currentCol=0; /當(dāng)前列 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; 執(zhí)行結(jié)果：研究了遞歸方法實現(xiàn)回溯，解決N皇后問題，下面我們來探討一下非遞歸方案實驗結(jié)果令人還是有些失望，原來非遞歸方案的性能并不比遞歸方案性能高代碼如下：package com.newflypig.eightqueen;import java.util.Date;/* * 使用循環(huán)控制來實現(xiàn)回溯，解決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：初始狀態(tài)，尚未擺放 -1：開始嘗試擺放 0到N-1：皇后安全的擺放在這一列的哪一行 */ sho

20、rt chess = new shortN; for (short i = 1; i =N) /* * 擺到邊界，清空當(dāng)前行的擺放記錄，標(biāo)志死路 */ 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死路標(biāo)志，告訴循環(huán)什么時候需要回溯，什么時候需要繼續(xù)深搜getRow() 函數(shù)返

22、回當(dāng)前最后擺放皇后的行號，每次擺放皇后和判斷安全性時都要調(diào)用，所以顯得性能偏低下面取消了getRow()函數(shù)，使用全局變量row來表示已經(jīng)擺到那一行的皇后了，用一個小小的變量空間換了一部分時間：package com.newflypig.eightqueen;import java.util.Date;/* * 使用循環(huán)控制來實現(xiàn)回溯，解決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：初始狀態(tài)，尚未擺放 -1：開始嘗試擺放 0到N-1：皇后安全的擺放在這一列的哪一行 */ short chess = new

24、shortN; for (short i = 1; i =N) /* * 擺到邊界，清空當(dāng)前行的擺放記錄，標(biāo)志死路 */ 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; 最終的執(zhí)行效率為：這跟我們第一篇博客的遞歸調(diào)用的效率：還是有些差距，所以算法屆大張旗鼓的所謂“遞歸影響性能”的說法并不存在，至少在這個問題上有待探討最后我還想再實現(xiàn)以下多線程解決N皇后的問題因為我發(fā)現(xiàn)無論用不用遞歸，我的N皇后程序跑起來的時候，CPU使用率都在15%以下可能用了JAVA的緣故，虛擬機沙盒有限制，而且是多核的CPU，暫時也沒搞明白為什么不能發(fā)揮更高的CPU使用率最后

26、我將用多線程再次嘗試更高的程序性能，看看能否有突破。接連寫了幾篇關(guān)于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()+毫秒，計算結(jié)果：+sum);privatestaticlongmath(intn)longsum=0;for(inti=0;in;i+)sum+=i;returnsum;執(zhí)行效率為24秒，截圖如下：下面使用JAVA的ExecutorService，編寫帶有返回值的多線程代碼帶有返回值的多線程接口Callable是JAVA1.5之后引入的，完美的解決了多線程編程帶有返回值的問題在這之前在JAVA中要使用synchronized 關(guān)鍵字做同步鎖，顯得相當(dāng)繁瑣，而且極易出錯，導(dǎo)致程

28、序死鎖現(xiàn)在有了線程池和Callable接口，一切顯得相當(dāng)方便，實現(xiàn)上述計算的代碼如下：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;