n皇后问题-分支限界法_第1页
n皇后问题-分支限界法_第2页
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、

人人文库> 全部分类> 教育资料 > 中学教育

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论