实验报告:回溯法求解N皇后问题(Java实现).pdf
![资源得分’ 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皇后问题(Java实现).pdf》由会员分享,可在线阅读,更多相关《实验报告:回溯法求解N皇后问题(Java实现).pdf(2页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、实验报告实验报告一、实验名称:一、实验名称:回溯法求解回溯法求解 N N 皇后问题(皇后问题(JavaJava 实现)实现)二、学习知识:二、学习知识:回溯法:回溯法:也称为试探法,它并不考虑问题规模的大小,而是从问题的最明显的最小规也称为试探法,它并不考虑问题规模的大小,而是从问题的最明显的最小规模开始逐步求解出可能的答案,并以此慢慢地扩大问题规模,迭代地逼近最终问题的解。模开始逐步求解出可能的答案,并以此慢慢地扩大问题规模,迭代地逼近最终问题的解。这种迭代类似于穷举并且是试探性的,因为当目前的可能答案被测试出不可能可以获得最这种迭代类似于穷举并且是试探性的,因为当目前的可能答案被测试出不可
2、能可以获得最终解时,则撤销当前的这一步求解过程,回溯到上一步寻找其他求解路径。终解时,则撤销当前的这一步求解过程,回溯到上一步寻找其他求解路径。为了能够撤销当前的求解过程,必须保存上一步以来的求解路径,这一点相当重要。为了能够撤销当前的求解过程,必须保存上一步以来的求解路径,这一点相当重要。三、问题描述三、问题描述N N 皇后问题:皇后问题:在一个在一个 N*N N*N 的国际象棋棋盘中,怎样放置的国际象棋棋盘中,怎样放置 N N 个皇后才能使个皇后才能使 N N 个皇后之间个皇后之间不会互相有威胁而共同存在于棋局中,即在不会互相有威胁而共同存在于棋局中,即在 N*N N*N 个格子的棋盘中没
3、有任何两个皇后是在个格子的棋盘中没有任何两个皇后是在同一行、同一列、同一斜线上。同一行、同一列、同一斜线上。深度优先遍历的典型案例。深度优先遍历的典型案例。四、求解思路四、求解思路1 1、求解思路:、求解思路:最容易想到的方法就是有序地从第最容易想到的方法就是有序地从第 1 1 列的第列的第 1 1 行开始,尝试放上一个行开始,尝试放上一个皇后,然后再尝试第皇后,然后再尝试第 2 2 列的第几行能够放上一个皇后,如果第列的第几行能够放上一个皇后,如果第 2 2 列也放置成功,那么就列也放置成功,那么就继续放置第继续放置第 3 3 列,如果此时第列,如果此时第3 3 列没有一行可以放置一个皇后,
4、说明目前为止的尝试是列没有一行可以放置一个皇后,说明目前为止的尝试是无效的(即不可能得到最终解),那么此时就应该回溯到上一步(即第无效的(即不可能得到最终解),那么此时就应该回溯到上一步(即第 2 2 步),将上一步步),将上一步(第(第 2 2 步)所放置的皇后的位置再重新取走放在另一个符合要求的地方如此尝试性地遍步)所放置的皇后的位置再重新取走放在另一个符合要求的地方如此尝试性地遍历加上回溯,就可以慢慢地逼近最终解了。历加上回溯,就可以慢慢地逼近最终解了。2 2、需要解决的问题:、需要解决的问题:如何表示一个如何表示一个 N*N N*N 方格棋盘能够更有效怎样测试当前所走的方格棋盘能够更有
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 报告 回溯 求解 皇后 问题 Java 实现
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内