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

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

3、8個個皇后的位置；皇后的位置；q由于行號固定，可簡單記為：由于行號固定，可簡單記為：(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個狀態；個狀態；n約束條件約束條件：八個：八個(1,x1),(2,x2) ,(3,x3),(4,x4) ,(5,x5), (6,x6) , (7,x7), (8,x8)不在同一行、同一列和同一對角線上。不在同一行、同一列和同一對角線上。n原問題即：在解空間中原問題即：在解空間中尋找符合約束條件尋找符合約束條件的解狀態。的解狀態。n按什么

4、順序去搜？按什么順序去搜？q目標是沒有漏網之魚，盡量速度快。目標是沒有漏網之魚，盡量速度快。6枚舉得有個順序，否則枚舉得有個順序，否則輕則有漏的、重復的；輕則有漏的、重復的；重則無法循環表示。重則無法循環表示。2 【問題設計問題設計】盲目的枚舉算法盲目的枚舉算法na 盲目的枚舉算法盲目的枚舉算法q通過通過8重循環模擬搜索空間中的重循環模擬搜索空間中的88個狀態；個狀態；q按按枚舉思想枚舉思想，以以DFS的方式的方式，從第，從第1個皇后在第個皇后在第1列開始列開始搜索，枚舉出所有的搜索，枚舉出所有的“解狀態解狀態”：n從中找出滿足約束條件的從中找出滿足約束條件的“答案狀態答案狀態”。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、枚舉的，保證了一行一個皇后；行；我們是按照行枚舉的，保證了一行一個皇后；2.列：判斷是否存在列：判斷是否存在xi=xj3.對角線：主對角線的對角線：主對角線的i-j與從對角線的與從對角線的i+j存在特殊關系，如存在特殊關系，如圖：圖：9盲目的枚舉算法盲目的枚舉算法n約束條件？約束條件？q不在同一列：不在同一列：xixj；q不在同一主對角線上：不在同一主對角線上：xi-i xj-j；q不在同一負對角線上：不在同一負對角線上：xi+i xj+j。q違規的情況可以整合改寫為：違規的情況可以整合改寫為：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); 雙重循環，任意兩個皇雙重循環，任意兩個皇后之間都必須檢查。后之間都必須檢查。用用a1a8存儲存儲x1x811n有有“通用的解題法通用的解題法”之稱。之稱。n回溯法的基本做法是回溯法的基本做法是搜索搜索，或是一種組織得井井有條，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數相當大的問題。用于解一些組合數相當大的問題。n回溯法在問題的解空間樹中，按深度優先策略，從根回溯法在問題的解空間樹中，按深度優先策略，從根結點出發

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

10、任一解：只要搜索到問題的一個解就可結束。求任一解：只要搜索到問題的一個解就可結束。1 回溯法回溯法131 回溯算法設計過程回溯算法設計過程nstep1 確定問題的解空間；確定問題的解空間；nstep2 確定結點的擴展規則；確定結點的擴展規則；nstep3 搜索解空間。搜索解空間。142 回溯法應用回溯法應用-加約束的枚舉算法加約束的枚舉算法n如果能夠排除那些沒有前途的狀態，會節約時間；如果能夠排除那些沒有前途的狀態，會節約時間；n如何提前發現？如何提前發現？回溯法指導思想回溯法指導思想走不通，就掉頭走不通，就掉頭 q如如(1,1, x3,x4,x5,x6,x7,x8)沒有必要再擴展；沒有必要再

11、擴展；n這種狀態擴展后會產生這種狀態擴展后會產生86個結點；個結點；q同樣的同樣的(1,2, x3,x4,x5,x6,x7,x8)，也應被排除。也應被排除。q在每一次擴展在每一次擴展E結點后，都進行檢查；結點后，都進行檢查；n對檢查結果如何處理？對檢查結果如何處理？q檢查合格的才繼續向下擴展；檢查合格的才繼續向下擴展；q遇到不合格的遇到不合格的“掉頭就走掉頭就走”。n只要當前枚舉到的狀態可行，就繼續枚舉下去。只要當前枚舉到的狀態可行，就繼續枚舉下去。當找到一種方案或者無法繼續枚舉下去時，就退當找到一種方案或者無法繼續枚舉下去時，就退回到上一狀態。退回到上一狀態的過程叫做回溯，回到上一狀態。退回

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

13、算法加約束的枚舉算法我們可以依次確定每一行皇后我們可以依次確定每一行皇后的位置的位置如果在某一列可以放下一個皇如果在某一列可以放下一個皇后，我們就在這里放下，并搜后，我們就在這里放下，并搜索下一行索下一行若無法放下皇后則回到上一行，若無法放下皇后則回到上一行，即回溯即回溯當當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此算法可讀性很好，此算法可讀性很好，體現了體現了“回溯回溯”。但。但它只能解決八皇后問它只能解決八皇后問題，而不能解決任意題，而不能解決任意的的n皇后問題。皇后問題。check2 (int a ,int n)/多次被調用，只是一重循環多次被調用，只是一重循環 int i; for(i=1;in) 即表示最后一個皇后擺放完畢，輸出結果即表示最后一個皇后擺放完畢，輸出結果; else for(i=下界下界 ; i0(有路可走有路可走) and (未達到目標未達到目標) /還未回溯到頭還未回溯到頭 if (i=n) 搜索到一個解