回溯法实验(n皇后问题)(迭代法).doc

. . 算法分析与设计实验报告 第 三 次附加实验 姓名 学号 班级 时间 12.26上午 地点 工训楼309 实验名称 回溯法实验(n皇后问题)（迭代法） 实验目的 掌握回溯法求解问题的思想 学会利用其原理求解相关问题 实验原理 用n元组x[1:n]表示n后问题的解。其中，x[i]表示皇后i放在棋盘的第i行的第x[i]列。由于不允许将2个皇后放在同一列上，所以解向量中的x[i]互不相同。2个皇后不能放在同一斜线上是问题的隐形约束。 用回溯法解n后问题时，用完全n叉树表示解空间。可行性约束Place剪出不满足行、列和斜线约束的子树。 递归函数Backtrack(1)实现对整个解空间的回溯有哪些信誉好的足球投注网站。 Backtrack(i)有哪些信誉好的足球投注网站解空间中第i层子树。类Queen的数据成员记录解空间中结点信息，以减少传给Backtrack的参数。Sum记录当前已找到的可行方案数。 实验步骤 数组法： （1）根据n皇后问题，可以把其设想为一个数组； （2）根据n皇后的规则，可以设想为数组上同一直线，横线，斜线的数字都不能相同，由此可以得到判断条件； （3）根据判断条件之后，建立回溯点，即可解决问题。 堆栈法： 检索当前行是否可以放置一个皇后； 利用检索过程，通过递归的方式，来确定每一个皇后的位置。 关键代码 递归回溯： void Queen::Backtrack(int t) { if(tn) { sum++; /*for(int i=1;i=n;i++) //输出皇后排列的解 { coutx[i] ; } coutendl;*/ } else {//回溯探索第i行的每一列是否有元素满足要求 for(int i=1;i=n;i++) { x[t]=i; if(Place(t)) { Backtrack(t+1); } } } } 迭代回溯： void Queen::Backtrack() //迭代法实现回溯函数 { x[1] = 0; int k = 1; while(k0) { x[k] += 1; //先将皇后放在第一列的位置上 while((x[k]=n)!(Place(k))) //寻找能够放置皇后的位置 { x[k] += 1; } if(x[k]=n) //找到位置 { if(k == n) //如果寻找结束输出结果 { /*for (int i=1;i=n;i++) { coutx[i] ; } coutendl; */ sum++; } else //没有结束则找下一行 { k++; x[k]=0; } } else //没有找到合适的位置则回溯 { k--; } } } 测试结果 较小皇后个数结果： 递归法较大的皇后个数： 迭代法较大的皇后个数： 输入较大的皇后个数15： 输入皇后个数是16时： 当输入的皇后个数是20时： 运行了一个上午都没有出结果，所以果断放弃了。 实验分析 在上述的实验结果中: (1) 我们可以观察到输出皇后排序结果与不输出结果，只输出解的个数是有差距的。 (2) 而且通过对比递归与迭代两种不同的实现方法，发现情况是基本相同的，时间上并没有什么太大的差距，但是相对的迭代会稍微快一点点。 (3) 然后对比输入较大的皇后个数之后，仅仅一个皇后之差就会使得时间上相差很大，如15个皇后的时候所用的时间是280.102，而当皇后个数是16时，所用的时间是2153.463，从而我们可以看出n皇后问题的时间复杂度是指数级的，从而n皇后问题确实是NP问题。 实验心得 Dijkstra算法在之前的数据结构中就学过，在当时只是学过这种思想，并没有去深思这种思想其背后到底是一种怎样的思想在里面。后来经过本门课的学习，对于贪心算法有了更深刻的了解，也知道了如何利用贪心算法去解决问题。最开心的是经过一定时间的练习，我的编程能力有了一定的提高，之前看见就很头疼的问题，现在也能静下心来去