文档介绍：皇后控制问题解题报告陈世强2007-7-14问题描述编程任务输入输出设计思想与分析皇后的攻击范围包括: 1)同一行 2)同一列 3)同一对角线(包括两个方向)分析后可见,皇后之间互不攻击当且仅当满足下列条件: 1)每一行只能有一个皇后 2)每一列只能有一个皇后 3)任意条对角线上面只能有一个皇后一、先求一次随机皇后放置的值具体如下:1、利用拉斯维加斯算法随机在棋盘上放置m个皇后(m可取3)2、利用回溯法,放置下一个皇后,并判断已经放置的皇后是否已经控制整个棋盘来决定是否已经放置完毕。找到一个解,result=所放置的皇后数。二、重复第一步n*n次,best=min(result)算法分析与设计:若:X(j)表示一个解的空间,j表示行数,里面的值表示可以放置在的列数,抽象约束条件得到能放置一个皇后的约束条件(1)X(i)!=X(k);(2)abs(X(i)-X(k))!=abs(i-k)。应用回溯法,当可以放置皇后时就继续到下一行,不行的话就返回到第一行,重新检验要放的列数,如此反复,直到将所有解解出。其中,拉斯维加斯算法如下: voidQeeen_search(m) {lenb=n;lenc=0;while(lenb>=1){intindex=(lenb)+1; row=b[index]; lenb--; lenc=0; for(inti=1;i<=n;i++) if(A[row][i]==0) c[++lenc]=i; if(lenc>0){ index=(lenc)+1;}关键程序段lenb=n;//lenb为放置皇后的循环次数,我们可知,皇后数必定小于或者等于n个。lenc=0;//已经放置的皇后数A[n][n]:初始为0,1表示已经被控制的单元,2表示放置皇后x[i]:存放结果位置,即第i行第x[i]列bestx[i]:存放最优放置结果的皇后位置算法数据结构:算法的准确性:该算法综合了数值概率算法和拉斯维加斯算法的思想,解的准确性随重复计算的次数增加而不断提高,最终能达到精确解。但如果时间复杂度超过了O(n!),就失去了算法的意义。通过不断测试,得到循环次数=n*n对准确度和复杂度都较为满意。时间复杂度:当循环次数=n*n时,时间复杂度=O(n4)时间复杂度