《人工智能四皇后问题实验报告》由会员分享，可在线阅读，更多相关《人工智能四皇后问题实验报告（5页珍藏版）》请在金锄头文库上搜索。
1、实验4回溯法求解四皇后问题一、问题描述四皇后问题一个4X4国际象棋盘，依次放入四个皇后，条件：每行、每列及对角线上只 允许出现一枚棋子。二、回溯法搜索策略图(41) (42) (43) (44)(41) (42) (43)讨论:皇后问题回溯算法捜索图上述算法产生22次回溯，原因在于规则自然顺序排列，没考虑任何智能因素。改进算法定义对角线函数：diag(i,j)：过ij点最长的对角线长度值。规定：如果: diag(i,k) W diag(i,j)则规则排列次序为：Rik， Rij同一行四条规则中， 对角线函数值小的排在前面 如果：diag(i,k) = diag(i,j)则规则排列次 序为：Ri
2、j，Rik j V k对角线长度相等的规则按照字母排列顺序排序按照对角线怅度定义规则的排列次序为：R12 Rep R11，R1 斗Kzi，尺22尺23-31 斗,R灵,K-33R 斗R斗A 41 44(21)(24)U31(42)(43)改进右的捜索图讨论： 利用局部知识排列规则是有效的。 BACKTRACK算法对重复出现的状态没有判断，所以可能造成出现死循环。 没有对搜索深度加以限制，可能造成搜索代价太大。三、算法描述回溯法一一在约束条件下先序遍历，并在遍历过程中剪去那些不满足条件的 分支。使用回溯算法求解的问题特征，求解问题要分为若干步，且每一步都有几种 可能的选择，而且往往在某个选择不成
3、功时需要回头再试另外一种选择，如果到 达求解目标则每一步的选择构成了问题的解，如果回头到第一步且没有新的选择 则问题求解失败。在回溯策略中，也可以通过引入一些与问题相关的信息来加快搜索解的速 度。对于皇后问题来说，由于每一行、每一列和每一个对角线，都只能放一个皇 后，当一个皇后放到棋盘上后，不管它放在棋盘的什么位置，它所影响的行和列 方向上的棋盘位置是固定的，因此在行、列方面没有什么信息可以利用。但在不 同的位置，在对角线方向所影响的棋盘位置数则是不同的。可以想象，如果把一 个皇后放在棋盘的某个位置后，它所影响的棋盘位置数少，那么给以后放皇后留 下的余地就太大，找到解的可能性也大；反之留有余地
4、就小，找到解的可能性也 小。四、算法流程图五、源程序#in cludeint coun t=0;int isCorrect(i nt i,i nt j,i nt (*Q)4)int s,t;for(s=i,t=0;t4;t+)判断行if(Qst=1 &t!=j) return 0;for(t=j,s=0;s=0&t=0;s-,t-) 判断左上方 if(Qst=1) return 0;for(s=i+1,t=j-1;s=0;s+,t-) 判断左下方 if(Qst=1) return 0;for(s=i-1,t=j+1;s=0&t=0&t4;s-,t+) / 判断右下方if(Qst=1)retur
5、n 0; return 1;void Queue(i nt j,i nt(*Q)4) int i,k;if(j=4)for (i=0;i4;i+)否则返回递归结束条件得到解，在屏幕上显示for (k=0;k4;k+)prin tf(%d ,Qik); prin tf(n);prin tf(n); coun t+;for (i=0;i4;i+) if(isCorrect(i,j,Q)Qij=1;Queue(j+1,Q);Qij=0;如果Qij可以放置皇后/放置皇后递归深度优先搜索解空间树这句代码就是实现回溯到上一层int mai n()int Q44=0;Queue(O,Q);prin tf(T
6、he nu mber of the an swers are %dn ,co un t); getchar ();return 0;六、结果截图七、总结心得体会通过对四皇后问题的编程学习，我熟练掌握了回溯算法，并对搜索策略有了 更深的理解。首先将规则给出一个固定的排序，在搜索时，对当前状态（搜索开始时，当 前状态是初始状态）依次检测每一条规则，在当前状态未使用过的规则中找到第 一条可应用规则，应用于当前状态，得到的新状态重新设置为当前状态，并重复 以上搜索。如果当前状态无规则可用，或者所有规则已经被试探过仍未找到问题 的解，则将当前状态的前一个状态（即直接生成该状态的状态）设置为当前状态。 重复以上搜索，直到找到问题的解，或者试探了所有可能后仍找不到问题的解为 止。
