1、1八皇后問題八皇后問題2n1八皇后問題背景八皇后問題背景n2盲目的枚舉算法盲目的枚舉算法n3加約束的枚舉算法加約束的枚舉算法n4回溯法及基本思想回溯法及基本思想n5 回溯法應(yīng)用回溯法應(yīng)用n6八皇后問題的遞歸回溯算法八皇后問題的遞歸回溯算法n7八皇后問題的非遞歸回溯算法八皇后問題的非遞歸回溯算法 3【背景背景】 八皇后問題是一個(gè)以國(guó)際象棋為背八皇后問題是一個(gè)以國(guó)際象棋為背景的問題：景的問題： 如何能夠在如何能夠在 88 的國(guó)際象棋棋盤上的國(guó)際象棋棋盤上放置八個(gè)皇后，使得任何一個(gè)皇后都放置八個(gè)皇后，使得任何一個(gè)皇后都無(wú)法直接吃掉其他的皇后？為了達(dá)到無(wú)法直接吃掉其他的皇后？為了達(dá)到此目的，任兩個(gè)皇后

2、都不能處于同一此目的，任兩個(gè)皇后都不能處于同一條橫行、縱行或斜線上。條橫行、縱行或斜線上。4八皇后問題八皇后問題q要在要在8*8的國(guó)際象棋棋盤中放的國(guó)際象棋棋盤中放8個(gè)皇后，使任意兩個(gè)皇個(gè)皇后，使任意兩個(gè)皇后都不能互相吃掉。后都不能互相吃掉。規(guī)則：皇后能吃掉同一行、同一規(guī)則：皇后能吃掉同一行、同一列、同一對(duì)角線的任意棋子。求所有的解。列、同一對(duì)角線的任意棋子。求所有的解。q八皇后的兩組解八皇后的兩組解5【問題分析問題分析】n設(shè)八個(gè)皇后為設(shè)八個(gè)皇后為xi，分別在第，分別在第i行行(i=1，2，3，4，8)；n問題的解狀態(tài)問題的解狀態(tài)：可以用：可以用(1,x1)，(2,x2)，(8,x8)表示表示

3、8個(gè)個(gè)皇后的位置；皇后的位置；q由于行號(hào)固定，可簡(jiǎn)單記為：由于行號(hào)固定，可簡(jiǎn)單記為：(x1,x2,x3,x4,x5,x6,x7,x8)；n問題的解空間問題的解空間：(x1,x2,x3,x4,x5,x6,x7,x8)，1xi8(i=1，2，3，4，8)，共，共88個(gè)狀態(tài)；個(gè)狀態(tài)；n約束條件約束條件：八個(gè)：八個(gè)(1,x1),(2,x2) ,(3,x3),(4,x4) ,(5,x5), (6,x6) , (7,x7), (8,x8)不在同一行、同一列和同一對(duì)角線上。不在同一行、同一列和同一對(duì)角線上。n原問題即：在解空間中原問題即：在解空間中尋找符合約束條件尋找符合約束條件的解狀態(tài)。的解狀態(tài)。n按什么

4、順序去搜？按什么順序去搜？q目標(biāo)是沒有漏網(wǎng)之魚，盡量速度快。目標(biāo)是沒有漏網(wǎng)之魚，盡量速度快。6枚舉得有個(gè)順序，否則枚舉得有個(gè)順序，否則輕則有漏的、重復(fù)的；輕則有漏的、重復(fù)的；重則無(wú)法循環(huán)表示。重則無(wú)法循環(huán)表示。2 【問題設(shè)計(jì)問題設(shè)計(jì)】盲目的枚舉算法盲目的枚舉算法na 盲目的枚舉算法盲目的枚舉算法q通過通過8重循環(huán)模擬搜索空間中的重循環(huán)模擬搜索空間中的88個(gè)狀態(tài)；個(gè)狀態(tài)；q按按枚舉思想枚舉思想，以以DFS的方式的方式，從第，從第1個(gè)皇后在第個(gè)皇后在第1列開始列開始搜索，枚舉出所有的搜索，枚舉出所有的“解狀態(tài)解狀態(tài)”：n從中找出滿足約束條件的從中找出滿足約束條件的“答案狀態(tài)答案狀態(tài)”。n約束條件？

5、約束條件？1.按什么順序去查找所有的解按什么順序去查找所有的解 a.盲目的枚舉算法盲目的枚舉算法 void main() int x100; for (x1=1;x1=10;x1+) for (x2=1;x2=10;x2+) for (x3=1;x3=10;x3+) for (x4=1;x4=10;x4+) for (x5=1;x5=10;x5+) for (x6=1;x6=10;x6+) for (x7=1;x7=10;x7+) for (x8=1;x8=10;x8+) if (check(x)=0) printf(x); 該如何解決沖突的問題呢？該如何解決沖突的問題呢？1.行；我們是按照行

6、枚舉的，保證了一行一個(gè)皇后；行；我們是按照行枚舉的，保證了一行一個(gè)皇后；2.列：判斷是否存在列：判斷是否存在xi=xj3.對(duì)角線：主對(duì)角線的對(duì)角線：主對(duì)角線的i-j與從對(duì)角線的與從對(duì)角線的i+j存在特殊關(guān)系，如存在特殊關(guān)系，如圖：圖：9盲目的枚舉算法盲目的枚舉算法n約束條件？約束條件？q不在同一列：不在同一列：xixj；q不在同一主對(duì)角線上：不在同一主對(duì)角線上：xi-i xj-j；q不在同一負(fù)對(duì)角線上：不在同一負(fù)對(duì)角線上：xi+i xj+j。q違規(guī)的情況可以整合改寫為：違規(guī)的情況可以整合改寫為：nabs(xi - xj)=abs( i-j ) or (xi = xj)10盲目的枚舉算法盲目的枚

7、舉算法queen1( ) int a9; for (a1=1;a1=8;a1+) for (a2=1;a2=8;a2+) for (a3=1;a3=8;a3+) for (a4=1;a4=8;a4+) for (a5=1;a5=8;a5+) for (a6=1;a6=8;a6+) for(a7=1;a7=8;a7+) for(a8=1;a8=8;a8+)if (check(a,8)=0) continue; else for(i=1;i=8;i+) print(ai); check1(a,n)int i,j; for(i=2;i=n;i+) for(j=1;j=i-1;j+) if (ai=a

8、j) or (abs(ai-aj)=abs(i-j) return(0); return(1); 雙重循環(huán)，任意兩個(gè)皇雙重循環(huán)，任意兩個(gè)皇后之間都必須檢查。后之間都必須檢查。用用a1a8存儲(chǔ)存儲(chǔ)x1x811n有有“通用的解題法通用的解題法”之稱。之稱。n回溯法的基本做法是回溯法的基本做法是搜索搜索，或是一種組織得井井有條，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問題。用于解一些組合數(shù)相當(dāng)大的問題。n回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)

9、搜索解空間樹。算法搜索至解空間樹的任意結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含，則跳過對(duì)該結(jié)點(diǎn)為根的子樹的搜索，逐層向不包含，則跳過對(duì)該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。先策略搜索。1 回溯法回溯法回溯法指導(dǎo)思想回溯法指導(dǎo)思想走不通，就掉頭。走不通，就掉頭。 12n求問題所有解：要回溯到根，且根結(jié)點(diǎn)的所有子樹都求問題所有解：要回溯到根，且根結(jié)點(diǎn)的所有子樹都已被搜索遍才結(jié)束。已被搜索遍才結(jié)束。n求

10、任一解：只要搜索到問題的一個(gè)解就可結(jié)束。求任一解：只要搜索到問題的一個(gè)解就可結(jié)束。1 回溯法回溯法131 回溯算法設(shè)計(jì)過程回溯算法設(shè)計(jì)過程nstep1 確定問題的解空間；確定問題的解空間；nstep2 確定結(jié)點(diǎn)的擴(kuò)展規(guī)則；確定結(jié)點(diǎn)的擴(kuò)展規(guī)則；nstep3 搜索解空間。搜索解空間。142 回溯法應(yīng)用回溯法應(yīng)用-加約束的枚舉算法加約束的枚舉算法n如果能夠排除那些沒有前途的狀態(tài)，會(huì)節(jié)約時(shí)間；如果能夠排除那些沒有前途的狀態(tài)，會(huì)節(jié)約時(shí)間；n如何提前發(fā)現(xiàn)？如何提前發(fā)現(xiàn)？回溯法指導(dǎo)思想回溯法指導(dǎo)思想走不通，就掉頭走不通，就掉頭 q如如(1,1, x3,x4,x5,x6,x7,x8)沒有必要再擴(kuò)展；沒有必要再

11、擴(kuò)展；n這種狀態(tài)擴(kuò)展后會(huì)產(chǎn)生這種狀態(tài)擴(kuò)展后會(huì)產(chǎn)生86個(gè)結(jié)點(diǎn)；個(gè)結(jié)點(diǎn)；q同樣的同樣的(1,2, x3,x4,x5,x6,x7,x8)，也應(yīng)被排除。也應(yīng)被排除。q在每一次擴(kuò)展在每一次擴(kuò)展E結(jié)點(diǎn)后，都進(jìn)行檢查；結(jié)點(diǎn)后，都進(jìn)行檢查；n對(duì)檢查結(jié)果如何處理？對(duì)檢查結(jié)果如何處理？q檢查合格的才繼續(xù)向下擴(kuò)展；檢查合格的才繼續(xù)向下擴(kuò)展；q遇到不合格的遇到不合格的“掉頭就走掉頭就走”。n只要當(dāng)前枚舉到的狀態(tài)可行，就繼續(xù)枚舉下去。只要當(dāng)前枚舉到的狀態(tài)可行，就繼續(xù)枚舉下去。當(dāng)找到一種方案或者無(wú)法繼續(xù)枚舉下去時(shí)，就退當(dāng)找到一種方案或者無(wú)法繼續(xù)枚舉下去時(shí)，就退回到上一狀態(tài)。退回到上一狀態(tài)的過程叫做回溯，回到上一狀態(tài)。退回

12、到上一狀態(tài)的過程叫做回溯，枚舉下一個(gè)狀態(tài)的過程叫做遞歸。枚舉下一個(gè)狀態(tài)的過程叫做遞歸。n回溯就是像人走迷宮一樣，先選擇一個(gè)前進(jìn)方向回溯就是像人走迷宮一樣，先選擇一個(gè)前進(jìn)方向嘗試，一步步試探，在遇到死胡同不能再往前的嘗試，一步步試探，在遇到死胡同不能再往前的時(shí)候就會(huì)退到上一個(gè)分支點(diǎn)，另選一個(gè)方向嘗試，時(shí)候就會(huì)退到上一個(gè)分支點(diǎn)，另選一個(gè)方向嘗試，而在前進(jìn)和回撤的路上都設(shè)置一些標(biāo)記，以便能而在前進(jìn)和回撤的路上都設(shè)置一些標(biāo)記，以便能夠正確返回，直到達(dá)到目標(biāo)或者所有的可行方案夠正確返回，直到達(dá)到目標(biāo)或者所有的可行方案都已經(jīng)嘗試完為止。都已經(jīng)嘗試完為止。162 回溯法應(yīng)用回溯法應(yīng)用-例例1 b加約束的枚舉

13、算法加約束的枚舉算法我們可以依次確定每一行皇后我們可以依次確定每一行皇后的位置的位置如果在某一列可以放下一個(gè)皇如果在某一列可以放下一個(gè)皇后，我們就在這里放下，并搜后，我們就在這里放下，并搜索下一行索下一行若無(wú)法放下皇后則回到上一行，若無(wú)法放下皇后則回到上一行，即回溯即回溯當(dāng)當(dāng)n行的皇后都已確定后，我們行的皇后都已確定后，我們就找到了一種方案就找到了一種方案182 例例1 b加約束的枚舉算法加約束的枚舉算法queen1( )int a9; for (a1=1;a1=8;a1+) for (a2=1;a2=8;a2+) if ( check(a,2)=0 ) continue; for (a3=1

14、;a3=8;a3+) if (check(a,7)=0) continue; for(a8=1;a8=8;a8+) if (check(a,8)=0)continue; else for(i=1;i=8;i+) print(ai); n此算法可讀性很好，此算法可讀性很好，體現(xiàn)了體現(xiàn)了“回溯回溯”。但。但它只能解決八皇后問它只能解決八皇后問題，而不能解決任意題，而不能解決任意的的n皇后問題。皇后問題。check2 (int a ,int n)/多次被調(diào)用，只是一重循環(huán)多次被調(diào)用，只是一重循環(huán) int i; for(i=1;in) 即表示最后一個(gè)皇后擺放完畢，輸出結(jié)果即表示最后一個(gè)皇后擺放完畢，輸出結(jié)果; else for(i=下界下界 ; i0(有路可走有路可走) and (未達(dá)到目標(biāo)未達(dá)到目標(biāo)) /還未回溯到頭還未回溯到頭 if (i=n) 搜索到一個(gè)解