人工智能实验报告_八皇后问题

《人工智能实验报告_八皇后问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、八皇后问题八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。基本思想：在open表中保留已生成而未考察的结点，并用启发函数h(x)对它们全部进行估价，从中选出最优结点进行扩展，而不管这个结点出现在搜索树的什么地方。（1）把初始结点S0放入open表中，计算h(S0);（2）若open表为空，则搜索失败，EXIT；（3）移出open表中第一个结

2、点N放入closed表中,并冠以序号n（4）若目标结点Sg=N则搜索成功，EXIT（5）若N不可扩展，则转步骤（2）；（6）扩展N，计算每个子结点x的函数值h(x)，并将所有子结点配以指向N的返回指针后放入open表中，再对open表中的所有子结点按其函数值大小以升序排序，转步骤2；//采用启发式修补解N皇后问题#include#include//采用启发式修补解N皇后问题#include#includeusing...namespacestd

3、;voidshuffle(intQueen[],constintn)...{//随机取得各行的初始皇后位置，以Queen[i]表示第i行的皇后位置for(inti=0;i

4、

5、(Queen[

6、i]-column)==(i-row)

7、

8、(Queen[i]-column)==(row-i)))//同列，同对角线的情况bug;}returnbug;}voidshow(intQueen[],constintn)...{//打印皇后图cout<<"╭";for(intk=0;k

9、/有皇后的位置用"凤"cout<

10、tn)...{//启发式修补intmax=-1;//标志行行之间冲突数intminbug=n;intcount=0;while(max!=0&&count<=100)...{max=0;for(inti=0;i

11、.{//保持皇后在等冲突的情况下不断变更位置，有利于后面行的优化minbug=bug;Queen[i]=j;}}if(minbug>max)max=minbug;}show(Queen,n);count;}returncount;}voidmain()...{intn=-1;intstep=0;cout<<"WelcometoNQueenSettlement"<>n;if(n<

12、=0)...{cout<<"IllegalInput!"<