随机与回溯结合解决N后问题

《随机与回溯结合解决N后问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法分析与设计》实验报告日期2011.06.01地点西一楼207实验名称课程名称随机与回溯结合解决N后问题算法分析与设计姓名专业班级计算机班学号教师成绩1•实验目的(1)掌握N后问题：N皇后问题是在N*N的棋盘上，放置N个皇后，要求每一横行每一列，每一对角线上均只能放置一个皇后，求解可能的方案及方案数。(2)利用随机与回溯结合的方法设计解决N后问题的算法，掌握算法设计的基本步骤，掌握回溯算法的思想与应用。2•实验内容问题说明：n皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻

2、击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。算法分析：n皇后问题一般是采用回溯法求解，但当n值较大时，回溯算法效率较低，所以此次作业中将随机算法和回溯法结合起来求解n皇后问题，以提高算法的效率。引入随机算法，能保证每次找出的解是正确的，但可能在一次求解过程中找不出可行解，这一点在程序运行过程中能得到体现。3.实验结果以n二8为例说明情况，运行结果如下:请输入＞退出〉：8请送择尊法馆一〉退出；1一＞回溯法;15863724请输入n值5--＞退出〉：8置送择童法5—＞退出；1—＞回溯法;RandomxLl]=6RandomxL2J=2Randomx[3]=

3、562500000请输入n值＜0--＞退出〉:请搖择豊法5—＞退岀;RandomxLl1=8Randomx[2]=4Randomxt3]=784700000请输入n值5--＞退岀〉:请送择尊法＜0—〉退岀;Randomxtl]=5RandomxE2]=1Randomx[3J=481一＞回溯法;2—＞回溯和随机结合法〉：12—＞回溯和随机结合法〉：22—＞回溯和随机结合法〉：22--＞回溯和随机结合法〉：251468273軀爲退旳0当n值较大时，如n=100,此时若用回溯算法，因n值太大，得不出结果，而随机算法却能很快分析出正确结果，这时就体现出了随机算法的优越性了，当n=100时

4、两种算法运行结果分别如下：回溯法随机法与回溯法结合:“..n皇后间题请输入门值5--＞退岀〉：100请连择算法＜0—＞退岀；：L—＞回溯法；2—＞回溯和随机结合法〉：2Randomxtll=36RandonxL2]=3Randomx[3]=76Randomx[43=7Randomx[5J=57RandomxC6]=90Randomxt?]=17Randomx[8]=47Randomx[9J=6RandomxC10]=53RandomxLllJ=78RandomxC12]=66Randomx[13]=12Randomx[14]=18Randonx[15]=39Randomx[16]

5、=60RandomxL17]=80RandomxC18]=23Randomx[19J=14Randonx[20]=82Randomx[213=54Randomx[22]=58Randomx[23]=70RandomxC243=45Randomx[25]=4Randomx[26]=35Randomx[271=9RandomxC28]=94RandomxL291=48Randomx[30]=88Randomx[31]=77Randomx[32]=63Randonx[33]=26Random■xL34J=51■nr4•总结与回顾n皇后问题一般是采用回溯法求解，但当n值较大时，回溯算法效

6、率较低，所以此次作业中将随机算法和回溯法结合起来求解n皐后问题，以提高算法的效率。引入随机算法，能保证每次找出的解是正确的，但可能在一次求解过程中找不出可行解，这一点在程序运行过程中能得到体现。通过本实验，我对n后问题的理解有了进一步的加深；更重要的是对回溯算法的思想有了更深刻的理解，通过冋溯算法与随机算法的比较，了解了冋溯算法在n值较大的情况下存在的不足，同时也了解了随机算法在此时所具备的优越性。在整个实验的过程中，我对算法的基本设计过程有了系统的操作与理解。但由于编程能力的限制，在算法实现过程中遇到了一些障碍，不过在同学的帮助下克服了，最终完成实验。附：源代码#include

7、#include#includeh>usingnamespacestd;intcount,rand_count;〃/判断第k个皇后的(列)位置是否满足要求boolplace(intx[],intk){inti;for(i=1;ivk;++i){if((x[i]==x[k])

8、

9、(abs(x[i]-x[k])==abs(i-k))){returnfalse;}}returntrue;}〃/回溯法求解n皇后问题voidBack_n_que