2024年7月22日发(作者：仝卓)
实验
八数码游戏问题
一、八数码游戏问题简介
九宫排字问题(乂称八数码问题)是人工智能当中有名的难题之一。问题是在
3X3方格盘上，放有八个数码，剩下第九个为空，每一空格其上下左右的数码可移
至空格。
问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始位置转
化为目标位置。
(a)初始状态
图
(b)目标状态
八数码游戏
二、实验目的
1 .熟悉人工智能系统中的问题求解过程；
2 .熟悉状态空间的盲目搜索和启发式搜索算法的应用;
3 .熟悉对八数码问题的建模、求解及编程语言的应用。
三、实验的思路
八数码问题：在3X3的方格棋盘上，摆放着1到8这八个数码，有1个方格
是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移
和空格下移这四个操作使得棋盘从初始状态到目标状态。
例如:
图1八数码问题示意图
1 .启发函数设定
由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路
径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，
最后为零，因此可以把数码不同的位置个数作为标志一个节点到目标节点距离远
近的一个启发性信息，利用这个信息来扩展节点的选择，减少搜索范围，提高搜索
速度。
2 .搜索过程：（搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过
劣质节点））
a、把初始数码组压入队列；
b、从队列中取出一个数码组节点；
c、扩展子节点，即从上下左右四个方向移动空格，生成相应子节点：
d、对子节点数码组作评估，是否为优越节点，即其评估值是否小于等于其父
节点加一，是则将其压入队，否则抛弃。
e、判断压入队的子节点数码组（优越点）的评估值，为零则表示搜索完成，退
出搜索；
f、跳到步骤2；
四、数据结构的设计
数码结构体
typedefstnictnode
(
intfonn[N][N];
intevalue;
intudirec;
右
stmctnode"parent;
}Graph;
Giaph*Qu[MAX];〃队歹
lj
4
//八数码结构体
〃数码组
〃评估值，差距
〃所屏蔽方向，防止往回推到上一状态,1上2下3左
〃父节点
起始
五、实验过程及代码
#mclude
#include
# defineN3〃数码组大小
# defineMax_Step50〃最大搜索深度
# defineMAX50
typedefstinctnode//八数码结构体{intform[N][N];〃数码组intevahie;//评估值
intudirect;〃所屏蔽方向，防止往回推到上已状态，1上2下3左4右
stiuctnode*parent;〃父节点
}Graph;
Graph*Qu[MAX];//队歹ij
Gi-aph*St[MAX];
n)else{pnntffn
M
);
for(i=0;i n |t H );for(j=0;j [i][j]);〃遍历打印}pinitfC , t|n n ); } pniitf( n |ttt差距:%dt|ir：The_graph->evahie);//差距显示pnntffn M ); 〃堆栈 〃 / 〃 / 〃 / 打印数码组 图为空voidPrint(Graph*The_graph){mtij;if(The_gi-aph=NULL)pnntf(” ) ) 〃//〃/〃评价函数 mtEvaluate(Graph*The_gi'aph,Graph*End_graph) { int T alute=O;//差E巨数 mtij; fbr(i=O;i { for(j=0;j ( if(The_graph->fbmi[i]|j]!=End_gi'aph->fonn[i][j]) ( valute++; } } } The_giaph->evalue=x r alute; returnvalute; } /〃/〃/〃移动数码组 Graph*Move(Graph*Tlie_gi'aph,mtDirect,intCreatNew_graph){ Graph*New_graph; intHasGetBlank=O;〃是否获取空格位置 intAbleMove=1;〃是否可移动 int for(i=0;i { for(j=0;j ( if(The_graph->fbim[i][j]=0) ( HasGetBlaiik=l; break; } } if(HasGetBlank=l)break; } 〃prin氓”空格位置:%d,%dn”,i,j); t户 U=J； 〃移动空格switch(Direct){ case1://_E tj-s if(t_i<0) AbleMove=0; break; case27/Ft_i++;if(t_i>=N) AbleMove=0; break; case3://左 if(U AbleMove=0; break; case4://右tj++;if(tj>=N) AbleMove=0;break; } if(AbleMove==0)〃不能移动则返回原节点 { returnThe_graph; ) if(CreatNew_gi , aph=1) { New_graph=(Graph*)malloc(sizeof(Graph));//生成节点for(x=0;x fbr(y^O;y ( New_gi , aph->fbnn[x][y]=The_graph->fomi[x][y];//目制数码组} } ) else New_graph=The_graph; } 〃移动后 New_graph->fdmi[i][j]=New_gi-aph->fbnn[t_i][tj]; New_graph->fbnn[t_i][t_j]=O; //pnntf("移动产生的新图:n"); //Print(New_graph); retiimNew_graph; } /〃/〃/〃搜索函数 Graph*Search(Graph"Begin,Graph*End) { Graph*gl,*g2,*g; intStep=O;〃深度 intDirect=O;〃方向 inti; intfront,rear; fiont=i-eai--l-Jf队列初始化 g=NULL; reai++;〃入队 Qu[rear]=Begin; while(rear!=fixmt)〃队列不空 { fhmHT;〃出队gl=Qu[front]; “printf("开始第％d个图ont); //Pimt(gl); for(i=1;iv=4;i++)〃分别从四个方向推导出新子节点( Duect=i; if(Du-ect=g1->udirect)〃跳过屏蔽方向contmue; g2=Move(gl,Direct,1)；〃移动数码组 if(g2!=gl)〃数码组是否可以移动 ( 〃可以移动 Evahiate(g2,End);〃评价新的节点〃pnntf("开始产生的 第％d个图: //Print(g2); if(g2->evalue<=gl->evalue+1) 〃是优越节点g2->parent=gl;〃移动空格 switch(Direct)〃设置屏蔽方向，防止往回推( case1://Jt g2->udirect=2; break; case2:〃下 g2->udu , ect=l; break; case3:〃左 g2->udkect=4; break; case4:〃右 g2->udirect=3;break; ) rear4-+; Qu[rear]=g2;〃存储节点到待处理队列 if(g2->evalue==0)〃为0则搜索完成( g=g2； //i=5;break; ) } else ( 丘ee(g2);〃抛弃劣质节点g2=NULL; } ) } if(g!=NULL)〃为0则搜索完成 ( if(g->evalue==O) break; Step++;〃统计深度if(Step>Max_Step) break; } } retiinig; } mtmam(mtargc ? constchar*argv口) { // GraphBegm_graph={ {{2,8,3},{1,6,4},{7,0,5}},0,0,NULL )； /*I GraphBegm_graph={ {{2,8,3},{1,0,4},{7,6,5}},0,0,NULL )； GraphBegm_graph={ {{2,0,1},{4,6,5},{3,7,8}},0,0,NULL )； */ 〃目标数码组 GraphEnd_graph={ {{1,2,3},{8,0,4},{7,6,5}},0,0,NULL )； Evaluate(&Begin_gi,aph,&End_graph);//对初始的数码组评价pnntf("初始 数码组:n”)； Pnnt(&Begm_graph); pnntf("目标数码组An")； Pnnt(&End_giaph); Graph*G,*P: inttop=-l; 〃图搜索 G=Search(&Begm_graph,&End_graph); 〃打印 if(G){ 〃把路径倒序 P=G; 〃压栈 while(P!=NULL) ( top++; St[top]=P; P=P->parent; } pnntf(y H ); 〃弹栈打印 while(top>-l) ( P=St[top]; top--; Prmt(P); } pniitf( n <««««««««^Mc»»»>»»»»»>^i n );}else{ prmtf("搜索不到结果，深度为％dW,Max_Step); 〃设计搜索深度范围主要是防止队列内存越界) retiim0; 六、实验结果 ・ c:l:21：warning: #include A yxhQCanuer /桌面$ •/2 初 始数码组： Cancer. /桌面$ gcc/I 数码.码 c-o2 extratokensatendof^includedirective 〃设计了搜索深度范围，防止队列内存越。 目标数码组: 3 4 5 差距：。| 3 4 5 差距 :3| 2 1 7 0 8 6 3 4 5 差 距 0 1 7 2 8 6 3 4 5 差 距 :3 3 4 1 0 7 2 8 6 ■ 巨 ：2 1 8 7 2 0 6 3 4 5 差 yxh@Canuer 桌面$ 2024年7月22日发(作者：仝卓) 实验 八数码游戏问题 一、八数码游戏问题简介 九宫排字问题(乂称八数码问题)是人工智能当中有名的难题之一。问题是在 3X3方格盘上，放有八个数码，剩下第九个为空，每一空格其上下左右的数码可移 至空格。 问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始位置转 化为目标位置。 (a)初始状态 图 (b)目标状态 八数码游戏 二、实验目的 1 .熟悉人工智能系统中的问题求解过程； 2 .熟悉状态空间的盲目搜索和启发式搜索算法的应用; 3 .熟悉对八数码问题的建模、求解及编程语言的应用。 三、实验的思路 八数码问题：在3X3的方格棋盘上，摆放着1到8这八个数码，有1个方格 是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移 和空格下移这四个操作使得棋盘从初始状态到目标状态。 例如: 图1八数码问题示意图 1 .启发函数设定 由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路 径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少， 最后为零，因此可以把数码不同的位置个数作为标志一个节点到目标节点距离远 近的一个启发性信息，利用这个信息来扩展节点的选择，减少搜索范围，提高搜索 速度。 2 .搜索过程：（搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过 劣质节点）） a、把初始数码组压入队列； b、从队列中取出一个数码组节点； c、扩展子节点，即从上下左右四个方向移动空格，生成相应子节点： d、对子节点数码组作评估，是否为优越节点，即其评估值是否小于等于其父 节点加一，是则将其压入队，否则抛弃。 e、判断压入队的子节点数码组（优越点）的评估值，为零则表示搜索完成，退 出搜索； f、跳到步骤2； 四、数据结构的设计 数码结构体 typedefstnictnode ( intfonn[N][N]; intevalue; intudirec; 右 stmctnode"parent; }Graph; Giaph*Qu[MAX];〃队歹 lj 4 //八数码结构体 〃数码组 〃评估值，差距 〃所屏蔽方向，防止往回推到上一状态,1上2下3左 〃父节点 起始 五、实验过程及代码 #mclude #include # defineN3〃数码组大小 # defineMax_Step50〃最大搜索深度 # defineMAX50 typedefstinctnode//八数码结构体{intform[N][N];〃数码组intevahie;//评估值 intudirect;〃所屏蔽方向，防止往回推到上已状态，1上2下3左4右 stiuctnode*parent;〃父节点 }Graph; Graph*Qu[MAX];//队歹ij Gi-aph*St[MAX]; n)else{pnntffn M ); for(i=0;i n |t H );for(j=0;j [i][j]);〃遍历打印}pinitfC , t|n n ); } pniitf( n |ttt差距:%dt|ir：The_graph->evahie);//差距显示pnntffn M ); 〃堆栈 〃 / 〃 / 〃 / 打印数码组 图为空voidPrint(Graph*The_graph){mtij;if(The_gi-aph=NULL)pnntf(” ) ) 〃//〃/〃评价函数 mtEvaluate(Graph*The_gi'aph,Graph*End_graph) { int T alute=O;//差E巨数 mtij; fbr(i=O;i { for(j=0;j ( if(The_graph->fbmi[i]|j]!=End_gi'aph->fonn[i][j]) ( valute++; } } } The_giaph->evalue=x r alute; returnvalute; } /〃/〃/〃移动数码组 Graph*Move(Graph*Tlie_gi'aph,mtDirect,intCreatNew_graph){ Graph*New_graph; intHasGetBlank=O;〃是否获取空格位置 intAbleMove=1;〃是否可移动 int for(i=0;i { for(j=0;j ( if(The_graph->fbim[i][j]=0) ( HasGetBlaiik=l; break; } } if(HasGetBlank=l)break; } 〃prin氓”空格位置:%d,%dn”,i,j); t户 U=J； 〃移动空格switch(Direct){ case1://_E tj-s if(t_i<0) AbleMove=0; break; case27/Ft_i++;if(t_i>=N) AbleMove=0; break; case3://左 if(U AbleMove=0; break; case4://右tj++;if(tj>=N) AbleMove=0;break; } if(AbleMove==0)〃不能移动则返回原节点 { returnThe_graph; ) if(CreatNew_gi , aph=1) { New_graph=(Graph*)malloc(sizeof(Graph));//生成节点for(x=0;x fbr(y^O;y ( New_gi , aph->fbnn[x][y]=The_graph->fomi[x][y];//目制数码组} } ) else New_graph=The_graph; } 〃移动后 New_graph->fdmi[i][j]=New_gi-aph->fbnn[t_i][tj]; New_graph->fbnn[t_i][t_j]=O; //pnntf("移动产生的新图:n"); //Print(New_graph); retiimNew_graph; } /〃/〃/〃搜索函数 Graph*Search(Graph"Begin,Graph*End) { Graph*gl,*g2,*g; intStep=O;〃深度 intDirect=O;〃方向 inti; intfront,rear; fiont=i-eai--l-Jf队列初始化 g=NULL; reai++;〃入队 Qu[rear]=Begin; while(rear!=fixmt)〃队列不空 { fhmHT;〃出队gl=Qu[front]; “printf("开始第％d个图ont); //Pimt(gl); for(i=1;iv=4;i++)〃分别从四个方向推导出新子节点( Duect=i; if(Du-ect=g1->udirect)〃跳过屏蔽方向contmue; g2=Move(gl,Direct,1)；〃移动数码组 if(g2!=gl)〃数码组是否可以移动 ( 〃可以移动 Evahiate(g2,End);〃评价新的节点〃pnntf("开始产生的 第％d个图: //Print(g2); if(g2->evalue<=gl->evalue+1) 〃是优越节点g2->parent=gl;〃移动空格 switch(Direct)〃设置屏蔽方向，防止往回推( case1://Jt g2->udirect=2; break; case2:〃下 g2->udu , ect=l; break; case3:〃左 g2->udkect=4; break; case4:〃右 g2->udirect=3;break; ) rear4-+; Qu[rear]=g2;〃存储节点到待处理队列 if(g2->evalue==0)〃为0则搜索完成( g=g2； //i=5;break; ) } else ( 丘ee(g2);〃抛弃劣质节点g2=NULL; } ) } if(g!=NULL)〃为0则搜索完成 ( if(g->evalue==O) break; Step++;〃统计深度if(Step>Max_Step) break; } } retiinig; } mtmam(mtargc ? constchar*argv口) { // GraphBegm_graph={ {{2,8,3},{1,6,4},{7,0,5}},0,0,NULL )； /*I GraphBegm_graph={ {{2,8,3},{1,0,4},{7,6,5}},0,0,NULL )； GraphBegm_graph={ {{2,0,1},{4,6,5},{3,7,8}},0,0,NULL )； */ 〃目标数码组 GraphEnd_graph={ {{1,2,3},{8,0,4},{7,6,5}},0,0,NULL )； Evaluate(&Begin_gi,aph,&End_graph);//对初始的数码组评价pnntf("初始 数码组:n”)； Pnnt(&Begm_graph); pnntf("目标数码组An")； Pnnt(&End_giaph); Graph*G,*P: inttop=-l; 〃图搜索 G=Search(&Begm_graph,&End_graph); 〃打印 if(G){ 〃把路径倒序 P=G; 〃压栈 while(P!=NULL) ( top++; St[top]=P; P=P->parent; } pnntf(y H ); 〃弹栈打印 while(top>-l) ( P=St[top]; top--; Prmt(P); } pniitf( n <««««««««^Mc»»»>»»»»»>^i n );}else{ prmtf("搜索不到结果，深度为％dW,Max_Step); 〃设计搜索深度范围主要是防止队列内存越界) retiim0; 六、实验结果 ・ c:l:21：warning: #include A yxhQCanuer /桌面$ •/2 初 始数码组： Cancer. /桌面$ gcc/I 数码.码 c-o2 extratokensatendof^includedirective 〃设计了搜索深度范围，防止队列内存越。 目标数码组: 3 4 5 差距：。| 3 4 5 差距 :3| 2 1 7 0 8 6 3 4 5 差 距 0 1 7 2 8 6 3 4 5 差 距 :3 3 4 1 0 7 2 8 6 ■ 巨 ：2 1 8 7 2 0 6 3 4 5 差 yxh@Canuer 桌面$