四皇后问题实验报告.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)
《四皇后问题实验报告.pdf》由会员分享,可在线阅读,更多相关《四皇后问题实验报告.pdf(6页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、 人工智能四皇后问题 一、问题描述 四皇后问题 一个44国际象棋盘,依次放入四个皇后,条件:每行、每列及对角线上只允许出现一枚棋子。设:DATA=L表 xL x i j 1 i,j 4 其中:i j 表示棋子所在行列 如:24 表示第二行第四列有一枚棋子 棋盘上可放入的棋子数为0 4 个 L表中的元素数为0 4 个,即 Length L=0 4,如图A 12,24,31,43 定义规那么:if 1 i 4 and Length DATA=i 1 then APPEND(DATA(ij)1 j 4 对于任一行i,1 j 4 说明每行有四条规那么。比方第一行:R11,R12,R13,R14 棋盘中
2、共有四行,所以共有16条规那么。即:R11,R12,R13,R14 R21,R22,R23,R24 R31,R32,R33,R34 R41,R42,R43,R44 16条规那么中,哪些是当前可用规那么,取决于DATA的长度,即:DATA中的元素个数。换言之,每次只能将一个棋子放在当前行的下一行。二、回溯法搜索策略图 讨论:上述算法产生22次回溯,原因在于规那么自然顺序排列,没考虑任何智能因素。改良算法 定义对角线函数:diag(i,j):过ij点最长的对角线长度值。规定:如果:diag(i,k)diag(i,j)那么规那么排列次序为:Rik,Rij 同一行四条规那么中,对角线函数值小的排在前面
3、 如果:diag(i,k)diag(i,j)那么规那么排列次序为:Rij,Rik j k 对角线长度相等的规那么按照字母排列顺序排序 讨论:利用局部知识排列规那么是有效的。BACKTRACK算法对重复出现的状态没有判断,所以可能造成出现死循环。没有对搜索深度加以限制,可能造成搜索代价太大。三、算法描述 回溯法在约束条件下先序遍历,并在遍历过程中剪去那些不满足条件的分支。使用回溯算法求解的问题特征,求解问题要分为假设干步,且每一步都有几种可能的选择,而且往往在某个选择不成功时需要回头再试另外一种选择,如果到达求解目标那么每一步的选择构成了问题的解,如果回头到第一步且没有新的选择那么问题求解失败。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 皇后 问题 实验 报告
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内