算法实验 递归回溯解八皇后问题.doc

《算法实验 递归回溯解八皇后问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、深圳大学实验报告课程名称：算法分析与复杂性理论实验项目名称：八皇后问题学院：计算机与软件学院专业：软件工程指导教师：烜报告人：学号：班级：15级软工学术型实验时间：2015-12-08实验报告提交时间：2015-12-09教务部制一．实验目的1.掌握选回溯法设计思想。2.掌握八皇后问题的回溯法解法。二．实验步骤与结果实验总体思路：根据实验要求，通过switch选择八皇后求解模块以及测试数据模块操作，其中八皇后模块调用摆放皇后函数模块，摆放皇后模块中调用判断模块。测试数据模块主要调用判断模块进行判断，完成测试。用

2、一维数组保存每行摆放皇后的位置，根据回溯法的思想递归讨论该行的列位置上能否放置皇后，由判断函数Judge()判断，若不能放置则检查该行下一个位置。相应结果和过程如下所示（代码和结果如下图所示）。回溯法的实现及实验结果：1、判断函数代码1：procedureBTrack_Queen(n)//如果一个皇后能放在第K行和X(k)列，则返回true，否则返回false。global X(1:k);integer i,ki←1while i

3、k)thenreturn (false)endifi←i+1repeatreturn (true)end Judge2、回溯递归求解代码2：procedureBTrack_Queen(n)integerk,n,X(1:n)X(1)←0;k←1   //k是当前行，X(k)是当前行的位置whilek>0doX(k)←X(k)+1  //移到下一个位置whileX(k)<=nandnotJudge(k)do   //判断能否放置皇后X(k)←X(k)+1repeatifX(k)<=n              //找

4、到一个位置thenifk=n         //是一个完整的解吗thenprint(X)     //是，打印数组elsek←k+1;X(k)←0    //转向下一行endifelsek←k-1    //否则，回溯上一行endifrepeatendBTrack_Queen实验结果：(图1回溯法解八皇后问题)(图2回溯法解八皇后问题)(图3测试数据结果)注：根据实验数组中保存的列坐标，对应行坐标顺序输入即可。实验中多加入了一组不满足八皇后问题的解。MFC可视化下八皇后的实现与结果：代码3：//判断是否符合八皇

5、后问题的解intCBfhouDlg::check(introw,intcol){//看同行是否合法;for(inti=0;i<=col-1;i++){if(a[row][i]==1)return0;}for(i=col+1;i<8;i++){if(a[row][i]==1)return0;}//看同列是否合法;for(i=0;i<=row-1;i++){if(a[i][col]==1)return0;}for(i=row+1;i

6、;i=row-1;j=col+1;while(i>=0&&j<=N-1){if(a[i][j]==1)return0;--i;++j;}i=row+1;j=col-1;while((i<=N-1)&&j>=0){if(a[i][j]==1)return0;++i;--j;}i=row-1;j=col-1;while(i>=0&&j>=0){if(a[i][j]==1)return0;--i;--j;}i=row+1;j=col+1;while((i<=N-1)&&j<=N-1){if(a[i][j]==1)ret

7、urn0;++i;++j;}return1;}实验结果：（图4八皇后的第1种解）(图5八皇后的第92种解)注：由于时间有限，这个月考试较多，程序还要很多地方需要完善。三．实验分析与结论根据八皇后问题的规则皇后不能放置在同行、同列及同一对角线上，进而将问题转化为将第i个皇后放在第i行第x[i]列上(1

8、i－x[i]

9、!=

10、j－x[j]

11、。八皇后问题的解法主要有枚举法、非递归回溯法、递归回溯法这三种，枚举法是将所以的可能组合都进行判断，

12、时间复杂度为O(nn),适用于个数n比较少的情况。而非递归回溯法采用深度优先搜索策略判断当前位置是否符合该问题的解，时间复杂度为O(n2)，在实现大规模的N皇后问题上性能更好。递归回溯法同样采用深度优先搜索策略，但在搜索到不满足约束条件时能及时回溯，整体上提高了解题的效率。时间复杂度较非回溯法更低。四．实验心得八皇后问题以前也看过，只是以前没有将测试数据模块和解八皇后问题