《人工智能八数码游戏》由会员分享，可在线阅读，更多相关《人工智能八数码游戏（13页珍藏版）》请在金锄头文库上搜索。
1、 . . . .实验一：八数码游戏问题一、八数码游戏问题简介九宫排字问题（又称八数码问题）是人工智能当中有名的难题之一。问题是在33方格盘上，放有八个数码，剩下第九个为空，每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始位置转化为目标位置。2 8 31 2 31 6 48 47 57 6 5 （a）初始状态 （b）目标状态 图 八数码游戏二、实验目的 1.熟悉人工智能系统中的问题求解过程； 2.熟悉状态空间的盲目搜索和启发式搜索算法的应用； 3.熟悉对八数码问题的建模、求解及编程语言的应用。三、实验的思路八数码问题：在33的方格棋盘上，摆放着1到
2、8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。例如：28312316484705765(a) 初始状态 (b) 目标状态图1 八数码问题示意图1. 启发函数设定 由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零，因此可以把数码不同的位置个数作为标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息来扩展节点的选择，减少搜索围，提高搜索速度。2. 搜索过程：（搜索采用广度搜索方式，利用待处理队
3、列辅助，逐层搜索（跳过劣质节点）a、把初始数码组压入队列；b、从队列中取出一个数码组节点；c、扩展子节点，即从上下左右四个方向移动空格，生成相应子节点：d、对子节点数码组作评估，是否为优越节点，即其评估值是否小于等于其父节点加一，是则将其压入队，否则抛弃。 e、判断压入队的子节点数码组（优越点）的评估值，为零则表示搜索完成，退出搜索； f、跳到步骤2；四、数据结构的设计数码结构体typedef struct node /八数码结构体int formNN; /数码组int evalue; /评估值，差距int udirec; /所屏蔽方向,防止往回推到上一状态,1上2下3左4右struct no
4、de *parent; /父节点Graph;Graph *QuMAX;/队列Graph *StMAX;/堆栈起始把s放入open表失败成功是否open表为空表？是把open表中的第一个节点n移入close表否扩展节点n，把其后裔放入open表的前头是否有后继节点为目标节点？否是 五、实验过程及代码#include /设计了搜索深度围，防止队列存越界#include #include #define N 3 /数码组大小 #define Max_Step 50 /最大搜索深度 #define MAX 50 typedef struct node/八数码结构体 int formNN;/数码组 in
5、t evalue;/评估值 int udirect;/所屏蔽方向，防止往回推到上已状态，1上2下3左4右 struct node *parent;/父节点 Graph;Graph *QuMAX; /队列Graph *StMAX; /堆栈/打印数码组 void Print(Graph *The_graph) int i,j; if(The_graph=NULL) printf(图为空n); else printf(-n); for(i=0;iN;i+) printf(|t); for(j=0;jformij);/遍历打印 printf(t|n); printf(|ttt差距:%dt|n,The_
6、graph-evalue);/差距显示 printf(-n); /评价函数 int Evaluate(Graph *The_graph,Graph *End_graph) int valute=0;/差距数 int i,j; for(i=0;iN;i+) for(j=0;jformij!=End_graph-formij) valute+; The_graph-evalue=valute; return valute; /移动数码组 Graph *Move(Graph *The_graph,int Direct,int CreatNew_graph) Graph *New_graph; int
7、 HasGetBlank=0;/是否获取空格位置 int AbleMove=1;/是否可移动 int i,j,t_i,t_j,x,y; for(i=0;iN;i+)/获取空格坐标i,j for(j=0;jformij=0) HasGetBlank=1; break; if(HasGetBlank=1) break; /printf(空格位置:%d,%dn,i,j); t_i=i; t_j=j; /移动空格 switch(Direct) case 1:/上 t_i-; if(t_i=N) AbleMove=0; break; case 3:/左 t_j-; if(t_j=N) AbleMove=
8、0; break; if(AbleMove=0)/不能移动则返回原节点 return The_graph; if(CreatNew_graph=1) New_graph=(Graph *)malloc(sizeof(Graph);/生成节点 for(x=0;xN;x+) for(y=0;yformxy=The_graph-formxy;/复制数码组 else New_graph=The_graph; /移动后 New_graph-formij=New_graph-formt_it_j; New_graph-formt_it_j=0; /printf(移动产生的新图:n); /Print(New_graph); return New_graph; /搜索函数 Graph *Search(Graph *Begin,Graph *End) Graph *g1,*g2,*g; int Step=0;/深度 int Direct=0;/方向 int i; int front,rear; front=rear=-1;/队列初始化 g=NULL; rear+;/入队 Qurear=Begin; while(rear!=front)/队列不空 front+;/出队 g1=Qufront;
