基本算法4-回溯法-N皇后问题
- 格式:ppt
- 大小:1.26 MB
- 文档页数:23
n皇后问题实验报告n皇后问题实验报告引言:n皇后问题是一个经典的数学问题,它要求在一个n×n的棋盘上放置n个皇后,使得它们互相之间不能相互攻击,即任意两个皇后不能处于同一行、同一列或同一对角线上。
本实验旨在通过编程实现n皇后问题的求解,并探索不同算法在解决该问题上的性能差异。
实验步骤及结果:1. 回溯算法的实现与性能分析回溯算法是最常见的解决n皇后问题的方法之一。
它通过递归的方式遍历所有可能的解,并通过剪枝操作来提高效率。
我们首先实现了回溯算法,并对不同规模的问题进行了求解。
在测试中,我们将问题规模设置为4、8、12和16。
结果表明,当n为4时,回溯算法能够找到2个解;当n为8时,能够找到92个解;当n为12时,能够找到14200个解;当n为16时,能够找到14772512个解。
可以看出,随着问题规模的增加,回溯算法的求解时间呈指数级增长。
2. 启发式算法的实现与性能分析为了提高求解效率,我们尝试了一种基于启发式算法的解决方法。
在该方法中,我们使用了遗传算法来搜索解空间。
遗传算法是一种模拟生物进化过程的优化算法,通过进化操作(如选择、交叉和变异)来寻找问题的最优解。
我们将遗传算法应用于n皇后问题,并对不同规模的问题进行了求解。
在测试中,我们将问题规模设置为8、12和16。
结果表明,遗传算法能够在较短的时间内找到问题的一个解。
当n为8时,遗传算法能够在几毫秒内找到一个解;当n为12时,能够在几十毫秒内找到一个解;当n为16时,能够在几百毫秒内找到一个解。
相比之下,回溯算法在同样规模的问题上需要几秒钟甚至更长的时间。
3. 算法性能对比与分析通过对比回溯算法和启发式算法的性能,我们可以看到启发式算法在求解n皇后问题上具有明显的优势。
回溯算法的求解时间随问题规模呈指数级增长,而启发式算法的求解时间相对较短。
这是因为启发式算法通过优化搜索策略,能够更快地找到问题的解。
然而,启发式算法并非没有缺点。
算法分析与设计实验报告第三次附加实验附录:完整代码(回溯法)//回溯算法递归回溯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(int t); //定义回溯函数int n; //皇后个数int *x; //当前解long sum; //当前已找到的可行方案数};int main(){int m,n;for(int i=1;i<=1;i++){cout<<"请输入皇后的个数:"; //输入皇后个数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 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(x[j]-x[k]))||(x[j]==x[k]))//如果两个在同一斜线或者在同一列上,说明冲突,该位置不可用{return false;}}return true;}void Queen::Backtrack(int t){if(t>n){sum++;/*for(int i=1;i<=n;i++) //输出皇后排列的解{cout<<x[i]<<" ";}cout<<endl;*/}else{//回溯探索第i行的每一列是否有元素满足要求for(int i=1;i<=n;i++){x[t]=i;if(Place(t)){Backtrack(t+1);}}}}int nQueen(int n){Queen X; //定义Queen类的对象X//初始化XX.n=n;X.sum=0;int *p=new int[n+1]; //动态分配for(int i=0;i<=n;i++) //初始化数组{p[i]=0;}X.x=p;X.Backtrack(1);delete[] 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; // 皇后个数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); //调用求解皇后问题的函数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)==abs(x[j]-x[k]))||(x[j]==x[k])) //如果两个皇后在同一斜线或者在同一列上,说明冲突,该位置不可用{return false;}}return true;}void Queen::Backtrack() //迭代法实现回溯函数{x[1] = 0;int k = 1;while(k>0){x[k] += 1; //先将皇后放在第一列的位置上while((x[k]<=n)&&!(Place(k))) //寻找能够放置皇后的位置{x[k] += 1;}if(x[k]<=n) //找到位置{if(k == n) //如果寻找结束输出结果{/*for (int i=1;i<=n;i++){cout<<x[i]<<" ";}cout<<endl; */sum++;}else//没有结束则找下一行{k++;x[k]=0;}}else//没有找到合适的位置则回溯{ k--; }}}int nQueen(int n){Queen X; //定义Queen类的对象X//初始化XX.n=n;X.sum=0;int *p=new int[n+1];for(int i=0;i<=n;i++){p[i]=0;}X.x=p;X.Backtrack();delete []p;return X.sum; //返回不同解的个数}。
实验四N 皇后问题求解、题目1) 以Q-皇后问题为例,掌握回溯法的基本设计策略。
2) 掌握回溯法解决Q-皇后问题的算法并实现;二、算法设计思想回溯法是在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。
当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。
(其实回溯法就是对隐式图的深度优先搜索算法)。
若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。
而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束。
判断解是否可行的条件:1. 不在同一行或者同一列,x[i]!=x[j],i!=j2•不在一条斜线上,设两个皇后在(i,j)和(k,l)位置,卜k|!=|j-l|三、程序#include<stdio.h>#include<stdlib.h>int n,stack[100]; // 存当前路径int total; // 路径数int att(int,int);void make(int l) //递归搜索以stack[l]为初结点的所有路径{int i,j; //子结点个数if (l==n+1){total=total+1; // 路径数+1 for(i=1;i<=n;i++)printf(" 输出皇后的列位置%-3d",stack[i]);// 输出第i 行皇后的列位置stack[i]}int att(int l,int i){}for (i=1;i<=n;i++){stack[l]=i; II算符i 作用于生成stack[l-1]产生子状态stack[l];if (!att(l,i))make(l+1);printf("\n");exit; II 回溯} II 再无算符可用,回溯int k;for (k=1;k<l;k++)if (abs(l-k)==abs(stack[k]-i)||i==stack[k])return 1;return 0;}int main(){}四、运行结果printf("N=");scanf("%d",&n);total=0; II 路径数初始化为0make(1); II从结点1出发,递归搜索所有的路径printf("%d\n",total);system("pause");return 0;六、心得体会在解决N皇后的时候一开始有点不止如何着手,因为这里有个N的不确定性,所以选择简单少量的情况进行具体考虑显得相对容易了许多,还有一个值得注意的问题就是如何判断要不要重新开始搜索,并且在已经形成的简单模型基础上进行改进,使之也能满足后面较复杂情况。
⼋皇后以及N皇后问题分析⼋皇后是⼀个经典问题,在8*8的棋盘上放置8个皇后,每⼀⾏不能互相攻击。
因此拓展出 N皇后问题。
下⾯慢慢了解解决这些问题的⽅法:回溯法:回溯算法也叫试探法,它是⼀种系统地搜索问题的解的⽅法。
回溯算法的基本思想是:从⼀条路往前⾛,能进则进,不能进则退回来,换⼀条路再试。
在现实中,有很多问题往往需要我们把其所有可能穷举出来,然后从中找出满⾜某种要求的可能或最优的情况,从⽽得到整个问题的解。
回溯算法就是解决这种问题的“通⽤算法”,有“万能算法”之称。
N皇后问题在N增⼤时就是这样⼀个解空间很⼤的问题,所以⽐较适合⽤这种⽅法求解。
这也是N皇后问题的传统解法,很经典。
算法描述:1. 算法开始,清空棋盘。
当前⾏设为第⼀⾏,当前列设为第⼀列。
2. 在当前⾏,当前列的判断放置皇后是否安全,若不安全,则跳到第四步。
3. 在当前位置上满⾜条件的情况: 在当前位置放⼀个皇后,若当前⾏是最后⼀⾏,记录⼀个解; 若当前⾏不是最后⼀⾏,当前⾏设为下⼀⾏,当前列设为当前⾏的第⼀个待测位置; 若当前⾏是最后⼀⾏,当前列不是最后⼀列,当前列设为下⼀列; 若当前⾏是最后⼀⾏,当前列是最后⼀列,回溯,即清空当前⾏以及以下各⾏的棋盘,然后当前⾏设为上⼀⾏,当前列设为当前⾏的下⼀个待测位置; 以上返回第⼆步。
4.在当前位置上不满⾜条件: 若当前列不是最后⼀列,当前列设为下⼀列,返回到第⼆步; 若当前列是最后⼀列,回溯,即,若当前⾏已经是第⼀⾏了,算法退出,否则,清空当前⾏以及以下各⾏的棋盘,然后,当前⾏设为上⼀⾏,当前列设为当前⾏的下⼀个待测位置,返回第⼆步。
如何判断是否安全:把棋盘存储为⼀个N维数组a[N],数组中第i个元素的值代表第i⾏的皇后位置,这样便可以把问题的空间规模压缩为⼀维O(N),在判断是否冲突时也很简单, ⾸先每⾏只有⼀个皇后,且在数组中只占据⼀个元素的位置,⾏冲突就不存在了, 其次是列冲突,判断⼀下是否有a[i]与当前要放置皇后的列j相等即可。
实验报告4回溯算法实验4回溯算法解决N皇后问题一、实验目的1)掌握回溯算法的实现原理,生成树的建立以及限界函数的实现;2)利用回溯算法解决N皇后问题;二、实验内容回溯算法解决N皇后问题。
三、算法设计1)编写限界函数bool PLACE(int k,int x[]),用以确定在k列上能否放置皇后;2)编写void NQUEENS(int n)函数用以摆放N个皇后;3)编写主函数,控制输入的皇后数目;4)改进和检验程序。
四、程序代码//回溯算法解决N皇后问题的c++程序#include<math.h>#include<iostream>using namespace std;int count=0; //皇后摆放的可能性bool PLACE(int k,int x[]);//限界函数void NQUEENS(int n);//摆放皇后int main(){}int queen;cout<<"先生(女士)请您输入皇后的总数,谢谢!:"<<endl;cin>>queen;NQUEENS(queen);cout<<"所有可能均摆放完毕,谢谢操作"<<endl;return 0;void NQUEENS(int n){/*此过程使用回溯算法求出在一个n*n棋盘上放置n个皇后,使其即不同行,也不同列,也不在同一斜角线上*/int k, *x=new int[n];//存放皇后所在的行与列x[0]=0;k=0;while (k>=0&&k<n){ //对所有的行执行以下语句x[k]=x[k]+1; //移到下一列while(x[k]<=n&&(!PLACE(k,x))){ //此处能放置一个皇后吗?}if( x[k]<=n ) { //找到一个位置if( k==n-1 ){ //是一个完整的解吗cout<<"第"<<++count<<"排法是:"<<endl;for(int i=0;i<n;i++)//打印皇后的排列{}cout<<"\n";for (int j=0;j<n;j++){}cout<<"\n";if (x[i] == j+1){}else{}cout<<". ";cout<<"*";x[k]=x[k]+1; //移到下一列}}}}else { k=k+1; x[k]=0;} //移向下一行else k=k-1; //回溯bool PLACE(int k,int x[]){/*如果一个皇后能放在第k行和x(k)列,返回ture;否则返回false。
实验报告一、实验名称:回溯法求解N皇后问题(Java实现)二、学习知识:回溯法:也称为试探法,它并不考虑问题规模的大小,而是从问题的最明显的最小规模开始逐步求解出可能的答案,并以此慢慢地扩大问题规模,迭代地逼近最终问题的解。
这种迭代类似于穷举并且是试探性的,因为当目前的可能答案被测试出不可能可以获得最终解时,则撤销当前的这一步求解过程,回溯到上一步寻找其他求解路径。
为了能够撤销当前的求解过程,必须保存上一步以来的求解路径,这一点相当重要。
三、问题描述N皇后问题:在一个 N * N 的国际象棋棋盘中,怎样放置 N 个皇后才能使N 个皇后之间不会互相有威胁而共同存在于棋局中,即在 N * N 个格子的棋盘中没有任何两个皇后是在同一行、同一列、同一斜线上。
深度优先遍历的典型案例。
四、求解思路1、求解思路:最容易想到的方法就是有序地从第1列的第 1 行开始,尝试放上一个皇后,然后再尝试第2 列的第几行能够放上一个皇后,如果第 2 列也放置成功,那么就继续放置第 3 列,如果此时第3列没有一行可以放置一个皇后,说明目前为止的尝试是无效的(即不可能得到最终解),那么此时就应该回溯到上一步(即第 2 步),将上一步(第 2 步)所放置的皇后的位置再重新取走放在另一个符合要求的地方…如此尝试性地遍历加上回溯,就可以慢慢地逼近最终解了。
2、需要解决的问题:如何表示一个N * N 方格棋盘能够更有效?怎样测试当前所走的试探路径是否符合要求?这两个问题都需要考虑到使用怎样的数据结构,使用恰当的数据结构有利于简化编程求解问题的难度。
3、我们使用以下的数据结构:int column[col] = row 表示第 col 列的第 row 行放置一个皇后boolean rowExi sts[i] = true 表示第 i 行有皇后boolean a[i] = true 表示右高左低的第 i 条斜线有皇后(按→↓顺序从1~ 2*N -1 依次编号)boolean b[i] = true 表示左高右低的第 i 条斜线有皇后(按→↑顺序从1~ 2*N -1 依次编号)五、算法实现对应这个数据结构的算法实现如下:1.**2. * 回溯法求解N 皇后问题3. * @author haollo yin4. */5.public classN_Quee ns {6.7.// 皇后的个数8. privat e int queens Num = 4;9.10.// column[i] = j表示第 i 列的第 j 行放置一个皇后11. privat e int[] queens = new int[queens Num + 1];12.13.// rowExi sts[i] = true 表示第 i 行有皇后14. privat e boolea n[] rowExi sts = new boolea n[queensNum + 1];15.16.// a[i] = true 表示右高左低的第 i 条斜线有皇后17. privat e boolea n[] a = new boolea n[queens Num * 2];18.19.// b[i] = true 表示左高右低的第 i 条斜线有皇后20. privat e boolea n[] b = new boolea n[queens Num * 2];21.22.// 初始化变量23. privat e void init() {24. for (int i = 0; i < queens Num + 1; i++) {25. rowExi sts[i] = false;26. }27.28. for(int i = 0; i < queens Num * 2; i++) {29. a[i] = b[i] = false;30. }31. }32.33.// 判断该位置是否已经存在一个皇后,存在则返回true34. privat e boolea n isExis ts(int row, int col) {35. return (rowExi sts[row] || a[row + col - 1]|| b[queens Num + col - row]);36. }37.38.// 主方法:测试放置皇后39. public void testin g(int column) {40.41.// 遍历每一行42. for (int row = 1; row < queens Num + 1; row++) {43.// 如果第 row 行第 column列可以放置皇后44. if (!isExis ts(row, column)) {45.// 设置第 row 行第 column列有皇后46. queens[column] = row;47.// 设置以第 row 行第 column列为交叉点的斜线不可放置皇后48. rowExi sts[row] = a[row + column - 1] = b[queens Num + column - row] = true;49.50.// 全部尝试过,打印51. if(column == queens Num) {52. for(int col = 1; col <= queens Num; col++) {53. System.out.print("("+col +"," + queens[col] + ") ");54. }55. System.out.printl n();56. }else {57.// 放置下一列的皇后58. testin g(column + 1);59. }60.// 撤销上一步所放置的皇后,即回溯61. rowExi sts[row] = a[row + column - 1] = b[queens Num + column - row] = false;62. }63. }64. }65.66.//测试67. public static void main(String[] args) {68. N_Quee ns queen= new N_Quee ns();69. queen.init();70.// 从第 1 列开始求解71. queen.testin g(1);72. }73.}六、运行结果当N = 8 时,求解结果如下(注:横坐标为列数,纵坐标为行数):(1,1) (2,5) (3,8) (4,6) (5,3) (6,7) (7,2) (8,4)1.(1,1) (2,6) (3,8) (4,3) (5,7) (6,4) (7,2) (8,5)2.(1,1) (2,7) (3,4) (4,6) (5,8) (6,2) (7,5) (8,3)3.... ...4.... ...5.(1,8) (2,2) (3,4) (4,1) (5,7) (6,5) (7,3) (8,6)6.(1,8) (2,2) (3,5) (4,3) (5,1) (6,7) (7,4) (8,6)7.(1,8) (2,3) (3,1) (4,6) (5,2) (6,5) (7,7) (8,4)8.(1,8) (2,4) (3,1) (4,3) (5,6) (6,2) (7,7) (8,5)当N = 4 时,求解结果如下:1.(1,2) (2,4) (3,1) (4,3)2.(1,3) (2,1) (3,4) (4,2)七、实验小结:1、根据问题选择恰当的数据结构非常重要,就像上面 a 、b 标志数组来表示每一条斜线的编号顺序以及方向都相当重要。
回溯法解决N皇后问题C语⾔问题描述:⼋皇后问题是⼀个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置⼋个皇后,使得任何⼀个皇后都⽆法直接吃掉其他的皇后?为了达到此⽬的,任两个皇后都不能处于同⼀条横⾏、纵⾏或斜线上。
回溯法:回溯法⼜称试探法。
回溯法的基本做法是深度优先搜索。
即从⼀条路往前⾛,能进则进,不能进则退回来,换⼀条路再试。
源代码:#include<stdio.h>#include<math.h>int x[9]={0};bool PLACE(int k)//检测第k个皇后能否放进棋盘{int i=1;while(i<k){if(x[i]==x[k]||fabs(x[i]-x[k])==fabs(i-k))return false;i++;}return true;}void NQUEENS(int n){int i,k=1; //k为当前⾏号x[1]=0;//x[k]为第k⾏皇后所放的列号while(k>0){x[k]++;while(x[k]<=n&&!PLACE(k))//该⾏不符合,则放⼊下⼀⾏x[k]++;if(x[k]<=n){if(k==n)//输出x[]{for(i=1;i<=n;i++)printf("x[%d]:%d ",i,x[i]);printf("\n");}else//判断下⼀⾏{k++; x[k]=0;}}else k--;//没找到,则回溯}return ;}int main(){NQUEENS(8);return0;}。