n皇后问题算法设计.doc
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《n皇后问题算法设计.doc》由会员分享,可在线阅读,更多相关《n皇后问题算法设计.doc(8页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-daten皇后问题算法设计数据结构试验报告算法设计及分析 n皇后问题-回溯求解国际象棋中皇后威力很大,它可以象“车”一样沿直线上下或左右移动;也可以如同“象”那样沿着斜线移动。双方的皇后是不能在同一行或同一列或同一斜线上对持的。那么,在一张空白的国际象棋盘上最多可以放上几个皇后并且不让它们互相攻击呢?这个问题是伟大数学家高斯在十九世纪中期提出来的,并作了部分解答。高斯在棋盘上
2、放下了N个互不攻击的皇后,他还认为可能有N种不同的放法,这就是有名的“N皇后”问题。如果你动手试试,就一定会发现开头几颗皇后很容易放置,越到后来就越困难。由于我们的记忆有限,很可能在某个位置放过子后来证明不行取消了,但是以后又重新放上子去试探,这样就会不断地走弯路,花费大量的精力。因此,必须找到一个简易有效、有条不紊的法则才行。回溯法的基本思想:对于用回溯法求解的问题,首先要将问题进行适当的转化,得出状态空间树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树,枚举每种可能的解的情况;从而得出结果。在深度优先搜索的过程中,不断的将每个解(并不一定是完整的,事实上这也就是构造约束
3、函数的意义所在)与约束函数进行对照从而删除一些不可能的解,这样就不必继续把解的剩余部分列出从而节省部分时间。不妨以8皇后为例,设8皇后为xi,她们分别在第i行(i=1,2,3,4,5,6,7,8),这样问题的解空间就是一个8个皇后所在列的序号,为n元一维向量(x1,x2,x3,x4,x5,x6,x7,x8),搜索空间是1xi8(i=1,2,3,4,5,6,7,8),共88个状态。约束条件是8个点(1,x1),(2,x2),(3,x3),(4,x4),(5,x5),(6,x6),(7,x7),(8,x8)不在同一列和同一对角线上。虽然问题共有88个状态,但算法不会真正地搜索这么多的状态,因为回溯
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 皇后 问题 算法 设计
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内