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

【实验名称】 人工智能实验一 ： 八数码问题 算法描述： 步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。 实验代码： #includestdio.h #includemalloc.h #includestdlib.h #define Overflow 1 #define N 3 int goal[N][N]={1,2,3,8,0,4,7,6,5}; int zero[2],NodeQTY=0; int *z=zero;//记录0的位置，zero[0]:r行；zero[1]:c列 typedef int Piece; struct Chessboard{//棋盘信息 Piece pos[N][N];//记录每个数码a的位置r行c列 int d,f,move;//d:深度；f:启发函数值 ；move:父节点移动到该节点的方式 }; struct LNode{ Chessboard board; LNode *parent,*next; bool flag; }; typedef LNode* List; int* Findzero(LNode* Node) { int i,j,zr[2]; int *z=zr; for(i=0;iN;i++){ for(j=0;jN;j++){ if(Node-board.pos[i][j]==0){ zr[0]=i+1; zr[1]=j+1; break; } } } return z; } int Wrong(LNode *Node) { int w=0,i,j; for(i=0;iN;i++){ for(j=0;jN;j++){ if(Node-board.pos[i][j]!=goal[i][j]Node-board.pos[i][j]!=0) w++; } } return w; } int pick(LNode *Node) { int w=0,i,j,ii,jj; for(i=0;iN;i++){ for(j=0;jN;j++){ if(Node-board.pos[i][j]!=goal[i][j]Node-board.pos[i][j]!=0){ for(ii=0;iiN;ii++) for(jj=0;jjN;jj++) if(Node-board.pos[i][j]==goal[ii][jj]){ w=w+abs(ii-i)+abs(jj-j); break; } } } } return w; } LNode* extend(LNode *Node,int depth,int zero[2],int moveflag,int Choose) { LNode* NewNode=new LNode; for(int i=0;iN;i++){ for(int j=0;jN;j++){ NewNode-board.pos[i][j]=Node-board.pos[i][j]; } } switch(moveflag) { case 1: //向左移，不能出界：zero[1]=2 NewNode-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; case 2: //向右移，不能出界：zero[1]=2 NewNode-board.pos[zero[0]-1][zero[1]-1]=NewNode-board.pos[zero[0]-1][zero[1]]; NewNode-board.pos[zero[0]-1][zero[1]]=0; break; case 3: //向上移，不能出界：zero[0]=2 NewNode-board.pos[zero[0]-1][zero[1]-1]=NewNode-board.pos