回溯法Java語(yǔ)言

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

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

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

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

8、s EightQueen2 private static final short K=15; /使用常量來(lái)定義，方便之后解N皇后問(wèn)題 private static int count=0; /結(jié)果計(jì)數(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列有一個(gè)皇后 */ 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+ 皇后問(wèn)題，用時(shí)： +String.valueOf(end.getTime()-begin.getTime()+ 毫秒，計(jì)算結(jié)果：+count); private static void putQueenAtRow(short chess, short row) /* * 遞歸終止判斷：如果row=N，則說(shuō)明已經(jīng)成功擺放了8個(gè)皇后 * 輸出結(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(); /* * 向這一行的每一個(gè)位置嘗試排放皇后 * 然后檢測(cè)狀態(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; 運(yùn)算結(jié)果：可以看到所有結(jié)果的耗時(shí)縮短了一倍有余，這無(wú)疑是一次算法的進(jìn)步辣么，還有改進(jìn)空間嗎？答案必然是肯定的，對(duì)于算法，我們?cè)绞蔷媲缶覀兊哪芰驮綇?qiáng)大，我們?cè)绞菧\嘗輒止，我們的進(jìn)步就越慢。下一篇博客我們來(lái)繼續(xù)改進(jìn)這個(gè)問(wèn)題的算法，摒棄編譯器自帶的遞歸回溯，自己手寫回溯過(guò)程，相信效率會(huì)進(jìn)一步提高，最終在可控范圍內(nèi)將16皇后問(wèn)題解出來(lái)。8皇后以及N皇后算法探究，回溯算法的JAVA實(shí)現(xiàn)，遞歸方案是使用遞歸方法實(shí)現(xiàn)回溯算法的，在第一次使用二維矩陣的情況下，又做了一次改

12、一維的優(yōu)化但是算法效率仍然差強(qiáng)人意，因?yàn)槭褂眠f歸函數(shù)的緣故下面提供另一種回溯算法的實(shí)現(xiàn)，使用數(shù)據(jù)結(jié)構(gòu)”棧“來(lái)模擬，遞歸函數(shù)的手工實(shí)現(xiàn)，因?yàn)槲覀冎烙?jì)算機(jī)在處理遞歸時(shí)的本質(zhì)就是棧時(shí)間復(fù)雜度是一樣的，空間復(fù)雜度因?yàn)樽远x了class，有所上升經(jīng)過(guò)測(cè)試其性能甚至低于上篇博客的遞歸實(shí)現(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ù) * 實(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尋找第一個(gè)合法解，如果row達(dá)到邊界count+1，否則pus

14、h進(jìn)棧 */ 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+ 皇后問(wèn)題，用時(shí)： +String.valueOf(end.getTime()-begin.g

15、etTime()+ 毫秒，計(jì)算結(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; /是否訪問(wèn)過(guò) 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é)果：研究了遞歸方法實(shí)現(xiàn)回溯，解決N皇后問(wèn)題，下面我們來(lái)探討一下非遞歸方案實(shí)驗(yàn)結(jié)果令人還是有些失望，原來(lái)非遞歸方案的性能并不比遞歸方案性能高代碼如下：package com.newflypig.eightqueen;import java.util.Date;/* * 使用循環(huán)控制來(lái)實(shí)現(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：開(kāi)始嘗試擺放 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)什么時(shí)候需要回溯，什么時(shí)候需要繼續(xù)深搜getRow() 函數(shù)返

22、回當(dāng)前最后擺放皇后的行號(hào)，每次擺放皇后和判斷安全性時(shí)都要調(diào)用，所以顯得性能偏低下面取消了getRow()函數(shù)，使用全局變量row來(lái)表示已經(jīng)擺到那一行的皇后了，用一個(gè)小小的變量空間換了一部分時(shí)間：package com.newflypig.eightqueen;import java.util.Date;/* * 使用循環(huán)控制來(lái)實(shí)現(xiàn)回溯，解決N皇后 * 開(kāi)辟兩個(gè)變量控制行和列，避免不必要的計(jì)算，空間換時(shí)間 * 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：開(kāi)始嘗試擺放 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)用的效率：還是有些差距，所以算法屆大張旗鼓的所謂“遞歸影響性能”的說(shuō)法并不存在，至少在這個(gè)問(wèn)題上有待探討最后我還想再實(shí)現(xiàn)以下多線程解決N皇后的問(wèn)題因?yàn)槲野l(fā)現(xiàn)無(wú)論用不用遞歸，我的N皇后程序跑起來(lái)的時(shí)候，CPU使用率都在15%以下可能用了JAVA的緣故，虛擬機(jī)沙盒有限制，而且是多核的CPU，暫時(shí)也沒(méi)搞明白為什么不能發(fā)揮更高的CPU使用率最后

26、我將用多線程再次嘗試更高的程序性能，看看能否有突破。接連寫了幾篇關(guān)于8皇后問(wèn)題的算法研究的博客最終還是覺(jué)得回溯算法比較直觀，但是效率偏低于是想研究一下JAVA的多線程編程，下面是初次使用多線程編程的計(jì)算性能實(shí)測(cè)首先給一個(gè)沒(méi)有使用多線程編程的例子：12345678910111213141516171819202122publicstaticvoidmain(Stringargs)Datebegin=newDate();longsum=0;inttaskSize=100;for(inti=0;itaskSize;i+)sum+=math(i*);Dateend=newDate();System.o

27、ut.println(用時(shí)：+String.valueOf(end.getTime()-begin.getTime()+毫秒，計(jì)算結(jié)果：+sum);privatestaticlongmath(intn)longsum=0;for(inti=0;in;i+)sum+=i;returnsum;執(zhí)行效率為24秒，截圖如下：下面使用JAVA的ExecutorService，編寫帶有返回值的多線程代碼帶有返回值的多線程接口Callable是JAVA1.5之后引入的，完美的解決了多線程編程帶有返回值的問(wèn)題在這之前在JAVA中要使用synchronized 關(guān)鍵字做同步鎖，顯得相當(dāng)繁瑣，而且極易出錯(cuò)，導(dǎo)致程

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