人工智能实验报告八数码(共11页).doc

《人工智能实验报告八数码(共11页).doc》由会员分享，可在线阅读，更多相关《人工智能实验报告八数码(共11页).doc（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、double f,g;struct Node * parent; /父节点Node,*Lnode;int data9; 数码数组：记录棋局数码摆放状态。struct Chess * Parent; 父节点：指向父亲节点。下一步可以通过启发搜索算法构造搜索树。1、局部搜索树样例：2、搜索过程 搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点）。搜索过程如下： （1）、把原棋盘压入队列； （2）、从棋盘取出一个节点； （3）、判断棋盘估价值，为零则表示搜索完成，退出搜索； （4）、扩展子节点，即从上下左右四个方向移动棋盘，生成相应子棋盘；（5）、对子节点作评估，是否为优越节点（子节

3、点估价值小于或等于父节点则为优越节点），是则把子棋盘压入队列，否则抛弃； （5）、跳到步骤（2）；3、算法的评价完全能解决简单的八数码问题，但对于复杂的八数码问题还是无能为力。现存在的一些优缺点。1、可以改变数码规模（N），来扩展成N*N的棋盘，即扩展为N数码问题的求解过程。2、 内存泄漏。由于采用倒链表的搜索树结构，简化了数据结构，但有部分被抛弃节点的内存没有很好的处理，所以会造成内存泄漏；3、 采用了屏蔽方向，有效防止往回搜索（节点的回推），但没能有效防止循环搜索，所以不能应用于复杂度较大的八数码问题；源码：#include #include #include typedef struct

4、 Node/节点结构体 int data9;double f,g;struct Node * parent;Node,*Lnode;typedef struct Stack/OPEN CLOSED 表结构体Node * npoint;struct Stack * next;Stack,* Lstack;Node * Minf(Lstack * Open)/选取OPEN表上f值最小的节点，返回该节点地址Lstack temp = (*Open)-next,min = (*Open)-next,minp = (*Open);Node * minx; while(temp-next != NULL)

5、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);return minx;int Canslove(Node * suc, Node * goal)/判断是否可解int a = 0,b = 0,i,j;for(i = 1; i 9;i+)for(j = 0;j datai suc-dataj) & suc-dataj != 0)a+;if(goa

6、l-datai goal-dataj) & goal-dataj != 0)b+;if(a%2 = b%2)return 1;else return 0;int Equal(Node * suc,Node * goal)/判断节点是否相等，相等，不相等for(int i = 0; i datai != goal-datai)return 0; return 1;Node * Belong(Node * suc,Lstack * list)/判断节点是否属于OPEN表或CLOSED表，是则返回节点地址，否则返回空地址Lstack temp = (*list) - next ;if(temp =

7、NULL)return NULL;while(temp != NULL)if(Equal(suc,temp-npoint)return temp - npoint;temp = temp-next;return NULL;void Putinto(Node * suc,Lstack * list)/把节点放入OPEN 或CLOSED 表中 Stack * temp;temp =(Stack *) malloc(sizeof(Stack);temp-npoint = suc;temp-next = (*list)-next;(*list)-next = temp;/计算f值部分-开始/doubl

8、e Fvalue(Node suc, Node goal, int m)/计算f值switch(m)case 1:int error(Node,Node);int w=0;w=error(suc,goal);return w+suc.g; case 2:double Distance(Node,Node,int);double p = 0;for(int i = 1; i = 8; i+)p = p + Distance(suc, goal, i);return p + suc.g; /f = h + g; default:break; int error(Node suc,Node goal

9、)/计算错位个数int w,i;w=0;for(i=0;i9;i+)if(suc.datai!=goal.datai)w+;return w;double Distance(Node suc, Node goal, int i)/计算方格的错位距离int k,h1,h2;for(k = 0; k g) g)temp-parent = (*suc)-parent;temp-g = (*suc)-g;temp-f = (*suc)-f; flag = 1;elsePutinto(* suc, Open);(*suc)-f = Fvalue(*suc, goal, m);return flag; i

10、nt Canspread(Node suc, int n)/判断空格可否向该方向移动，表示空格向上向下向左向右移int i,flag = 0;for(i = 0;i 9;i+)if(suc.datai = 0)break;switch(n)case 1:if(i/3 != 0)flag = 1;break;case 2:if(i/3 != 2)flag = 1;break;case 3:if(i%3 != 0)flag = 1;break;case 4:if(i%3 != 2)flag = 1;break;default:break;return flag ;void Spreadchild(

11、Node * child,int n)/扩展child节点的字节点n表示方向，表示空格向上向下向左向右移int i,loc,temp;for(i = 0;i datai = child-parent-datai;for(i = 0;i datai = 0)break;if(n=0)loc = i%3+(i/3 - 1)*3;else if(n=1)loc = i%3+(i/3 + 1)*3;else if(n=2)loc = i%3-1+(i/3)*3;elseloc = i%3+1+(i/3)*3;temp = child-dataloc;child-datai = temp;child-d

12、ataloc = 0;void Spread(Lnode * suc, Lstack * Open, Lstack * Closed, Node goal, int m)/扩展后继节点总函数int i;Node * child;for(i = 0; i g = (*suc)-g +1; /算子节点的g值 child-parent = (*suc); /子节点父指针指向父节点 Spreadchild(child, i); /向该方向移动空格生成子节点 if(BelongProgram(&child, Open, Closed, goal, m) /判断子节点是否属于OPEN或CLOSED表并作出

13、相应的处理free(child);/扩展后继节点部分的函数-结束/Node * Process(Lnode * org, Lnode * goal, Lstack * Open, Lstack * Closed, int m)/总执行函数while(1)if(*Open)-next = NULL)return NULL; /判断OPEN表是否为空，为空则失败退出 Node * minf = Minf(Open); /从OPEN表中取出f值最小的节点Putinto(minf, Closed); /将节点放入CLOSED表中 if(Equal(minf, *goal)return minf; /如

14、果当前节点是目标节点，则成功退出 Spread(&minf, Open, Closed, *goal, m); /当前节点不是目标节点时扩展当前节点的后继节点int Shownum(Node * result)/递归显示从初始状态到达目标状态的移动方法if(result = NULL)return 0;elseint n = Shownum(result-parent);printf(第%d步：,n);for(int i = 0; i 3; i+)printf(n);for(int j = 0; j datai*3+j != 0)printf( %d ,result-datai*3+j);el

15、se printf( 0 );printf(n);return n+1;void Checkinput(Node *suc)/检查输入int i = 0,j = 0,flag = 0;char c;while(i = 0)flag = 0;else if(c = 0 & c datai = (c-0);flag = 1;for(j =0; j dataj = suc-datai)flag = -2; i+;else if(flag = 0)flag = -1;elseif(flag = 0)flag = -1;if(flag 0 | i 9)if(flag 0)if(flag = -1)pri

16、ntf(含有非法字符或数字!n请重新输入:n);else if(flag = -2)printf(输入的数字有重复!n请重新输入:n);else if(i next)!=NULL)k+;s=s-next;return k;void main()/主函数 /初始操作，建立open和closed表Lstack Open = (Stack *) malloc(sizeof(Stack);Open-next = NULL;Lstack Closed = (Stack *) malloc(sizeof(Stack);Closed-next = NULL;Node * org = (Node *) mal

17、loc(sizeof(Node);org-parent = NULL; /初始状态节点org-f =1;org-g =1; Node * goal = (Node *) malloc(sizeof(Node); /目标状态节点Node * result;int m;char c;int k;printf(=n);printf(说明:状态矩阵由0-8 九个数字表示,n请依次按照九宫格上的行列顺序输入,每个数字间用空格隔开。n); printf(=n);printf(请输入初始状态(0-8 9个数字以空格隔开回车表示输入结束):n);Checkinput(org);printf(请输入目标状态(0

18、-8 9个数字以空格隔开回车表示输入结束):n);Checkinput(goal);if(Canslove(org, goal)/A*算法开始，先将初始状态放入OPEN表 printf(请选择：1.按w(n)搜索 2.按p(n)搜索 n); scanf(%d,&m); while(c = getchar() != 10); printf(搜索中，请耐心等待(如果您觉得时间太久请重新执行程序并输入更快的速度,默认值为).n); Putinto(org,&Open); result = Process(&org, &goal, &Open, &Closed, m); /进行剩余的操作 printf(总步数:%d,Shownum(result)-1); printf(n); k=meassure(Closed); printf(扩展节点数：n); printf(%dn,k); printf(Press Enter key to exit!); while(c = getchar() != 10);else printf(程序认定该起始状态无法道达目标状态!n);专心-专注-专业