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

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

2、k(i)搜索解空間中第i層子樹。類Queen的數(shù)據(jù)成員記錄解空間中結點信息，以減少傳給Backtrack的參數(shù)。Sum記錄當前已找到的可行方案數(shù)。實驗步驟數(shù)組法：（1）根據(jù)n皇后問題，可以把其設想為一個數(shù)組；（2）根據(jù)n皇后的規(guī)則，可以設想為數(shù)組上同一直線，橫線，斜線的數(shù)字都不能相同，由此可以得到判斷條件；（3）根據(jù)判斷條件之后，建立回溯點，即可解決問題。堆棧法：（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() /迭代法實現(xiàn)回溯函數(shù) 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-; 測試結果較小皇后個數(shù)結果： 遞歸法較大的皇后個數(shù)： 迭代法較大的皇后個數(shù)： 輸入較大的皇后個數(shù)15：輸入皇后個數(shù)是16時：當輸入的皇后個數(shù)是20時：運行了一個上午都沒有出結果，所以果斷放棄了。實驗分析在上述的實驗結果中:(1)

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

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

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

8、個數(shù)cin>>n;cout<<"皇后問題的解為："<<endl;clock_t start,end,over; /計算程序運行時間的算法start=clock();end=clock();over=end-start;start=clock(); m=nQueen(n); /調(diào)用求解的函數(shù)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+) /初始化數(shù)組pi=0;X.x=p;X.Backtrack(1);delet

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

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

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() /迭代法實現(xiàn)回溯函數(shù) 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+;