回溯法实验n皇后问题迭代法

《回溯法实验n皇后问题迭代法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

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

3、um++;/*for(inti=1;i<=n;i++)//输出皇后排列的解{cout<0){x[k]+=1;//先将皇后放在第一列的位置上while((x[k]<=n)&&!(Place(k)))//寻找能够

4、放置皇后的位置{x[k]+=1;}if(x[k]<=n)//找到位置{if(k==n)//如果寻找结束输出结果{/*for(inti=1;i<=n;i++){cout<

5、述的实验结果中:(1)我们可以观察到输出皇后排序结果与不输出结果，只输出解的个数是有差距的。(2)而且通过对比递归与迭代两种不同的实现方法，发现情况是基本相同的，时间上并没有什么太大的差距，但是相对的迭代会稍微快一点点。(3)然后对比输入较大的皇后个数之后，仅仅一个皇后之差就会使得时间上相差很大，如15个皇后的时候所用的时间是280.102，而当皇后个数是16时，所用的时间是2153.463，从而我们可以看出n皇后问题的时间复杂度是指数级的，从而n皇后问题确实是NP问题。实验心得Dijkstra算法在之前的数据结构中就学过，在当时只是学过这种思想，并没有去深思这种

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

7、time.h>#include#include"math.h"usingnamespacestd;classQueen文案大全实用文档{friendintnQueen(int);//定义友元函数，可以访问私有数据private:boolPlace(intk);//判断该位置是否可用的函数voidBacktrack(intt);//定义回溯函数intn;//皇后个数int*x;//当前解longsum;//当前已找到的可行方案数};intmain(){intm,n;for(inti=1;i<=1;i++){cout<<"请输入皇后的个数：";//输

8、入皇后个数