回溯法實驗(n皇后問題)(迭代法)(共9頁)

1、精選優(yōu)質文檔-傾情為你奉上算法分析與設計實驗報告第 三 次附加實驗姓名學號班級時間12.26上午地點工訓樓309 實驗名稱回溯法實驗(n皇后問題)（迭代法）實驗目的1. 掌握回溯法求解問題的思想2. 學會利用其原理求解相關問題實驗原理用n元組x1:n表示n后問題的解。其中，xi表示皇后i放在棋盤的第i行的第xi列。由于不允許將2個皇后放在同一列上，所以解向量中的xi互不相同。2個皇后不能放在同一斜線上是問題的隱形約束。用回溯法解n后問題時，用完全n叉樹表示解空間?？尚行约s束Place剪出不滿足行、列和斜線約束的子樹。遞歸函數Backtrack(1)實現對整個解空間的回溯搜索。 Backtrac

2、k(i)搜索解空間中第i層子樹。類Queen的數據成員記錄解空間中結點信息，以減少傳給Backtrack的參數。Sum記錄當前已找到的可行方案數。實驗步驟數組法：（1）根據n皇后問題，可以把其設想為一個數組；（2）根據n皇后的規(guī)則，可以設想為數組上同一直線，橫線，斜線的數字都不能相同，由此可以得到判斷條件；（3）根據判斷條件之后，建立回溯點，即可解決問題。堆棧法：（1） 檢索當前行是否可以放置一個皇后；（2） 利用檢索過程，通過遞歸的方式，來確定每一個皇后的位置。關鍵代碼遞歸回溯：void Queen:Backtrack(int t)if(t>n)sum+;/*for(int i=1;i

3、<=n;i+) /輸出皇后排列的解cout<<xi<<" "cout<<endl;*/else/回溯探索第i行的每一列是否有元素滿足要求for(int i=1;i<=n;i+)xt=i;if(Place(t)Backtrack(t+1);迭代回溯：void Queen:Backtrack() /迭代法實現回溯函數 x1 = 0; int k = 1; while(k>0) xk += 1; /先將皇后放在第一列的位置上 while(xk<=n)&&!(Place(k) /尋找能夠放置皇后的位置 xk

4、 += 1; if(xk<=n) /找到位置 if(k = n) /如果尋找結束輸出結果 /*for (int i=1;i<=n;i+) cout<<xi<<" " cout<<endl; */ sum+; else /沒有結束則找下一行 k+; xk=0; else /沒有找到合適的位置則回溯 k-; 測試結果較小皇后個數結果： 遞歸法較大的皇后個數： 迭代法較大的皇后個數： 輸入較大的皇后個數15：輸入皇后個數是16時：當輸入的皇后個數是20時：運行了一個上午都沒有出結果，所以果斷放棄了。實驗分析在上述的實驗結果中:(1)

5、 我們可以觀察到輸出皇后排序結果與不輸出結果，只輸出解的個數是有差距的。(2) 而且通過對比遞歸與迭代兩種不同的實現方法，發(fā)現情況是基本相同的，時間上并沒有什么太大的差距，但是相對的迭代會稍微快一點點。(3) 然后對比輸入較大的皇后個數之后，僅僅一個皇后之差就會使得時間上相差很大，如15個皇后的時候所用的時間是280.102，而當皇后個數是16時，所用的時間是2153.463，從而我們可以看出n皇后問題的時間復雜度是指數級的，從而n皇后問題確實是NP問題。實驗心得Dijkstra算法在之前的數據結構中就學過，在當時只是學過這種思想，并沒有去深思這種思想其背后到底是一種怎樣的思想在里面。后來經過

6、本門課的學習，對于貪心算法有了更深刻的了解，也知道了如何利用貪心算法去解決問題。最開心的是經過一定時間的練習，我的編程能力有了一定的提高，之前看見就很頭疼的問題，現在也能靜下心來去思考，而且實現Dijkstra算法也可以通過一定程度的思考也能寫出來了，感覺還是很開心的。Dijkstra算法求單源最短路徑在很多地方都有應用，經過一次又一次的練習，終于能好好的掌握這一算法了，還是希望不要那么快忘記啊。實驗得分助教簽名附錄：完整代碼（回溯法）/回溯算法 遞歸回溯 n皇后問題#include<iostream>#include<time.h>#include<iomani

7、p>#include"math.h"using namespace std;class Queenfriend int nQueen(int); /定義友元函數，可以訪問私有數據private:bool Place(int k); /判斷該位置是否可用的函數void Backtrack(int t); /定義回溯函數int n; /皇后個數int *x; /當前解long sum; /當前已找到的可行方案數;int main()int m,n;for(int i=1;i<=1;i+) cout<<"請輸入皇后的個數：" /輸入皇后

8、個數cin>>n;cout<<"皇后問題的解為："<<endl;clock_t start,end,over; /計算程序運行時間的算法start=clock();end=clock();over=end-start;start=clock(); m=nQueen(n); /調用求解的函數cout<<n<<"皇后問題共有"cout<<m<<"個不同的解！"<<endl; /輸出結果end=clock();printf("The t

9、ime is %6.3f",(double)(end-start-over)/CLK_TCK); /顯示運行時間cout<<endl;system("pause");return 0;bool Queen:Place(int k)/傳入行號for(int j=1;j<k;j+)if(abs(k-j)=abs(xj-xk)|(xj=xk)/如果兩個在同一斜線或者在同一列上，說明沖突，該位置不可用return false;return true;void Queen:Backtrack(int t)if(t>n)sum+;/*for(int i

10、=1;i<=n;i+) /輸出皇后排列的解cout<<xi<<" "cout<<endl;*/else/回溯探索第i行的每一列是否有元素滿足要求for(int i=1;i<=n;i+)xt=i;if(Place(t)Backtrack(t+1);int nQueen(int n)Queen X; /定義Queen類的對象X/初始化XX.n=n;X.sum=0;int *p=new intn+1; /動態(tài)分配for(int i=0;i<=n;i+) /初始化數組pi=0;X.x=p;X.Backtrack(1);delet

11、e p;return X.sum;/輸出解的個數完整代碼（回溯法）/回溯算法 迭代回溯 n皇后問題#include <iostream> #include<time.h>#include<iomanip>#include "math.h" using namespace std; class Queen friend int nQueen(int); /定義友元函數 private: bool Place(int k); /定義位置是否可用的判斷函數 void Backtrack(void); /定義回溯函數 int n; / 皇后個數

12、int *x; / 當前解 long sum; / 當前已找到的可行方案數 ; int main() int n,m; for(int i=1;i<=1;i+)cout<<"請輸入皇后的個數："cin>>n;cout<<n<<"皇后問題的解為："<<endl;clock_t start,end,over; /計算程序運行時間的算法start=clock();end=clock();over=end-start;start=clock(); m=nQueen(n); /調用求解皇后問題的函數

13、cout<<n<<"皇后問題共有" cout<<m<<"個不同的解!"<<endl; end=clock();printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK); /顯示運行時間cout<<endl;system("pause"); return 0; bool Queen:Place(int k) for (int j=1;j<k;j+) if (abs(k-j)=a

14、bs(xj-xk)|(xj=xk) /如果兩個皇后在同一斜線或者在同一列上，說明沖突，該位置不可用 return false; return true; void Queen:Backtrack() /迭代法實現回溯函數 x1 = 0; int k = 1; while(k>0) xk += 1; /先將皇后放在第一列的位置上 while(xk<=n)&&!(Place(k) /尋找能夠放置皇后的位置 xk += 1; if(xk<=n) /找到位置 if(k = n) /如果尋找結束輸出結果 /*for (int i=1;i<=n;i+) cout<<xi<<" " cout<<endl; */ sum+;