回溯法实验(n皇后问题)(共9页)

1、算法分析与设计实验报告第 六 次实验姓名学号班级时间12.12上午地点工训楼309 实验名称回溯法实验(n皇后问题)实验目的1. 掌握回溯法求解问题的思想2. 学会利用其原理求解相关问题实验原理用n元组x1:n表示n后问题的解。其中，xi表示皇后i放在棋盘的第i行的第xi列。由于不允许将2个皇后放在同一列上，所以解向量中的xi互不相同。2个皇后不能放在同一斜线上是问题的隐形约束。用回溯法解n后问题时，用完全n叉树表示解空间。可行性约束Place剪出不满足行、列和斜线约束的子树。递归函数Backtrack(1)实现对整个解空间的回溯搜索。 Backtrack(i)搜索解空间中第i层子树。类Que

2、en的数据成员记录解空间中结点信息，以减少传给Backtrack的参数。Sum记录当前已找到的可行方案数。实验步骤数组法：（1）根据n皇后问题，可以把其设想为一个数组；（2）根据n皇后的规则，可以设想为数组上同一直线，横线，斜线的数字都不能相同，由此可以得到判断条件；（3）根据判断条件之后，建立回溯点，即可解决问题。堆栈法：（1） 检索当前行是否可以放置一个皇后；（2） 利用检索过程，通过递归的方式，来确定每一个皇后的位置。关键代码递归回溯：void Queen:Backtrack(int t)if(t>n)sum+;/*for(int i=1;i<=n;i+) /输出皇后排列的解

3、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 += 1; if(xk<=n)

4、/找到位置 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) 而且通过对比递归与迭代两种不同的实现方法，发现情况是基本相同的，时间上并没有什么太大的差距，但是相对的迭代会稍微快一点点。(3) 然后对比输入较大的皇后个数之后，仅仅一个皇后之差就会使得时间上相差很大，如15个皇后的时候所用的时间是280.102，而当皇后个数是16时，所用的时间是2153.463，从而我们可以看出n皇后问题的时间复杂度是指数级的，从而n皇后问题确实是NP问题。实验心得Dijkstra算法在之前的数据结构中就学过，在当时只是学过这种思想，并没有去深思这种思想其背后到底是一种怎样的思想在里面。后来经过本门课的学习，对于贪心算法有了更深刻的了

6、解，也知道了如何利用贪心算法去解决问题。最开心的是经过一定时间的练习，我的编程能力有了一定的提高，之前看见就很头疼的问题，现在也能静下心来去思考，而且实现Dijkstra算法也可以通过一定程度的思考也能写出来了，感觉还是很开心的。Dijkstra算法求单源最短路径在很多地方都有应用，经过一次又一次的练习，终于能好好的掌握这一算法了，还是希望不要那么快忘记啊。实验得分助教签名附录：完整代码（回溯法）/回溯算法 递归回溯 n皇后问题#include<iostream>#include<time.h>#include<iomanip>#include"m

7、ath.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<<"请输入皇后的个数：" /输入皇后个数cin>>n;cout&

8、lt;<"皇后问题的解为："<<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 time is %6.3f",(

9、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=1;i<=n;i+) /输出皇后

10、排列的解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; /动态分配for(int i=0;i<=n;i+) /初始化数组pi=0;X.x=p;X.Backtrack(1);delete p;return X.sum;/输出

11、解的个数完整代码（回溯法）/回溯算法 迭代回溯 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; / 皇后个数 int *x; / 当前解 long s

12、um; / 当前已找到的可行方案数 ; 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); /调用求解皇后问题的函数cout<<n<<

13、;"皇后问题共有" 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)=abs(xj-xk)|(xj=xk) /如

14、果两个皇后在同一斜线或者在同一列上，说明冲突，该位置不可用 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; */