下次自动登录
现在的位置:
& 综合 & 正文
八皇后问题各种解法分析
最近学习分析，突然对八皇后问题十分感兴趣，下面是我研究一段时间后的思想汇总。希望能够引起各位算法爱好者的共鸣，当然如果有什么遗漏之处希望互相交流。
一：回溯法
这种算法想必学习计算机算法分析与设计的人都应该知道，说白了，这个算法就是一个搜索算法，对一棵树进行深度优先搜索，但是在搜索的过程中具有自动终止返回上一层继续往下搜索的能力，这个算法其实就是一个搜索树，对部分节点进行了剪枝是一种可行的算法，对八皇后这样皇后数较少的问题还能够解决，如果皇后数再大一点就无能为力了，当然我们通过这学习了一种算法。至于具体算法怎么实现在此就不一一详述了，因为大部分网站都有具体的源码，核心思想也基本相同，只是编程应用的数据结构有所不同而已。
二：概率算法
这种算法网络上很少有，在此我只是提供一点思路供爱好者探讨。
基本思想：首先应用随机函数在一个8*8的矩阵中放入合适的4个皇后（即一半的皇后）然后再应用之前的回溯的方法进行搜索，随后循环这样的一个过程，当时间容许的情况下，很快就可以找到满足所有的解。当然这种方法对回溯法只是进行了一点点的改动，但时间复杂度上将有很大的提高。算法源码在此也不予提供，有兴趣的可以与我联系。
三：A*算法
这种算法原本是人工智能里求解搜索问题的解法，但八皇后问题也同样是一个搜索问题，因此可以应用这种方法来进行求解。这里关于A*算法的定义以及一些概念就不提供了，大家可以上网进行搜索，网上有很多关于A*算法的详细介绍。如果有兴趣的朋友可以借阅一本人工智能的书籍上面有关于A*算法求解八皇后问题的详细解答过程，在此我就不多说了，我只是提供一种学习的思路。
四：广度优先搜索
这个是和回溯法搜索相反的一种方法，大家如果学过数据结构的应该知道，图的搜索算法有两种，一种是深度优先搜索，二种是广度优先搜索。而前面的回溯算法回归到图搜索的本质后，发现其实是深度优先搜索，因此必定会有广度优先搜索解决八皇后问题，由于应用广度优先搜索解决八皇后问题比应用深度优先搜索其空间复杂度要高很多，所以很少有人去使用这种方法，但是这里我们是来学习算法的，这种算法在此不适合，不一定在其他的问题中就不适合了，有兴趣的朋友可以参考任何一本数据结构的数据上面都有关于广度优先搜索的应用。
总结：上面我对八皇后问题的这种算法只是起了一点抛砖引玉的作用，没有深入讲解，一是自己时间有限，二是自己研究的也不够彻底，在此只能提供一点点解题思路希望大家看到后可以有一点前进的方向，最后说一下其实八皇后问题还可以应用一些更加高级的算法进行求解，例如遗传算法，蚁群算法，粒子群算法等等，这些算法我还在研究中希望有兴趣的朋友可以和我交流。以上都仅为个人观点，如果错误之处请指正本人不胜感激。
【上篇】【下篇】悲观的头脑。乐观的意志，
算法学习之暴力求解
暴力求解(brute force)
Brute force is a straightforward approach to solving a problem, usually directly based on the problem statement and definitions of the concepts involved.
暴力求解即根据问题的描述和定义直接求解,不使用一些特殊的算法.
排序问题的应用
选择排序将数组分为排序与未排序两个部分,每次将从未排序部分取出最小的值,插入排序部分的最后,最终未排序部分消失,排序完成.
冒泡排序也是将数组分为排序与未排序两个部分,每次从未排序部分的第一个数开始,与后一个比较,如果大于它两两交换,否则从第二个开始继续与后一个比较.最终未排序部分的最后一个数即最大的数.循环n次即完成排序.
搜索问题的应用
简单粗暴,一个个比较.
字符串匹配
同样道理,逐个比较.
最近点问题
把所有两点距离求出来,然后选择最小值.
用循序渐进的方式求取给定点集的凸包，首先把最初输入的3个不共线(Non-collinear)的点按 逆时针方向构成一个三角形，这就是这3点的凸包。接着便会考察第4点，看看这个点是否位于前述三 角形之内或三角形的边上。若是，则这第4点并非凸包上的点，前述三角形保持不变。若否，则把这前述的三角 形扩大为一个四边形，并把不适用的边擦去。这个四边形便是这首4点的凸包。接着程序又会考察第5点，如此 类推，直至所有点均已被考察为止.由于每次都要检查所有之前的点，时间复杂度为O(n^2).
以下3个问题都可以用穷举的方法暴力求解,把所有可能都试一遍.然而实际上由于可能情况太多,一般不会使用穷举的方法.数据量小的情况可以考虑使用.每个问题都有不少更优的算法.
旅行推销员问题(Travelling Salesman Problem)
有n个城市，一个推销员要从其中某一个城市出发，唯一走遍所有的城市，再回到他出发的城市，求最短的路线。也即求一个最短的哈密顿回路。
背包问题(knapsack problem)
给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
任务分配问题(assignment problem)
线性任务分配问题：P是二元组(a, b)的集合，其中a和b分别是集合A和B中的元素。C是某一函数，并满足特定约束条件，例如：A的每一个元素必须在P中出现一次，或者B的每一个元素必须在P中出现一次，或者以上二者都必须满足。线性任务分配问题的目标就是最大化或者最小化C(a, b)之和。
暴力求解法可以说毫无技巧,但是简单容易实现.一般情况是不会用到的,但是在特定情况下有奇效.可以说当人们解决某个问题的时候用暴力求解应该是第一直觉,然而这太简单并不能体现自己的能力,就会开始寻找更快的方法.我的理解是更优的算法应该是基于暴力求解法之上的.例如说背包问题,同样样遍历所有情况,动态规划巧妙的利用前面的尝试过的数据,减少了工作量.但本质上还是要试遍所有可能,只是试的少了.
没有更多推荐了，有事可以加QQ我们可以 一起提高哦！
n皇后问的三种解答方式
不用多说直接上代码#include&iostream&
#include&math.h&
#include&conio.h&
#include&stdlib.h&
/************************************************/
/*以地图的形式来打印出皇后的位置*/
/************************************************/
void display(int queenArr[],int nLen,int nSolution) {
printf("******************QueenDisplay**** %d*******************\n",nSolution);
for(int i = 0; i&nL i++) {
if( -1==queenArr[i]) {
for(int j = 0; j &nL j++) {
printf("%c",65);
printf("\n");
//打印皇后的前面的空余部分
for(int j = 0; j&queenArr[i]; j++) {
printf("%c",65);
printf("%c",66);
//打印后面的空格
for(int j = 0; j&nLen-queenArr[i]-1; j++) {
printf("%c",65);
printf("\n");
//判断方案是否可行
bool isClash(int queenArr[]) {
for(int i = 0; i&8; i++) {
for(int j = 0; j&i-1; j++) {
if(queenArr[i] == queenArr[j]) {
//说明在同一列
if(abs(queenArr[i] - queenArr[j])==abs(i-j)) {
//蛮力法实现8*8*8*8*8*8*8*8种方案拿出来分别来验证
void enumQueenPostion(int queenArr[],int &nSolution) {
//第一个皇后按照顺序从第一列开始往后移动
for( queenArr[0] = 0; queenArr[0]&8; queenArr[0]++) {
//第二个皇后也从第一列开始排列
for( queenArr[1] = 0; queenArr[1]&8; queenArr[1]++) {
for( queenArr[2] = 0; queenArr[2]&8; queenArr[2]++) {
for( queenArr[3] = 0; queenArr[3]&8; queenArr[3]++) {
for( queenArr[4] = 0; queenArr[4]&8; queenArr[4]++) {
for( queenArr[5] = 0; queenArr[5]&8; queenArr[5]++) {
for( queenArr[6] = 0; queenArr[6]&8; queenArr[6]++) {
for( queenArr[7] = 0; queenArr[7]&8; queenArr[7]++) {
//判断方案是否可行皇后是否打架
if(isClash(queenArr)) {
//如果不成立
nSolution++;
//如果成立
display(queenArr,8,nSolution);
//_getch();
//蛮力法的计算量是很大的算法的时间复杂度很高
利用递归函数做一个解析
//在放一个皇后在第一行的时候，放一个去掉一行
bool isClash(int queenArr[],int nRow) {
for(int nColumn = 0; nColumn&nR nColumn++) {
if(queenArr[nColumn]==queenArr[nRow]) {
if (abs(queenArr[nColumn]-queenArr[nRow])==abs(nColumn-nRow)) {
void putQueen(int queenArr[],int nRow,int nLen ,int &nSolution) {
for(int i = 0; i&nL i++) {
queenArr[nRow] =
//如果已经有冲突了，我们就忽略其他皇后
if(!isClash(queenArr,nRow)) {
if(nRow == nLen-1) {
nSolution++;
//全部已经解析OK了
display(queenArr,nLen,nSolution);
putQueen(queenArr,nRow+1,nLen,nSolution);
/*拉斯维加斯算法实现*/
int Random(int a,int b) {
return (rand()%(b-a)+a);
/*判断皇后是否冲突*/
int Place(int queenArr[],int k) {
// 测试皇后k置于第x[k]列的合法性
for(int j = 0; j & j++)
if((abs(k-j) == abs(queenArr[j]-queenArr[k])) || (queenArr[j]==queenArr[k]))
void QueensLV(int queenArr[],int n,int &nSolution) {
int i,j,count = 0;
for(i = 0; i&n;) {
j = Random(1,n);
queenArr[i] =
if(!Place(queenArr,i)) {
count = 0;
} else if(count==n) {
printf("本次运行失败\n");
for(int i = 0; i&n; i++) {
nSolution++;
display(queenArr,8,nSolution);//显示皇后的位置
int main() {
int queenArr[8] ;//每一个皇后在每一行的第一个位置，queenArr[0] = 4表示第一行的皇后在地五个位置
// for(int i = 0; i&8; i++) {
queenArr[i] = 0;
// //memset(queenArr,0,sizeof(int)*8);
// queenArr[0]=4;
// queenArr[1]=6;
// display(queenArr,8);
int nSolution = 0;
QueensLV(queenArr,8,nSolution);
//putQueen(queenArr,0,n,nSolution);
//enumQueenPostion(queenArr,nSolution);
cout&&"hello world!"&&
没有更多推荐了，【图文】蛮力法_百度文库
您的浏览器Javascript被禁用，需开启后体验完整功能，
享专业文档下载特权
&赠共享文档下载特权
&10W篇文档免费专享
&每天抽奖多种福利
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
阅读已结束，下载本文到电脑
想免费下载本文？
登录百度文库，专享文档复制特权，积分每天免费拿！
你可能喜欢Access denied | www.bkjia.com used Cloudflare to restrict access
Please enable cookies.
What happened?
The owner of this website (www.bkjia.com) has banned your access based on your browser's signature (436fc4-ua98).}