《回溯法实验》由会员分享，可在线阅读，更多相关《回溯法实验（20页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计实验报告第三次附加实验姓名学号班级时间12.26上午地点工训楼309实验名称回溯法实验（n皇后问题）（迭代法）实验目的1. 掌握回溯法求解问题的思想2. 学会利用其原理求解相关问题实验原理用n元组x1:n表示n后问题的解。其中，xi表示皇后i放在棋盘的第i 行的第xi列。由于不允许将2个皇后放在同一列上，所以解向量中的xi 互不相同。2个皇后不能放在同一斜线上是问题的隐形约束。用回溯法解n后问题时，用完全n叉树表示解空间。可行性约束Place剪出不 满足行、列和斜线约束的子树。递归函数Backtrack（1）实现对整个解空间的回溯搜索。Backtrack（i）搜索解 空间中第i层
2、子树。类Queen的数据成员记录解空间中结点信息，以减少传给 Back track的参数。Sum记录当前已找到的可行方案数。实验步骤数组法：（1）根据n皇后问题，可以把其设想为一个数组；（2）根据n皇后的规则，可以设想为数组上同一直线，横线，斜线的数字都 不能相同，由此可以得到判断条件；（3）根据判断条件之后，建立回溯点，即可解决问题。堆栈法：（1）检索当前行是否可以放置一个皇后；（2）利用检索过程，通过递归的方式，来确定每一个皇后的位置。关键代码递归回溯：void Queen:Backtrack(int t)if(tn)sum+;/*for(int i=l;i=n;i+)/输出皇后排列的解c
3、outxi;coutendl;*/else/回溯探索第i行的每一列是否有元素满足要求for(int i=l;i0)xk += 1;/先将皇后放在第一列的位置上while(xk=n)&!(Place(k) /寻找能够放置皇后的 位置 xk += 1;if(xk=n)/找到位置if(k = n) /如果寻找结束输出结果/*for (int i=l;i=n;i+)coutxi ;coutendl; */ sum+;else /没有结束则找下一行k+;xk=0;else /没有找到合适的位置则回溯k;较小皇后个数结果：3 F:算法实锹实验四回溯法n_queenDebugn_queen.exe憶顿人呈屁
4、胆个数：吗 星嘗冋题的解为:B 4 1 33 14 2咗皇后问题共有2个不同的解!The time is 0.014请按任意键继续- 递归法较大的皇后个数：迭代法较大的皇后个数：:8:10:11主壬,宅有M盹个不同的解?0.187勺个数；12皇后眈个不同的解!0.005后的僻丫亘衣务必个不同的解?is 0.054亍间粵扌ime isime is鬻品个不同的解?5.769呈后卩he t ime is自百问题共有女2个不同的解?t ime is 0.031Y X M二馆爪前题共有142丽个不同的解?ime is 0.966亘二笃势1310.2-1.0数.丸 .勺.9 0勺.3 驻有勢有 后的E；
5、i后的酎 白 _ 一题11rle皇题11 紺.elti入爭请旦1.广 2ly10 c8S:.0数720右有的垦i后的题i后的题i后的题i后的题i曲 me呈题间置_=题问rle白_=题问詈_=题间rle咅 ti入星ti人星.Alti入男ti elD 王 王 e9f 王 王 e rh主i 厲主酉壬Lirh主酉mL25主署壬L3rh主数：師.1数：14.9数：73.8 有0有阿有5吐 勺力牛土. 勺力牛土. 內力牛土.LL Tnnj-ulJ_7s /Du n.fllA- s rtn s输入较大的皇后个数15 :2) F: 算法宴验宴验四回溯法jq U eenDeb gn_q u een. exe幘穆
6、人皇屈的丫熱佔 區后回題的A 匡皇启冋题#2279184个不同的解!The time is 288.1S2请按任意键继续 输入皇后个数是16时:J*l IF:算法实验百&验四回溯法n.queer2Debugn_qu了却2e=xe*哇石冋题单蛍労：A 1石皇启冋题共#14772512个不同的解辛 rTlie tine is 2153.463捨按任意键继练当输入的皇后个数是20时：运行了一个上午都没有出结果，所以果断放弃了。3 FR算法卖验宜验四回蒯法n_queffn2Debugn_queen2.eKe-20在上述的实验结果中：(1) 我们可以观察到输出皇后排序结果与不输出结果，只输出解的个数是有
7、差 距的。实验分析(2) 而且通过对比递归与迭代两种不同的实现方法，发现情况是基本相同的, 时间上并没有什么太大的差距，但是相对的迭代会稍微快一点点。(3) 然后对比输入较大的皇后个数之后，仅仅一个皇后之差就会使得时间上相 差很大，如15个皇后的时候所用的时间是280.102，而当皇后个数是16时， 所用的时间是2153.463，从而我们可以看出n皇后问题的时间复杂度是指数 级的，从而n皇后问题确实是NP问题。Dijkstra算法在之前的数据结构中就学过，在当时只是学过这种思想，并没 有去深思这种思想其背后到底是一种怎样的思想在里面。后来经过本门课的学 习，对于贪心算法有了更深刻的了解，也知道
8、了如何利用贪心算法去解决问题。 最开心的是经过一定时间的练习，我的编程能力有了一定的提高，之前看见就 很头疼的问题，现在也能静下心来去思考，而且实现Dijkstra算法也可以通 过一定程度的思考也能写出来了，感觉还是很开心的。Dijkstra算法求单源 最短路径在很多地方都有应用，经过一次又一次的练习，终于能好好的掌握这算法了，还是希望不要那么快忘记啊。实验得分助教签名附录： 完整代码(回溯法)/回溯算法 递归回溯n皇后问题#include#include#include#includemath.husing namespace std;class Queenfriend int nQueen
9、(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+)coutn;cout皇后问题的解为：endl;clock_t start,end,over；/计算程序运行时间的算法start=clock();end=clock();over=end-start;start=clock();m=nQueen(n); /
10、调用求解的函数coutn皇后问题共有;coutm个不同的解！endl;/输出结果end=clock();printf(The time is %6.3f,(double)(end-start-over)/CLK_TCK); /显示运行时间coutendl;system(pause);return 0;bool Queen:Place(int k)/传入行号for(int j=1;jn)sum+;/*for(int i=1;i=n;i+) /输出皇后排列的解 coutxi ;coutendl;*/else/回溯探索第i行的每一列是否有元素满足要求for(int i=1;i=n;i+)xt=i;i
11、f(Place(t)Backtrack(t+1);int nQueen(int n)Queen X; /定义Quee n类的对象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;ret urn X.sum;/输出解的个数完整代码(回溯法)/回溯算法迭代回溯n皇后问题#include #include#include#includemath.husing namespace std;class Queenfriend int nQuee
12、n(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+)coutn;coutn皇后问题的解为：endl;clock_t start,end,over; /计算程序运行时间的算法start=clock();end=clock();over=end-start;start=clock();m=nQueen(n); /调用求解皇后问题的函数coutn皇后问题共有;cou tm个不同的解！endl;end=clock();printf(T
