人工智能实验一-八数码问题

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

1、【实验名称】人工智能实验一：八数码问题算法描述：步1把初始节点S0放入OPEN表中，计算h(S0)；步2若OPEN表为空，则搜索失败，退出；步3取OPEN表中前面第一个节点N放入CLOSED表中；步4若目标节点Sg=N，则搜索成功，结束;步5若N不可扩展，则转步2。步6扩展N，计算每个子节点x的函数值h(x)，并将所有子节点配上指向N的返回指针放入OPEN表中，再对OPEN表中的所有子节点按其函数值大小以升序排序，转步2。实验代码：#include#include#include

2、h>#defineOverflow1#defineN3intgoal[N][N]={1,2,3,8,0,4,7,6,5};intzero[2],NodeQTY=0;int*z=zero;//记录0的位置，zero[0]:r行；zero[1]:c列typedefintPiece;structChessboard{//棋盘信息Piecepos[N][N];//记录每个数码a的位置r行c列intd,f,move;//d:深度；f:启发函数值；move:父节点移动到该节点的方式};structLNode{Chessboardboard;LN

3、ode*parent,*next;boolflag;};typedefLNode*List;int*Findzero(LNode*&Node){inti,j,zr[2];int*z=zr;for(i=0;iboard.pos[i][j]==0){zr[0]=i+1;zr[1]=j+1;break;}}}returnz;}intWrong(LNode*Node){intw=0,i,j;for(i=0;i

4、>board.pos[i][j]!=goal[i][j]&&Node->board.pos[i][j]!=0)w++;}}returnw;}intpick(LNode*Node){intw=0,i,j,ii,jj;for(i=0;iboard.pos[i][j]!=goal[i][j]&&Node->board.pos[i][j]!=0){for(ii=0;iiboard.pos[i][j]==

5、goal[ii][jj]){w=w+abs(ii-i)+abs(jj-j);break;}}}}returnw;}LNode*extend(LNode*Node,intdepth,intzero[2],intmoveflag,intChoose){LNode*NewNode=newLNode;for(inti=0;iboard.pos[i][j]=Node->board.pos[i][j];}}switch(moveflag){case1://向左移，不能出界

6、：zero[1]>=2NewNode->board.pos[zero[0]-1][zero[1]-1]=NewNode->board.pos[zero[0]-1][zero[1]-2];NewNode->board.pos[zero[0]-1][zero[1]-2]=0;break;case2://向右移，不能出界：zero[1]<=2NewNode->board.pos[zero[0]-1][zero[1]-1]=NewNode->board.pos[zero[0]-1][zero[1]];NewNode->board.pos[z

7、ero[0]-1][zero[1]]=0;break;case3://向上移，不能出界：zero[0]>=2NewNode->board.pos[zero[0]-1][zero[1]-1]=NewNode->board.pos[zero[0]-2][zero[1]-1];NewNode->board.pos[zero[0]-2][zero[1]-1]=0;break;case4://向下移，不能出界：zero[0]<=2NewNode->board.pos[zero[0]-1][zero[1]-1]=NewNode->board.p

8、os[zero[0]][zero[1]-1];NewNode->board.pos[zero[0]][zero[1]-1]=0;break;}NewNode->board.d=depth+1;switch(Choose){case1: