四皇后问题实验报告.doc

---------------------------------作者:_____________-----------------------------日期::_____________四皇后问题实验报告---------------------------------------------------------------------编制:---------------------------------------------------------------------日期:人工智能——四皇后问题问题描述四皇后问题一个4×4国际象棋盘,依次放入四个皇后,条件:每行、每列及对角线上只允许出现一枚棋子。设:DATA=L(表)x∈Lx∈﹛ij﹜1≤i,j≤4其中:ij表示棋子所在行列如:24表示第二行第四列有一枚棋子∵棋盘上可放入的棋子数为0~4个∴L表中的元素数为0~4个,即LengthL=0~4,如图A﹛12,24,31,43﹜定义规则:if1≤i≤4andLengthDATA=i-1thenAPPEND(DATA(ij))1≤j≤4①对于任一行i,1≤j≤4表明每行有四条规则。比如第一行:R11,R12,R13,R14②棋盘中共有四行,所以共有16条规则。即:R11,R12,R13,R14R21,R22,R23,R24R31,R32,R33,R34R41,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,Rikj<k对角线长度相等的规则按照字母排列顺序排序讨论:①利用局部知识排列规则是有效的。②BACKTRACK算法对重复出现的状态没有判断,所以可能造成出现死循环。③没有对搜索深度加以限制,可能造成搜索代价太大。三、算法描述回溯法——在约束条件下先序遍历,并在遍历过程中剪去那些不满足条件的分支。使用回溯算法求解的问题特征,求解问题要分为若干步,且每一步都有几种可能的选择,而且往往在某个选择不成功时需要回头再试另外一种选择,如果到达求解目标则每一步的选择构成了问题的解,如果回头到第一步且没有新的选择则问题求解失败。在回溯策略中,也可以通过引入一些与问题相关的信息来加快搜索解的速度。对于皇后问题来说,由于每一行、每一列和每一个对角线,都只能放一个皇后,当一个皇后放到棋盘上后,不管它放在棋盘的什么位置,它所影响的行和列方向上的棋盘位置是固定的,因此在行、列方面没有什么信息可以利用。但在不同的位置,在对角线方向所影响的棋盘位置数则是不同的。可以想象,如果把一个皇后放在棋盘的某个位置后,它所影响的棋盘位置数少,那么给以后放皇后留下的余地就太大,找到解的可能性也大;反之留有余地就小,找到解的可能性也小。四、算法流程图 五、源程序#include<>#defineN4char