运用回溯法求解把皇后问题

《运用回溯法求解把皇后问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法分析与设计实验报告第6次实验八皇后问题姓名杨玉茹学号201508010325班级计科1503时间5.12下午地点软件大楼109实验名称运用冋溯法求解把皇后问题实验目的通过上机实验，要求掌握冋溯法，解决皇后算法的问题描述、算法设计思想、程序设计。实验原理运用回溯法来解决这个问题：1.首先需要用一个量来表示这个皇后的位置，i来表示皇后所在行的位置，X[i]来表示皇后所在的列，根据实验题目的要求，不能够让皇后之间在同一行或者同一列，或者同一对角线上，同一行和同一列这是一个显示约束条件，但是同一对角线上这个

2、是一个隐式约束条件，应该将这个转化为一个显示的约束条件，所以根据分析，同一个对角线上的两个元素的坐标只差相等，也就是1,j均表示皇后所在的列，X[i]与X[j]均表示皇后所在的列，那么2.根据约朿条件以及回溯法的规则來查找每一个皇后的位置，如果每一个皇后都找到正确的位置，那么方案数目就加1；实验步骤1.用一个Bool函数来描述皇后之间位置的约束条件；Queen函数就是来依次判断每一个皇后的位置，当i<=n的吋候，X[i]二1,2,3,...n—共n个子节点，对当前的每一个子节点用约朿函数去检查每一个儿子

3、节点是否符合，并且运用深度优先的方法去搜索子树，或者剪去不可行的子树，然后再回溯到第一个皇后查找还有没有其他的方案；boolplace(intt)ffor(inti二1;i〈t;i++)关键代码1if((abs(i-t)==abs(x[t]-x[i]))

4、

5、(x[t]二二x[i]))returnfalse;//returntrue;lreturntrue;}voidqueen()/iinti;x[l]二0;intk=l;while(k>0){x[k]+二1;while((x[k]<=N)&&!place

6、(k))x[k]+=l;if(x[k]〈=N){if(k==N){sum++;}else{k++；x[k]=0;}}else{k-;//回溯测试结果实验心得在这次实验当中最重要的就是利用回溯法去解决这个问题，当然最开始还应当将隐约束问题转换为显约束问题，即同一个对角线上的两个皇后也是不可行的，因此应该观察对角线上的元素之1'可的特征，最后即可得到这个约朿函数，再者就是运用回溯法当中的排列树去解决，将每一行的皇后看成树的每一层，这样深度搜索的方式搜索，然后再回溯，最后得到方案，这里最重要的就是牢牢把握住回

7、溯法的思想。实验得分助教签名算法分析与设计实验报告第6次实验子集合问题姓名杨玉茹时间5.12下午学号201508010325班级计科1503地点软件大楼109实验名称运用回溯法解决子集合问题实验目的通过上机实验，要求掌握回溯算法的问题描述、算法设计思想、程序设计。运用非递归冋溯法来解答子集合的问题的时候，首先分析出来，可以运用子集树的方法来解决这个问题，那么根据子集树的概念，在本题当中，我们只需要找出一个符合问题的方案即可，所以假若第一次就找到，那么我们就返回，如果一直到达了叶子节点也没有找到，那么我们

8、就再冋溯回去接着找。实验原理1h2,31,2b312,323①将这个函数声明为一个bool函数，然后只要相加的结果等于目标值，那么就返回true;实验步骤②如果所得的结果大于目标值，那么我们就朝右子树搜索，如果所得结果小于目标值，那么我们就朝左子树搜索，如果到了叶子节点，依然没有找到我们想要的节点，那么就再回溯回去；③只要还有元素没有判断就继续选择。直到第n个元素，如果第n个元素判断完还没有找到解的话，就回溯到上一次选择的那个点，将其从集合里面删除并从它后一个点继续重复前面的操作。如果冋溯的时候回溯到了

9、笫一个元素Z前的话呢，表示这个时候要么所有元素都加入到集合都不够，或者是所有的情况都找过了还是没有解决方案，这个时候返回无解。关键代码boolBacktrack(intt){if(sum==c){returntrue;}if(t>n){returnfalse;}r-=data[t];if(sum+data[t]<=c){x[t]=l;//t++;sum=sum+data[t];if(Backtrack(t+1))returntrue;sum-=data[t];}if(sum+r>=c){x[t]二0;〃

10、t++;if(Backtrack(t+1))returntrue;}r+=data[t];returnfalse;}测试结果实验心得这次实验主要学会的是运用非递归冋溯法进行解题，这道题和之前所学的例题稍微有些不同，这道题不是求最优解，而是寻找一个目标值，如果这个目标值存在，那么就返回true,否则就false,所以运用子集树进行深度优先搜索，然后如果没有得到理想值，再冋溯，通过这道题，以后做其他的题也可以进行类比分析。实验得分助教签名算法分