四皇后问题实验报告.pdf
人工智能四皇后问题 一、问题描述 四皇后问题 一个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 棋盘中共有四行,所以共有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 同一行四条规那么中,对角线函数值小的排在前面 如果:diag(i,k)diag(i,j)那么规那么排列次序为:Rij,Rik j k 对角线长度相等的规那么按照字母排列顺序排序 讨论:利用局部知识排列规那么是有效的。BACKTRACK算法对重复出现的状态没有判断,所以可能造成出现死循环。没有对搜索深度加以限制,可能造成搜索代价太大。三、算法描述 回溯法在约束条件下先序遍历,并在遍历过程中剪去那些不满足条件的分支。使用回溯算法求解的问题特征,求解问题要分为假设干步,且每一步都有几种可能的选择,而且往往在某个选择不成功时需要回头再试另外一种选择,如果到达求解目标那么每一步的选择构成了问题的解,如果回头到第一步且没有新的选择那么问题求解失败。在回溯策略中,也可以通过引入一些与问题相关的信息来加快搜索解的速度。对于皇后问题来说,由于每一行、每一列和每一个对角线,都只能放一个皇后,当一个皇后放到棋盘上后,不管它放在棋盘的什么位置,它所影响的行和列方向上的棋盘位置是固定的,因此在行、列方面没有什么信息可以利用。但在不同的位置,在对角线方向所影响的棋盘位置数那么是不同的。可以想象,如果把一个皇后放在棋盘的某个位置后,它所影响的棋盘位置数少,那么给以后放皇后留下的余地就太大,找到解的可能性也大;反之留有余地就小,找到解的可能性也小。四、算法流程图 五、源程序#include#define N 4 char boardNN;int t;int colN;/存储第i行对应的列的值,这样的(i,j)值满足当前棋盘上的皇后不能互相攻击。int safetyPlace(int x,int y)/(x,y)位置是否平安 int i,j;for(i=0;ix;i+)j=coli;if(x=i|y=j)return 0;if(x-y=i-j|x+y=i+j)/判断左右对角线 return 0;return 1;void get_position(int i)/处在第i行时状态 int w,j;char a1=3;if(i=N)/输出棋盘 for(w=0;wN;w+)for(j=0;jN;j+)if(boardwj=001)printf(%c ,boardwj);else printf(%c,a0);printf(%c,boardwj);printf(n);printf(n);printf(-n);t+;else int u;for(u=0;uN;u+)if(safetyPlace(i,u)=1)coli=u;/记录下第i行可行的列的位置 boardiu=001;/放置皇后 get_position(i+1);/转换到下一个状态,即下一行 coli=0;/回溯到当前状态,重置列和棋盘的值 boardiu=0;main()printf(%c是皇后!nn,001);get_position(0);printf(一共有%d种方法!n,t);六、结果截图 七、总结心得体会 通过对四皇后问题的编程学习,让我对搜索策略更深层次的理解,尤其能比拟熟练掌握回溯策略首先将规那么给出一个固定的排序,在搜索时,对当前状态搜索开始时,当前状态是初始状态依次检测每一条规那么,在当前状态未使用过的规那么中找到第一条可应用规那么,应用于当前状态,得到的新状态重新设置为当前状态,并重复以上搜索。如果当前状态无规那么可用,或者所有规那么已经被试探过仍未找到问题的解,那么将当前状态的前一个状态 即直接生成该状态的状态设置为当前状态。重复以上搜索,直到找到问题的解,或者试探了所有可能后仍找不到问题的解为止。同时,在整个编程学习过程中,使得我对人工智能感到越来越多的趣味性 例如四皇后问题上升到n皇后如何求解,更引起我对学习人工智能这门课程的积极性。