回溯法及其应用.doc

八皇后问题的基本策略及其应用 郭洋洋 王刚 李晴 孙佳 （陕西师范大学计算机科学学院09级计算机科学与技术，西安，710062）摘要：针对八皇后问题，本文采用回溯法，给出递归与非递归两种算法的设计与分析，并通过实验验证两种算法的性能，得出最佳的算法。关键词：八皇后；回溯法；递归算法；非递归算法 The Basic Algorithm Strategy For Eight Queens And Its Application Guo Yangyang,Wang Gang,Li Qing, Sun Jia (School of Computer Science ,Shanxi Normal University ,Xian ,710062 )Abstract: Aiming at the problem of Eight Queens,this paper gives Backtracking , and Recursive algorithm and Non-recursive algorithm , and show the design and analysis of the two kinds of algorithms,and through the experiment ,verified the performance of them,getting the most suitable algorithm.Keywords: Eight Queens; Backtracking; Recursive; Non-Recursive1 引言 八皇后问题由19 世纪著名的数学家高斯在1850 年提出:在8 8 格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法.回溯算法是尝试搜索算法中最为基本的一种算法，其采用了一种“走不通就调头”的思想，作为其控制结构1。回溯法在用来求问题的所有解时，要回溯到根，且根节点的所有可行的子树都已被搜索遍才结束。而回溯法在用来求解问题任一解时，只要搜索到问题的一个解就可以结束。这就是以深度优先的方式系统的搜索问题解的回溯法，它适用于解决一些类似n皇后问题等就切方案问题，也可以解决一些最优化问题。2 问题描述与模型八皇后问题：在8 8 格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法.例如图一所示： 图一 8皇后问题模型建立：不妨设8个皇后为xi ，她们分别在第i行（i=1,2,3,8）,这样问题的解空间，就是一个8皇后所在列的序号，为n元一维向量（x1,x2,x3,x4,x5,x6,x7,x8）,搜索空间是1xi8（i=1,2,3,8）,共88个状态。约束条件是8个点（1，x1），（2，x2），（3，x3），（4，x4），（5，x5），（6，x6），（7，x7），（8，x8），不在同一列和同一对角线上。3 算法设计下面通过枚举法、非递归算法、递归算法来求解问题。3.1 枚举法算法设计：运用枚举法解决此问题是通过八重循环，按照深度优先思想，从第一个皇后开始搜索，确定第一个位置后，在搜索第二个位置；每进一步检查是否满足约束条件，不满足时，用continue回溯到上一个皇后继续寻找；满足约束条件时，开始下一个皇后的搜索；直到找出问题的解。显然，问题的搜索空间有88个状态。约束条件有有三个1：（）不在同一列的表达式为：xixj（）不在同一主对角线上的表达式为：xi-ixj-j;（）不在同一负对角线上的表达式为：xi+ixj+j;以上条件和可以合并为一个“不在同一对角线上”的约束条件，表达式为： abs(xi-xj)abs(i-j)(abs()取绝对值)。算法伪代码如下：main() for ( a1=1; a1=8;a1=a1+1)for(a2=1;a2=8;a2=a2+1) if (check(a,2)= =0) continue; for (a3=1;a3=8;a3=a3+1) if (check(a,3)= =0) continue; for (a4=1;a4=8;a4=a4+1) if (check(a,4)= =0) continue; for (a5=1;a5=8;a5=a5+1) if (check(a,5)= =0) continue; for (a6=1;a6=8;a6=a6+1) if (check(a,6)= =0) continue; for (a7=1;a7=8;a7=a7+1) if (check(a,7)= =0) continue; for (a8=1;a8=8;a8=a8+1) if (check(a,8)= =0) continue; else for (int i=1;i=8;i+) printf (ai); check( a,i) 功能： 将第i个皇后和前i-1个皇后比较，如果满足上述三个约束条件，则继续寻找第i+1个皇后的位置；否则，继续查找第i个皇后；若找不到则返回0；否则返回1.算法分析1： 表面上看，这个算法的时间复杂度为88，其实算法在check（）函数返回0时，continue返回，便不再执行其后的皇后查找工作，所以其时间复杂度并没有88。当然，我们可以将算法稍微改变后，它的复杂度便立即为88。在算法中：将前七个“if (check(a,i)=0) continue;” 去掉，只留下最后一个，同时将check函数改为如下：_check(a,n) int i,j; for (i=2;i=n;i+) for (j=1;j0(有路可走)and(未达到目标) if(in) 搜索到一个解，输出； else ai第一个可能的值； while(ai在不满足约束条件 and 在搜索空间内) ai下一个可能的值； if(ai在搜索空间内) 标示占用资源；i=i+1; else 清理现场； i=i-1; 算法伪代码如下： backdate (int n) while (k0) ak=ak+1; while(ak=n)&(check(k)=0) / 为第i个皇后搜索位置 ak=ak+1; if(akn) 输出结果； else for(j=下界；j=上界；j+) if(f(j) ai=j; . try(i+1); 回溯前的清理工作； 算法伪代码如下：main ( ) input (n); try (1); try (int i) for (int j=1;j=n;j+) if (bj=0)&(ci+j=0)&(di-j+n=0)/ 判断位置是否冲突 ai=j; bj=1; ci+j=1; di-j+n=1; if (in) try (i+1); /皇后没有摆完，继续下一个皇后 else output ( ); bj=0； ci+j=0； di-j+n=0； 算法说明： 递归算法的回溯是有函数调用结束自动完成的，不需要指出回溯点，但需要清理现场-将当前点占用的位置释放，也就是算法的最后三条语句。4 算法设计过程通过以上三种算法来解决八皇后问题，可以看出回溯法的基本思路，以下是回溯法的设计过程：（）确定问题的解空间；医用回溯法解决问题时，首先应该明确定义问题的解空间，问题的解空间至少包含问题的一个最优解；（）确定节点的扩展规则；如每个皇后在一行中得不同位置移动，而象棋中的象只能飞“田”；（）搜索解空间； 例如图二所示： 图二 4皇后问题回溯法应该从开始节点出发，以深度优先的方式搜索整个解空间。这个开始节点就是一个活结点，同时也成为当前的扩展节点。在当前的扩展节点处，搜索向纵深方向移至一个新的节点。这个新的节点再次成为新的活结点，并成为当前的可扩展节点。如果在当前的扩展节点处不能再向纵深方向移动，则当前扩展节点就成为死节点。此时，应该回溯到上一个节点。5 性能分析以下通过对8、10、12皇后的问题对算法性能分析：如表一所示，记枚举法、非递归算法、递归算法三者在8、10、12三种状态下的平均时间分别为：A1、A2、A3.算法次数 8皇后 10皇后 12皇后 平均时间A1A2A3枚举法 1 2 3 4 5非递归算法 11.6091.906 2 1.4372.234 31.391.859 41.392.093 51.4841.937递归算法 11.1252.28114.859 2 1.252.62515.078 31.2032.29615.125 41.1251.90614.843 51.1562.014.656 表一 三种算法的性能分析 （时间：s）6 结束语 回溯法在诸多方面都有应用，如排列问题，0-1背包问