没有合适的资源?快使用搜索试试~ 我知道了~
回溯法解决N皇后问题 Java代码实现
5星 · 超过95%的资源 需积分: 44 136 下载量 112 浏览量
2013-04-29
22:08:03
上传
评论 4
收藏 183KB DOC 举报
温馨提示
试读
20页
N皇后问题(n-queen problem)是一个经典的组合优化问题,也是一个使用回溯法(backtracking)的典型例子。回溯法是一种系统地搜索问题解的方法。 此文档包含算法分析、代码实现、演示程序、演示界面。
资源推荐
资源详情
资源评论
N 皇后问题
目录
1. 问题描述...........................................................................................................3
2. 算法分析...........................................................................................................3
3. 伪代码...............................................................................................................4
4. 演示程序设计...................................................................................................5
5. 演示界面...........................................................................................................5
6. 算法实现...........................................................................................................8
7. 总结...................................................................................................................19
8. 参考文献.......................................................................................................... 20
1. 问题描述:
N 皇后问题(n-queen problem)是一个经典的组合优化问题,也是一个
使用回溯法(backtracking)的典型例子。回溯法是一种系统地搜索问题解
的方法。为了实现回溯,首先需要为为问题定义一个解空间( solution
space),其至少包含问题的一个解(可能是最优解)。我们要从中找出满足
问题约束条件的解,即可行解(feasible solution)。回溯算法一次扩展一个
解,在对部分解进行扩展后,检查到目前为止的解是否为问题的一个解,
如果是,则输出;否则,检查是否可以继续扩展。如果可以,则继续扩展 ;
否则,删除最后添加的元素,尝试当前位置是否有另一元素。若没有合法
的扩展方式,则进行回溯(backtrack)。
N 皇后问题要求在一个 n×n 的棋盘上放置 n 个皇后,且使得每两个皇后
之间都不能相互攻击,即它们中的任意两个都不能位于同一行、同一列或
者同一对角线上。这次的任务就是借助 GUI 实现 N 皇后问题的动态演示。
我们设定皇后个数在四个到八个之间可选,所选编程语言为 JAVA。
2. 算法分析:
N 皇后问题是回溯法的一个经典例子,它的要求就是要找出在 n×n 的
棋盘上放置 n 个皇后并使其不能相互攻击的所有解。设 X=(x1,x2,…,xn)表
示问题的解,,其中 xi 表示第 i 皇后放在第 i 行所在的列数。由于不存在两
个皇后位于同一列上,因此 xi 互不相同。设有两个皇后分别位于棋盘( i , j )
和( k , l )处,如果两个皇后位于同一对角线上,则表明它们所在的位置应该
满足:i – j = k – l 或 i + j = k + l。综合这两个等式可得,如果两个皇后位于
同一对角线上,那么它们的位置关系一定满足| j – l | = | i – k |。这是对皇后
位置的合法性的判定,由函数 PLACE 来完成。
N-QUEEN 函数功能是求出 N 皇后问题的所有解。它在循环体中计算
xk 的值,并对每一个 xk 的值,调用 PLACE 过程测试它的合法性,即寻找
满足约束条件的 xk 的值。如果找到了一个合法的放置位置,就进一步测试
求得的(x1,x2,…,xk)是否为问题的解。如果是,就将其输出;否则,就将 k
的值增加 1 继续循环,即继续寻找下一个皇后合法的位置。如果不存在合
法的 xk 值,就将 k 的值减 1 进行回溯。
3. 伪代码:
N-QUEEN(n)
1 x[1] ← 0 //第一个皇后的列位置初始化
2 k ← 1 //当前列
3 while k > 0 do
4 x[k] ← x[k]+1 //到下一列
5 while x[k]≤n & not PLACE(k) do
6 x[k] ← x[k]+1
7 if x[k]≤n //找到一个位置
8 then if k=n //测试是否为问题的解
9 then output(X) //输出解
10 else k ← k+1 //转下一行,即给下一个皇后找位置
11 x[1] ← 0 //初始化当前皇后列取值
12 else k ← k-1 //回溯
13 return
PLACE(k)
1 i ← 1
2 while i<k do
3 if (x[i]=x[k] or abs(x[i]-x[k])=abs(i-k)) //同一列或同一对角线有
//两个皇后
4 then return (false)
5 i ← i+1
6 return(true)
4. 演示程序设计:
逐个输出所有的解
选择皇后个数 调用 N 皇后问题算法 显示解的个数
控制
功能按钮 动态演示皇后的布局
5. 演示界面
(1) 初始界面
剩余19页未读,继续阅读
资源评论
- zzxxccnngghh2014-05-18写的简单明了。。还不错
- WTT_22015-04-07为什么我没懂得怎么用呢?
- 娜_么爱你2014-05-22如果能把界面优化一下,会更棒的
- 晴一一2014-05-19对算法分析课程的学习很有帮助
- 青青河边草12345678902016-01-28不错的思路
Astro门
- 粉丝: 0
- 资源: 4
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功