回溯法解決n皇后問(wèn)題

1、回溯法解決n皇后問(wèn)題回溯法解決n皇后問(wèn)題摘要：回溯法是一種選優(yōu)搜索法，也稱(chēng)為試探法，按照深度優(yōu)先搜索的策略，從根結(jié)點(diǎn)出發(fā)深度探索解空間樹(shù)?；厮菟惴ń鉀Q問(wèn)題的一般步驟。八皇后問(wèn)題以及8-皇后問(wèn)題的推廣n-皇后問(wèn)題，等于要求N個(gè)皇后中的任意兩個(gè)不能被放在同一行或同一列或同一斜線上。關(guān)鍵詞：回溯法、八皇后、顯約束、顯約束、樹(shù)結(jié)構(gòu)一回溯法回溯法是一種選優(yōu)搜索法，也稱(chēng)為試探法，它并不考慮問(wèn)題規(guī)模的大小，而是從問(wèn)題的最明顯的最小規(guī)模開(kāi)始逐步求解出可能的答案，并以此慢慢地?cái)U(kuò)大問(wèn)題規(guī)模，迭代地逼近最終問(wèn)題的解。這種迭代類(lèi)似于窮舉并且是試探性的，因?yàn)楫?dāng)目前的可能答案被測(cè)試出不可能可以獲得最終解時(shí)，則撤銷(xiāo)當(dāng)前的這

2、一步求解過(guò)程，回溯到上一步尋找其他求解路徑。通過(guò)對(duì)問(wèn)題的歸納分析，找出求解問(wèn)題的一個(gè)線索，沿著這一線索往前試探，若試探成功，即得到解；若試探失敗，就逐步往回退，換其他路線再往前試探。因此，回溯法可以形象地概括為“向前走，碰壁回頭”。有許多問(wèn)題，當(dāng)需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時(shí)，往往使用回溯法。二回溯的一般方法 下面簡(jiǎn)要闡述回溯的一般方法。 回溯求解的問(wèn)題P，通常要能表達(dá)為：對(duì)于已知的由n元組(x1,x2,xn)組成的一個(gè)狀態(tài)空間E=(x1,x2,xn)|xisi,i=1,2,n，給定關(guān)于n元組中的一個(gè)分量的一個(gè)約束集D，要求E中滿足D的全部約

3、束條件的所有n元組。其中si是分量xi的定義域，且|si|有限，i=1,2,n。稱(chēng)E中滿足D的全部約束條件的任一n元組為問(wèn)題P的一個(gè)解。解問(wèn)題P的最樸素的方法就是窮舉法，上面已經(jīng)作了介紹，即對(duì)E中的所有n元組逐一地檢驗(yàn)其是否滿足D的全部約束，若滿足，則為問(wèn)題P的一個(gè)解。顯然，其計(jì)算量是相當(dāng)大的。 對(duì)于許多問(wèn)題，所給定的約束集D具有完備性，即i元組(x1,x2,xi)滿足D中僅涉及到x1,x2,xi的所有約束，意味著j(j<i)元組(x1,x2,xj)一定也滿足D中僅涉及到x1,x2,xj的所有約束，i=1,2,n。換句話說(shuō)，只要存在0jn-1，使得(x1,x2,xj)違反D中僅

4、涉及到x1,x2,xj的約束之一，則以(x1,x2,xj)為前綴的任何n元組(x1,x2,xj,xj+1,xn)也一定違反D中僅涉及到x1,x2,xj的一個(gè)約束，nij。因此，對(duì)于約束集D具有完備性的問(wèn)題P，一旦檢測(cè)斷定某個(gè)j元組(x1,x2,xj)違反D中僅涉及x1,x2,xj的一個(gè)約束，就可以肯定，以(x1,x2,xj)為前綴的任何n元組(x1,x2,xj,xj+1,xn)都不會(huì)是問(wèn)題P的解，因而就不必去搜索它們，即省略了對(duì)部分元素(xj+1,xn)的操作與測(cè)試?；厮莘ㄕ轻槍?duì)這類(lèi)問(wèn)題。三基本思想在包含問(wèn)題的所有解的解空間樹(shù)中，按照深度優(yōu)先搜索的策略，從根結(jié)點(diǎn)出發(fā)深度探索解空間樹(shù)。當(dāng)探索到

5、某一結(jié)點(diǎn)時(shí)，要先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解，如果包含，就從該結(jié)點(diǎn)出發(fā)繼續(xù)探索下去，如果該結(jié)點(diǎn)不包含問(wèn)題的解，則逐層向其祖先結(jié)點(diǎn)回溯。 若用回溯法求問(wèn)題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有可行的子樹(shù)都要已被搜索遍才結(jié)束。 而若使用回溯法求任一個(gè)解時(shí)，只要搜索到問(wèn)題的一個(gè)解就可以結(jié)束?；厮菟惴ń鉀Q問(wèn)題的一般步驟：1、定義一個(gè)解空間，它包含問(wèn)題的解。2、利用適于搜索的方法組織解空間。3、利用深度優(yōu)先法搜索解空間。4、利用限界函數(shù)避免移動(dòng)到不可能產(chǎn)生解的子空間。問(wèn)題的解空間通常是在搜索問(wèn)題的解的過(guò)程中動(dòng)態(tài)產(chǎn)生的，這是回溯算法的一個(gè)重要特性。問(wèn)題的解向量： 回溯法希望一個(gè)問(wèn)題的解能夠表示成一個(gè)n元式(

6、x1,x2,xn)的形式。顯約束： 對(duì)分量xi的取值限定。隱約束： 為滿足問(wèn)題的解而對(duì)不同分量之間施加的約束。解空間： 對(duì)于問(wèn)題的一個(gè)實(shí)例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實(shí)例的一個(gè)解空間。確定了解空間的組織結(jié)構(gòu)后，回溯法就從開(kāi)始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以深度優(yōu)先的方式搜索整個(gè)解空間。這個(gè)開(kāi)始結(jié)點(diǎn)就成為一個(gè)活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向移至一個(gè)新結(jié)點(diǎn)。這個(gè)新結(jié)點(diǎn)就成為一個(gè)新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動(dòng)，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)（回溯）至最近的一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)

7、點(diǎn)?；厮莘匆赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒(méi)有活結(jié)點(diǎn)時(shí)為止?；厮莘ㄓ小巴ㄓ媒忸}法”之稱(chēng)，是一種比窮舉“聰明”的搜索技術(shù)，在搜索過(guò)程中動(dòng)態(tài)地產(chǎn)生問(wèn)題的解空間，系統(tǒng)地搜索問(wèn)題的所有解。當(dāng)搜索到解空間樹(shù)的任一結(jié)點(diǎn)時(shí)，判斷該結(jié)點(diǎn)是否包含問(wèn)題的解。如果該結(jié)點(diǎn)肯定不包含，則“見(jiàn)壁回頭”，跳過(guò)以該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回溯，可大大縮減無(wú)效操作，提高搜索效率。因此，結(jié)合具體案例的實(shí)際設(shè)計(jì)合適的回溯點(diǎn)是應(yīng)用回溯法的關(guān)鍵所在。 值得注意的是，遞歸具有回溯的功能，很多問(wèn)題應(yīng)用遞歸回溯可探索出問(wèn)題的所有解。例如，在求解橋本分?jǐn)?shù)式中，既用了回溯法求解，也應(yīng)用

8、了遞歸求解，請(qǐng)認(rèn)真比較這二者之間的關(guān)聯(lián)。盡管遞歸的效率不高，但遞歸設(shè)計(jì)的簡(jiǎn)明是一般回溯設(shè)計(jì)所不及的。 回溯法的時(shí)間復(fù)雜度因案例的具體實(shí)際而異。一般來(lái)說(shuō)，其搜索效率要高于窮舉。四八皇后問(wèn)題八皇后問(wèn)題是一個(gè)古老而著名的問(wèn)題。該問(wèn)題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850提出；在8×8格的國(guó)際象棋上擺放八皇后，使得每一個(gè)皇后既攻擊不到另外七個(gè)皇后，也不被另外七個(gè)皇后所攻擊按照國(guó)際象棋的規(guī)則，一個(gè)皇后可以攻擊與之處在同一行或同一列或同一斜線上的其他任何棋子因此，八皇后問(wèn)題等于要求八個(gè)皇后中的任意兩個(gè)不能被放在同一行或同一列或同一斜線上?？梢詮木仃嚨奶攸c(diǎn)上找到規(guī)律，如果在同一行，則行號(hào)相同

9、；如果在同一列上，則列號(hào)相同；如果同在“/”斜線上的行列值之和相同；如果在對(duì)角線上，則行列號(hào)之和或之差相等，逐個(gè)紀(jì)錄符合題意的情況,最終得出解。分析：由于8*8的棋盤(pán)太大，所以用4*4來(lái)演示，右圖是一組解坐標(biāo)表示：（1，3）（2，1）（3，4）（4，2）當(dāng)n=4時(shí)的一種可能的樹(shù)結(jié)構(gòu)。像這樣的一棵樹(shù)稱(chēng)之為排列樹(shù)。樹(shù)的邊由xi的可能值所標(biāo)記。由1級(jí)到2級(jí)結(jié)點(diǎn)的邊給出x1的值。因此，最左子樹(shù)包含著x1=1的所有解，而該子樹(shù)的最左子樹(shù)又包含著x1=1且x2=2的所有解，等等。由i級(jí)到i1級(jí)的邊用xi的值標(biāo)記。解空間則是由從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的所有路徑所定義的。在下圖的這棵樹(shù)中，有4!=24個(gè)葉結(jié)點(diǎn)。圖2

10、4-皇后問(wèn)題解空間的樹(shù)結(jié)構(gòu)，結(jié)點(diǎn)按深度優(yōu)先檢索編號(hào)考慮用回溯法來(lái)處理n-皇后問(wèn)題。可用一些顯而易見(jiàn)的標(biāo)準(zhǔn)來(lái)作為限界函數(shù)，即如果(x1,x2,xi)是到當(dāng)前E-結(jié)點(diǎn)的路徑，那么具有父-子標(biāo)記xi+1的所有孩子結(jié)點(diǎn)是一些這樣的結(jié)點(diǎn)，它們使得(x1,x2,xi+1)表示沒(méi)有兩個(gè)皇后正在互相攻擊的一種棋盤(pán)格局。開(kāi)始時(shí)，把根結(jié)點(diǎn)作為唯一的活結(jié)點(diǎn)，該根結(jié)點(diǎn)就成為E-結(jié)點(diǎn)且路徑為()。接著生成一個(gè)孩子結(jié)點(diǎn)，如果假定按自然數(shù)遞增的次序來(lái)生成孩子結(jié)點(diǎn)，那么，如圖所示的結(jié)點(diǎn)2被生成，其路徑為(1)。這相當(dāng)于把皇后1放在第1列上。結(jié)點(diǎn)2變成E-結(jié)點(diǎn)，生成結(jié)點(diǎn)3，但立即被殺死。下一個(gè)生成的結(jié)點(diǎn)是8且路徑變成(l,3)

11、。結(jié)點(diǎn) 8成為 E-結(jié)點(diǎn)，由于它的所有孩子表示的是一些不可能導(dǎo)致答案結(jié)點(diǎn)的棋盤(pán)格局，因此結(jié)點(diǎn)8也被殺死。于是回溯到結(jié)點(diǎn)2并生成它的另一個(gè)孩子結(jié)點(diǎn)13?，F(xiàn)在的路徑是(l,4)。思路： 有序地從第 1 行的第 1 列開(kāi)始，嘗試放上一個(gè)皇后，然后再?lài)L試第 2 行的第幾列能夠放上一個(gè)皇后，如果第 2 行也放置成功，那么就繼續(xù)放置第 3 行，如果此時(shí)第 3 行沒(méi)有一行可以放置一個(gè)皇后，說(shuō)明目前為止的嘗試是無(wú)效的（即不可能得到最終解），那么此時(shí)就應(yīng)該回溯到上一步（即第 2 步），將上一步（第 2 步）所放置的皇后的位置再重新取走放在另一個(gè)符合要求的地方如此嘗試性地遍歷加上回溯，就可以慢慢地逼近最

12、終解了。下圖所示為應(yīng)用回溯的實(shí)施過(guò)程，其中方格中的*表示試圖在該方格放置一個(gè)皇后,但由于受前面已放置的皇后的攻擊而放棄的位置。圖 3 四皇后問(wèn)題的一個(gè)回溯解的例子1(a)1(b)*21(c)2*1(d)2*31(e)23*1(f)1(g)*21(h)23*4圖3生動(dòng)地顯示了應(yīng)用回溯算法求一個(gè)解所經(jīng)過(guò)的步驟。圖中的點(diǎn)表示曾試圖放置一個(gè)皇后但由于受到另-皇后的攻擊而放棄了的位置。在(a)中，第一個(gè)皇后被放在第1列上。在(b)中，第二個(gè)皇后被放在第1，第2列而最后放置在第3列上。在(c)中，算法把四列都試驗(yàn)了，但沒(méi)法將下一個(gè)皇后放在一個(gè)方格中，此時(shí)就進(jìn)行回溯。在(d)中，第二個(gè)皇后被移到下一個(gè)可能的

13、列，即第4列，然后將第三個(gè)皇后放在第2列上。(e)、(f)、(g)和(h)則顯示了用這個(gè)算法一直找到一個(gè)解為止所進(jìn)行的其余步驟。用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹(shù)；顯然，每一行可以而且必須放一個(gè)皇后，所以n皇后問(wèn)題的解可以用一個(gè)n元向量X=（x1,x2,.xn）表示，其中，1 i n且1 xi n，即第n個(gè)皇后放在第i行第xi列上。由于兩個(gè)皇后不能放在同一列上，所以，解向量X必須滿足的約束條件為:xi xj;若兩個(gè)皇后的擺放位置分別是（i,xi）和（j,xj），在棋盤(pán)上斜率為-1的斜線上，滿足條件：i-j=xi-xj;在棋盤(pán)上斜率為1的斜線上，滿足條件：i+j=xi+xj;綜合兩種情況

14、，由于兩個(gè)皇后不能位于同一斜線上，所以，解向量X必須滿足的約束條件為:|i-xi| |j-xj|用限界函數(shù)剪去得不到最優(yōu)解的子樹(shù)。i < n + 1j < n + 1五數(shù)據(jù)結(jié)構(gòu)Int column col = row 表示第 col 列的第 row 行放置一個(gè)皇后；Boolean rowExistsi = true 表示第 i 行有皇后；Boolean ai = true 表示右高左低的第 i 條斜線有皇后（按   順序從1 2*N -1 依次編號(hào)）；Boolean bi = true

15、0;表示左高右低的第 i 條斜線有皇后（按   順序從1 2*N -1 依次編號(hào)）。六程序調(diào)試當(dāng)n=4時(shí)：當(dāng)n=6時(shí)：七總結(jié)從八皇后問(wèn)題設(shè)計(jì)以及分析中，本人從中理解到了數(shù)據(jù)結(jié)構(gòu)對(duì)于計(jì)算機(jī)軟件設(shè)計(jì)的重要性，它的使用，可以改變一個(gè)軟件的運(yùn)行周期，也可以將軟件的思路從繁化簡(jiǎn)，并且都能夠通過(guò)數(shù)據(jù)結(jié)構(gòu)的相關(guān)引導(dǎo)，將本身以前編程思想進(jìn)行擴(kuò)充，發(fā)展；這也是在這次課程設(shè)計(jì)中我所掌握得到的。 參考文獻(xiàn) 1  蘇仕華,數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì).-北京:機(jī)械工業(yè)出版社,2005.5 2  于永彥,趙建洋.課程設(shè)計(jì)指導(dǎo)書(shū).淮安

16、：江蘇淮陰工學(xué)院 計(jì)算機(jī)工程系,2006 3 王峰.Java多媒體程序設(shè)計(jì).清華大學(xué)出版社.19994 耿祥義.Java課程設(shè)計(jì).清華大學(xué)出版社.2003代碼：public class nhuanghou private int queensNum=4 ; / queensNum代表皇后個(gè)數(shù)private int number = 1; / rowExistsi = true 表示第 i 行有皇后 private boolean rowExists = new booleanqueensNum + 1; / columni = j 表示第 i 列的第 j 行放置一個(gè)皇后 p

17、rivate int queens = new intqueensNum + 1; / ai = true 表示右高左低的第 i 條斜線有皇后 private boolean a = new booleanqueensNum * 2; / bi = true 表示左高右低的第 i 條斜線有皇后 private boolean b = new booleanqueensNum * 2; / 初始化變量 private void init() for (int i = 0; i < queensNum + 1; i+) rowExistsi = false; for(int i = 0; i

18、 < queensNum * 2; i+) ai = bi = false; / 判斷該位置是否已經(jīng)存在一個(gè)皇后,存在則返回 true private boolean isExists(int row, int col) return (rowExistsrow | arow + col - 1 | bqueensNum + col - row); / 主方法：測(cè)試放置皇后 public void testing(int column) / 遍歷每一行 for (int row = 1; row < queensNum + 1; row+) / 如果第 row 行第 column 列可以放置皇后 if (!isExists(row, column) / 設(shè)置第 row 行第 column 列有皇后 queenscolumn = row; /