人工智能试验报告

本文格式为Word版，下载可任意编辑——人工智能试验报告《人工智能》试验一题目

试验一启发式探寻算法

1.试验内容：

使用启发式探寻算法求解8数码问题。

⑴编制程序实现求解8数码问题A?算法，采用估价函数

??w?n?，f?n??d?n???pn????其中：d?n?是探寻树中结点n的深度；w?n?为结点n的数据库中错放的棋子个数；p?n?为结点n的数据库中每个棋子与其目标位置之间的距离总和。

⑵分析上述⑴中两种估价函数求解8数码问题的效率区别，给出一个是p?n?的上界的h?n?的定义，并测试使用该估价函数是否使算法失去可采用性。

2.试验目的

熟练把握启发式探寻A算法及其可采用性。3.数据结构与算法设计

该探寻为一个探寻树。为了简化问题，探寻树节点设计如下：typedefstructNode//棋盘{//节点结构体intdata[9];doublef,g;

structNode*parent;//父节点}Node,*Lnode;

intdata[9];数码数组：记录棋局数码摆放状态。structChess*Parent;父节点：指向父亲节点。下一步可以通过启发探寻算法构造探寻树。1、局部探寻树样例：

?

2、探寻过程

探寻采用广度探寻方式，利用待处理队列辅助，逐层探寻（跳过劣质节点）。探寻过程如下：

（1）、把原棋盘压入队列；（2）、从棋盘取出一个节点；

（3）、判断棋盘估价值，为零则表示探寻完成，退出探寻；

（4）、扩展子节点，即从上下左右四个方向移动棋盘，生成相应子棋盘；

（5）、对子节点作评估，是否为优越节点（子节点估价值小于或等于父节点则为优越节

点），是则把子棋盘压入队列，否则抛弃；（5）、跳到步骤（2）；3、算法的评价

完全能解决简单的八数码问题，但对于繁杂的八数码问题还是无能为力。现存在的一些优缺点。

1、可以改变数码规模（N），来扩展成N*N的棋盘，即扩展为N数码问题的求解过程。2、内存泄漏。由于采用倒链表的探寻树结构，简化

了数据结构，但有部分被抛弃节点的内存没有很好的处理，所以会造成内存泄漏；3、采用了屏蔽方向，有效防止往回探寻（节点的回

推），但没能有效防止循环探寻，所以不能应用于繁杂度较大的八数码问题；

源码：

#include#include#include

typedefstructNode{//节点结构体intdata[9];doublef,g;structNode*parent;}Node,*Lnode;

typedefstructStack

{//OPENCLOSED表结构体Node*npoint;structStack*next;}Stack,*Lstack;

Node*Minf(Lstack*Open)

{//选取OPEN表上f值最小的节点，返回该节点地址Lstacktemp=(*Open)->next,min=(*Open)->next,minp=(*Open);Node*minx;

while(temp->next!=NULL){if((temp->next->npoint->f)npoint->f)){min=temp->next;minp=temp;}temp=temp->next;}

minx=min->npoint;temp=minp->next;minp->next=minp->next->next;free(temp);returnminx;}

intCanslove(Node*suc,Node*goal){//判断是否可解inta=0,b=0,i,j;for(i=1;idata[i]>suc->data[j])if((goal->data[i]>goal->data[j])}if(a%2==b%2)return1;elsereturn0;}

intEqual(Node*suc,Node*goal)

{//判断节点是否相等，相等，不相等for(inti=0;idata[i]!=goal->data[i])return0;return1;}

Node*Belong(Node*suc,Lstack*list)

{//判断节点是否属于OPEN表或CLOSED表，是则返回节点地址，否则返回空地址Lstacktemp=(*list)->next;if(temp==NULL)returnNULL;while(temp!=NULL){if(Equal(suc,temp->npoint))returntemp->npoint;temp=temp->next;}returnNULL;}

voidPutinto(Node*suc,Lstack*list){//把节点放入OPEN或CLOSED表中Stack*temp;temp=(Stack*)malloc(sizeof(Stack));temp->npoint=suc;

temp->next=(*list)->next;(*list)->next=temp;}

///////////////计算f值部分-开始//////////////////////////////doubleFvalue(Nodesuc,Nodegoal,intm){//计算f值switch(m){case1:{interror(Node,Node);intw=0;w=error(suc,goal);returnw+suc.g;}case2:{doubleDistance(Node,Node,int);doublep=0;for(inti=1;ifor(k=0;kg)g)){temp->parent=(*suc)->parent;temp->g=(*suc)->g;temp->f=(*suc)->f;flag=1;}}else{Putinto(*suc,Open);(*suc)->f=Fvalue(**suc,goal,m);}returnflag;}

intCanspread(Nodesuc,intn){//判断空格可否向该方向移动，，，表示空格向上向下向左向右移inti,flag=0;for(i=0;idata[i]=child->parent->data[i];for(i=0;idata[i]==0)break;if(n==0)loc=i%3+(i/3-1)*3;elseif(n==1)loc=i%3+(i/3+1)*3;elseif(n==2)loc=i%3-1+(i/3)*3;elseloc=i%3+1+(i/3)*3;temp=child->data[loc];child->data[i]=temp;child->data[loc]=0;}

voidSpread(Lnode*suc,Lstack*Open,Lstack*Closed,Nodegoal,intm){//扩展后继节点总函数inti;Node*child;for(i=0;ig=(*suc)->g+1;//算子节点的g值child->parent=(*suc);//子节点父指针指向父节点Spreadchild(child,i);//向该方向移动空格生

成子节点

if(BelongProgram(}}}

///////////////////////扩展后继节点部分的函数-终止//////////////////////////////////

Node*Process(Lnode*org,Lnode*goal,Lstack*Open,Lstack*Closed,intm){//总执行函数while(1){if((*Open)->next==NULL)returnNULL;//判断OPEN表是否为空，为空则失败退出Node*minf=Minf(Open);//从OPEN表中取出f值最小的节点Putinto(minf,Closed);//将节点放入CLOSED表中if(Equal(minf,*goal))returnminf;//假使当前节点是目标节点，则成功退出

Spread(//当前节点不是目标节点时扩展当前节点的后继节点}}

intShownum(Node*result)

{//递归显示从初始状态到达目标状态的移动方法if(result==NULL)return0;else{intn=Shownum(result->parent);printf(\第%d步：\for(inti=0;idata[i*3+j]!=0)printf(\elseprintf(\}}printf(\

returnn+1;}}

voidCheckinput(Node*suc){//检查输入inti=0,j=0,flag=0;charc;while(i=0)flag=0;}elseif(c>='0'flag=1;for(j=0;jdata[j]==suc->data[i])flag=-2;i++;}elseif(flag>=0)flag=-1;}elseif(flag>=0)flag=-1;}if(flagnext)!=NULL){k++;s=s->next;}returnk;}

voidmain()

{//主函数//初始操作，建立open和closed表LstackOpen=(Stack*)malloc(sizeof(Stack));Open->next=NULL;LstackClosed=(Stack*)malloc(sizeof(Stack));Closed->next=NULL;Node*org=(Node*)malloc(sizeof(Node));org->parent=NULL;//初始状态节点org->f=1;org->g=1;

Node*goal=(Node*)malloc(sizeof(Node));//目标状态节点Node*result;intm;charc;intk;printf(\printf(\说明:状态矩阵由0-8九个数字表示,\\n请依次依照九宫格上的行列顺序输入,每个数字间用空格隔开。\\n\