《n皇后问题-分支限界法》由会员分享，可在线阅读，更多相关《n皇后问题-分支限界法（3页珍藏版）》请在金锄头文库上搜索。
1、一、 问题11、 问题描述一、N皇后问题在N*N的棋盘上放置彼此不受攻击的N个皇后。按照国际象棋的规则，皇后可以攻击与之处于同一行或同一列或同一斜线上的棋子。N皇后的问题等价于在N*N大小的棋盘中放置N个皇后，任何2个皇后都不放在同一行或同一列或同一斜线上。使用队列式分支限界法，求出N个皇后的一种放置方案。2、 算法设计思想分支限界法解向量：因为皇后不能同行或同列，所以我们可以用这样一个解向量来表示问题的解Xx1,x2xn x=1,2,3n;表示1n行皇后位于的列数解空间：因为皇后不能同行同列，因此解空间为排列树，使用广度优先搜索的方式搜索整棵树剪枝函数：判断新摆放的皇后是否在已经摆放的皇后的
2、斜线上3、 算法过程描述第一行第一列放置皇后，这个节点成为拓展节点，产生n-1个活结点，加入队列，第一行第二列到第n列分别产生n-1个活结点，加入队列，从队列取出第一个活结点，即第二行第二列，不满足剪枝函数的要求，除去这个节点，队列中的节点依次取出，满足剪枝函数的节点成为拓展节点产生活结点并加入队列，当成功进行到叶子节点时，就能得到问题的一个解，队列为空时，就得到了所有解4、 算法实现及运行结果#include#includeusing namespace std;bool isOK(int n, int pieces) /剪枝函数 /判断当前状态是否合理，即皇后会不会互相攻击 for (in
3、t i = 1; i = n-1; i+) for (int j = i + 1; j n) for (int i = 1; i = n; i+) for (int j = 1; j piecesi; j+) cout - ; cout piecesi ; for (int j = piecesi + 1; j = n; j+) cout - ; cout endl; cout endl; else for (int i = t; i n; int *pieces = new intn + 1; for (int i = 1; i = n; i+) piecesi = i; nQueen(n, 1, pieces); cout OK endl; system(pause);5、 算法复杂度分析及算法改进子集树O(nn)*剪枝函数(包括判断行列和斜线)O(n)=O(nn+1)
