回溯算法之n皇後問題

今天在看深度優先算法的時候，聯想到DFS本質不就是一個遞歸回溯算法問題，隻不過它是應用在圖論上的。OK，寫下這篇博文也是為了回顧一下回溯算法設計吧。

學習回溯算法問題，最為經典的問題我想應該就是八皇後問題了。

一、适用範圍

　　回溯算法應用的範圍當然是很多了，那麼歸納一下：如果一個問題中，沒有很好的數學模型來解決，或者有數學模型解決，但是很難實作，那麼我們就可以使用回溯算法來求解。

二、定義

回溯算法也叫試探法，它是一種系統地搜尋問題的解的方法。

用回溯算法解決問題的一般步驟：

1 針對所給問題，定義問題的解空間，它至少包含問題的一個（最優）解。

2 确定易于搜尋的解空間結構,使得能用回溯法友善地搜尋整個解空間 。

3 以深度優先的方式搜尋解空間，并且在搜尋過程中用剪枝函數避免無效搜尋。

問題的解空間通常是在搜尋問題解的過程中動态産生的，這是回溯算法的一個重要特性。

例題：八皇後問題

在8*8國際象棋棋盤上，要求在每一行放置一個皇後，且能做到在豎方向，斜方向都沒有沖突。國際象棋的棋盤如下圖所示：

顯然，每一行可以而且必須放一個皇後，是以n皇後問題的解可以用一個n元向量X=（x1,x2,.....xn）表示，其中，1≤ i≤ n且1≤ xi≤ n，即第n個皇後放在第i行第xi列上。

由于兩個皇後不能放在同一列上，是以，解向量X必須滿足的限制條件為:xi≠ xj;

若兩個皇後的擺放位置分别是（i,xi）和（j,xj），在棋盤上斜率為-1的斜線上,滿足條件i-j=xi-xj;在棋盤上斜率為1的斜線上，滿足條件i+j=xi+xj;

綜合兩種情況，由于兩個皇後不能位于同一斜線上，是以，解向量X必須滿足的限制條件為:

|i-xi|≠ |j-xj|

1 #include <cmath>
 2 #include <cstdlib>
 3 #include <iostream>
 4 using namespace std;
 5 const int MAXSIZE=100;
 6 
 7 int Pos_Queen[MAXSIZE];//Pos_Queen[k]代表的含義是第k行的皇後應放在第Pos_Queen[k]列處
 8 int count=0;//全局變量，用來記錄所有可能性數量
 9 bool Is_Safe(int k)//考察皇後k放置在Pos_Queen[k]列是否安全
10 {
11     for(int i=1; i<k; i++)
12         if( Pos_Queen[k] == Pos_Queen[i] || abs(k-i) == abs(Pos_Queen[k]-Pos_Queen[i]) )
13             return false;
14     return true;
15 }
16 
17 //列印皇後擺放情況
18 void Print_Queen( int queenList[], int n )
19 {
20     cout<<"Case "<<(++count)<<":"<<endl;
21     cout<<"  ";
22     for( int i=1; i<=n; i++ )
23     {
24         cout<<i<<" ";
25     }
26     cout<<endl;
27     for( int i=1; i<=n; i++ )
28     {
29         cout<<i<<" ";
30         for( int j=1; j<queenList[i]; j++ )
31         {
32             cout<<"* ";
33         }
34         cout<<"Q ";
35         for( int j=1; j<( n - queenList[i]+1 ); j++ )
36         {
37             cout<<"* ";
38         }
39         cout<<endl;
40     }
41     cout<<endl;
42 }
43 
44 void queue(int n)
45 {
46     int i,k;
47     for(i=1; i<=n; i++)
48         Pos_Queen[i]=0;
49     k=1;
50     while( k>=1 )
51     {
52         Pos_Queen[k] = Pos_Queen[k]+1;   //在下一列放置第k個皇後
53         while( Pos_Queen[k] <= n && !Is_Safe(k) )
54             Pos_Queen[k] = Pos_Queen[k]+1;//搜尋下一列
55         if( Pos_Queen[k] <= n && k == n )//得到一個輸出
56         {
57             count++;
58             //Print_Queen(Pos_Queen,n);
59             //return;//若return則隻求出其中一種解，若不return則可以繼續回溯，求出全部的可能的解
60         }
61         else if( Pos_Queen[k] <= n && k < n )
62             k = k+1;//放置下一個皇後
63         else
64         {
65             Pos_Queen[k]=0;//重置Pos_Queen[k],回溯
66             k = k-1;
67         }
68     }
69 }
70 
71 int main()
72 {
73     int n;
74     cout<<"輸入皇後個數n:";
75     cin>>n;
76     queue(n);
77     cout<<n<<"皇後問題共有"<<count<<"種放法"<<endl;
78     return 0;
79 }      

學習心得：

1.在編寫遞歸枚舉程式之前，需要深入分析問題，對模型精雕細琢。一般還應對解答樹的結點數有一個粗略的估計，作為評價模型的重要依據。

2.如果在回溯法中試用了輔助的全局變量，則一定要及時把它們恢複原狀。例如，若函數有多個出口，則需要在每個出口處恢複被修改的值。

3.從解答樹的角度講，回溯法正是按照深度優先的順序在周遊解答樹。

轉載于:https://www.cnblogs.com/HXloveLL/p/3687230.html