N皇后問(wèn)題.txt

1、8皇后問(wèn)題和N皇后問(wèn)題今天來(lái)學(xué)習(xí)一個(gè)非常著名的算法題：8皇后問(wèn)題和由他推廣得到的N皇后問(wèn)題。題目來(lái)源于國(guó)際象棋的玩法，因?yàn)榛屎笏诘奈恢每梢钥v向、橫向、兩個(gè)斜向四個(gè)方向的“捕捉”，所以8皇后問(wèn)題就是要求如何布置8個(gè)皇后在88的棋盤(pán)上而使他們互相無(wú)法“捕捉”。也就是說(shuō)不存在兩個(gè)皇后同行或同列，或在同一斜線上。而N皇后問(wèn)題就是如何布置N個(gè)皇后在NN棋盤(pán)里使不存在兩個(gè)皇后在同行同列和同一斜線上。因?yàn)?皇后問(wèn)題可以歸為N皇后問(wèn)題，所以下面按照N

2、皇后問(wèn)題來(lái)進(jìn)行討論。解決N皇后問(wèn)題的最好最著名的算法就是回溯法。在算法設(shè)計(jì)的基本方法中，回溯法是最一般的方法之一。在那些涉及到尋找一組解的問(wèn)題或者求滿足某些約束條件的最優(yōu)解的問(wèn)題中，有許多可以用回溯法來(lái)求解?；厮莘ㄊ且粋€(gè)既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問(wèn)題的所有解的解空間樹(shù)中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索至解空間樹(shù)的任一結(jié)點(diǎn)時(shí)，總是先判斷該結(jié)點(diǎn)是否肯定不包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)以該結(jié)

3、點(diǎn)為根的子樹(shù)的系統(tǒng)搜索，逐層向其祖先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。回溯法在用來(lái)求問(wèn)題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有子樹(shù)都已被搜索遍才結(jié)束。而回溯法在用來(lái)求問(wèn)題的任一解時(shí)，只要搜索到問(wèn)題的一個(gè)解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問(wèn)題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問(wèn)題?；厮莘ǖ幕舅枷耄捍_定了解空間的組織結(jié)構(gòu)后，回溯法就從開(kāi)始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以深度優(yōu)先的方式搜索整個(gè)解空間。這

4、個(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)。換句話說(shuō)，這個(gè)結(jié)點(diǎn)不再是一個(gè)活結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)（回溯）至最近的一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)?；厮莘匆赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒(méi)有活結(jié)點(diǎn)時(shí)為止。運(yùn)用

5、回溯法解題通常包含以下三個(gè)步驟：（1）針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；（2）確定易于搜索的解空間結(jié)構(gòu)；（3）以深度優(yōu)先的方式搜索解空間，并且在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索；一般回溯法可用遞歸來(lái)實(shí)現(xiàn)，下面是從網(wǎng)上找來(lái)的一個(gè)非常典型的遞歸程序結(jié)構(gòu)。proceduretry(i:integer)varbeginifinthen輸出結(jié)果elsefj:=下界to上界dobeginx[i]:=h[j]if可行滿足限界函數(shù)和約束條件thenbeg

6、in置值；try(i1)endendend說(shuō)明：i是遞歸深度；n是深度控制，即解空間樹(shù)的的高度；可行性判斷有兩方面的內(nèi)容：不滿約束條件則剪去相應(yīng)子樹(shù)；若限界函數(shù)越界，也剪去相應(yīng)子樹(shù)；兩者均滿足則進(jìn)入下一層，直到最后的葉子輸出結(jié)果?；氐絅皇后問(wèn)題的解決來(lái)，看看如何用回溯法解。首先找出解空間：給棋盤(pán)的行和列都編上1到N的號(hào)碼，皇后也給編上1到N的號(hào)碼。由于一個(gè)皇后應(yīng)在不同的行上，為不失一般性，可以假定第i個(gè)皇后將放在第i行上的某列。因此N皇

7、后問(wèn)題的解空間可以用一個(gè)N元組（X1，X2，.....Xn）來(lái)表示，其中Xi是放置皇后i所在的列號(hào)。這意味著所有的解都是N元組（1，2，3，.......，N）的置換。解空間大小為N！。其次我們看約束條件：因?yàn)榻饪臻g已經(jīng)給我們排除了不在同一行（因?yàn)槊總€(gè)皇后分別已經(jīng)對(duì)應(yīng)不同的行號(hào)）的約束條件。我們要判斷的是不在同一列和不在同一斜線的約束。因?yàn)閄i表示皇后所在的列號(hào)，所以如果存在X（k）=X（i）那么肯定存在第k個(gè)皇后和第i個(gè)皇后同列。所以