人工智能实验报告八数码.doc

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

1、《人工智能》实验一题目实验一启发式搜索算法1.实验内容：使用启发式搜索算法求解8数码问题。⑴编制程序实现求解8数码问题算法，采用估价函数，其中：是搜索树中结点的深度；为结点的数据库中错放的棋子个数；为结点的数据库中每个棋子与其目标位置之间的距离总和。⑵分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是的上界的的定义，并测试使用该估价函数是否使算法失去可采纳性。2.实验目的熟练掌握启发式搜索算法及其可采纳性。3.数据结构与算法设计该搜索为一个搜索树。为了简化问题，搜索树节点设计如下：typedefstructNode//棋盘{

2、//节点结构体intdata[9];doublef,g;structNode*parent;//父节点}Node,*Lnode;intdata[9];   数码数组：记录棋局数码摆放状态。structChess*Parent; 父节点：指向父亲节点。下一步可以通过启发搜索算法构造搜索树。1、局部搜索树样例：2、搜索过程 搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点）。搜索过程如下： （1）、把原棋盘压入队列； （2）、从棋盘取出一个节点； （3）、判断棋盘估价值，为零则表示搜索完成，退出搜索； （4）、扩展子节点，

3、即从上下左右四个方向移动棋盘，生成相应子棋盘；（5）、对子节点作评估，是否为优越节点（子节点估价值小于或等于父节点则为优越节点），是则把子棋盘压入队列，否则抛弃； （5）、跳到步骤（2）；3、算法的评价完全能解决简单的八数码问题，但对于复杂的八数码问题还是无能为力。现存在的一些优缺点。1、可以改变数码规模（N），来扩展成N*N的棋盘，即扩展为N数码问题的求解过程。2、 内存泄漏。由于采用倒链表的搜索树结构，简化了数据结构，但有部分被抛弃节点的内存没有很好的处理

4、，所以会造成内存泄漏；3、 采用了屏蔽方向，有效防止往回搜索（节点的回推），但没能有效防止循环搜索，所以不能应用于复杂度较大的八数码问题；源码：#include#include#includetypedefstructNode{//节点结构体intdata[9];doublef,g;structNode*parent;}Node,*Lnode;typedefstructStack{//OPENCLOSED表

5、结构体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)<(min->npoint->f)){min=temp->next;minp=temp;}temp=temp->nex

6、t;}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;i<9;i++)for(j=0;jdata[i]>suc->data[j])&&suc->data[j]!=0)a++;if((goal->data[i]>goal->data[j])&&goal->dat

7、a[j]!=0)b++;}if(a%2==b%2)return1;elsereturn0;}intEqual(Node*suc,Node*goal){//判断节点是否相等，相等，不相等for(inti=0;i<9;i++)if(suc->data[i]!=goal->data[i])return0;return1;}Node*Belong(Node*suc,Lstack*list){//判断节点是否属于OPEN表或CLOSED表，是则返回节点地址，否则返回空地址Lstacktemp=(*list)->next;if(temp==NUL

8、L)returnNULL;while(temp!=NULL){if(Equal(suc,temp->npoint))returntemp->npoint;temp=temp->next;}returnNULL;}void