人工智能实验报告

1、;*大学人工智能基础课程实验报告（2011-2012学年第一学期）启发式搜索 王浩算法班 级： * 学 号： * 姓 名： * 指导教师： * 成 绩： 2012年 1 月 10 日实验一 启发式搜索算法1. 实验内容：使用启发式搜索算法求解8数码问题。 编制程序实现求解8数码问题算法，采用估价函数，其中：是搜索树中结点的深度；为结点的数据库中错放的棋子个数；为结点的数据库中每个棋子与其目标位置之间的距离总和。 分析上述中两种估价函数求解8数码问题的效率差别，给出一个是的上界的的定义，并测试使用该估价函数是否使算法失去可采纳性。2. 实验目的熟练掌握启发式搜索算法及其可采纳性。3. 实验原理

2、使用启发式信息知道搜索过程，可以在较大的程度上提高搜索算法的时间效率和空间效率；启发式搜索的效率在于启发式函数的优劣，在启发式函数构造不好的情况下，甚至在存在解的情形下也可能导致解丢失的现象或者找不到最优解，所以构造一个优秀的启发式函数是前提条件。4.实验内容 1.问题描述 在一个3*3的九宫格 里有1至8 八个数以及一个空格随机摆放在格子中，如下图：1 2 38 0 47 6 52 8 3 1 6 47 0 5 初始状态 目标状态现需将图一转化为图二的目标状态，调整的规则为：每次只能将空格与其相邻的一个数字进行交换。实质是要求给出一个合法的移动步骤，实现从初始状态到目标状态的转变。2.算法分

3、析 (1)解存在性的讨论 对于任意的一个初始状态，是否有解可通过线性代数的有关理论证明。按数组存储后，算出初始状态的逆序数和目标状态的逆序数，若两者的奇偶性一致，则表明有解。（2）估价函数的确定通过对八数码的特性的研究，找出一个相对好的函数，f(n)=d(n)+h(n)其中h(n)=2*compare(n)+3*S(n);d(n)为已搜索的深度；（compare（n）为当前节点与目标结点相同位置不相同的个数，S(n)为当前节点的无序度。）（3）节点的处理 取得一个结点后，判断是否有解，然后对其进行扩展，用估价函数从中取得一个最优节点，依次循环将路径得到，直到取的最后的目标状态。 (4)算法设计

4、 a.输入初始结点，判断解的存在性，并与目标节点对比。 b.若不是目标节点则进行扩展，生成其全部后继节点。 c.对于每个后继节点均求其f(n),并比较。d.将最小f(n)存入正确路径，并与目标节点进行对比。e.若不是目标节点则循环执行b，若是目标节点则输出5实验结果输入输出：源代码如下：#includeint final9=1,2,3,8,0,4,7,6,5;/目标状态节点int a10009,c9,e9,f9;/路径节点和扩展节点int deep=1,fn;/深度和估计值int b9;char moveaction;/移动方向int fnjisuan(int b9)/估价函数int comp

5、are=0,s=0,fn1,d9;d0=b0;d1=b1;d2=b2;d3=b5;d4=b8;d5=b7;d6=b6;d7=b3;d8=b4;for(int i=0;i9;i+)if(bi!=finali&i!=4)compare+;for(i=0;i7;i+)if(di+1-di)!=1)s+;fn1=2*compare+3*s+deep;/估价函数计算结果return fn1;void show(int c9)/输出节点for(int i=0;i9;i+)adeepi=ci;for(i=0;i9;i+)if(i)%3=0)printf(n);printf(%dt,ci);deep+;pri

6、ntf(n);int jingguo(int e9)/测试当前节点是否已经经过 避免回溯for(int i=0;ideep;i+)int k=0;for(int j=0;j9;j+)if(ej=aij)k+;if(k=9)return 0;return 1;int move_up(int c9,int Zerosign)/上移操作for(int i=0;i9;i+)ci=bi;cZerosign=cZerosign-3; cZerosign-3=0;int fn1=fnjisuan(c);return fn1;int move_down(int c9,int Zerosign)/下移操作 fo

7、r(int i=0;i9;i+)ci=bi;cZerosign=cZerosign+3; cZerosign+3=0; int fn1=fnjisuan(c);return fn1;int move_left(int c9,int Zerosign)/左移操作 for(int i=0;i9;i+)ci=bi;cZerosign=cZerosign-1; cZerosign-1=0; int fn1=fnjisuan(c);return fn1;int move_right(int c9,int Zerosign)/右移操作for(int i=0;i9;i+)ci=bi;cZerosign=cZ

8、erosign+1; cZerosign+1=0;int fn1=fnjisuan(c); return fn1;int zuixiao(int fn1,int fn2,int fn3,int fn4)/求最小值int f1,f2,f3;f1=(fn1=fn2)?fn1:fn2;f2=(fn3=fn4)?fn3:fn4;f3=(f1=f2)?f1:f2;return f3;int cixiao(int fn1,int fn2,int fn3,int fn4)/求次小值int f1,f2,f3,f4;f1=(fn1fn2)?fn1:fn2;f2=(fn3fn2)?fn1:fn2;if(f1=f2

9、)if(f3=f2)return f3;else return f2;else if(f4=f1)return f4; else return f1;void budeng(int f1,int f2,int fn1,int fn2,int fn3,int fn4,int Zerosign)/处理估价函数最小值唯一的时候if(f1=fn1)if(moveaction!=d&jingguo(c)move_up(c,Zerosign);moveaction=u;elseif(f2=fn2)move_right(c,Zerosign);moveaction=r;if(f2=fn3)move_left

10、(c,Zerosign);moveaction=l;if(f2=fn4)move_down(c,Zerosign);moveaction=d;if(f1=fn2)if(moveaction!=l&jingguo(c)move_right(c,Zerosign);moveaction=r;elseif(f2=fn3)move_left(c,Zerosign);moveaction=l;if(f2=fn4)move_down(c,Zerosign);moveaction=d;if(f2=fn1)move_up(c,Zerosign);moveaction=u;if(f1=fn3)if(moveac

11、tion!=r&jingguo(c)move_left(c,Zerosign);moveaction=l;elseif(f2=fn1)move_up(c,Zerosign);moveaction=u;if(f2=fn2)move_right(c,Zerosign);moveaction=r;if(f2=fn4)move_down(c,Zerosign);moveaction=d;if(f1=fn4)if(moveaction!=u&jingguo(c)move_down(c,Zerosign);moveaction=d;elseif(f2=fn2)move_right(c,Zerosign);

12、moveaction=r;if(f2=fn3)move_left(c,Zerosign);moveaction=l;if(f2=fn1)move_up(c,Zerosign);moveaction=u;int ceshi(int k9)/测试估价函数int fn1=100,fn2=100,fn3=100,fn4=100,f1,Zerosign;for(int i=0;i9;i+)if(0=ki)Zerosign=i;break;if(Zerosign!=0&Zerosign!=1&Zerosign!=2&moveaction!=d)fn1=move_up(c,Zerosign);if(Zero

13、sign!=2&Zerosign!=5&Zerosign!=8&moveaction!=l)fn2=move_right(c,Zerosign);if(Zerosign!=0&Zerosign!=3&Zerosign!=6&moveaction!=r)fn3=move_left(c,Zerosign);if(Zerosign!=6&Zerosign!=7&Zerosign!=8&moveaction!=u)fn4=move_down(c,Zerosign);f1=zuixiao(fn1,fn2,fn3,fn4);return f1;void move(int c9)/确定移动方向int fn1

14、=100,fn2=100,fn3=100,fn4=100,f1,f2,Zerosign;for(int i=0;i9;i+)if(0=ci)Zerosign=i;break;if(Zerosign!=0&Zerosign!=1&Zerosign!=2&moveaction!=d)fn1=move_up(c,Zerosign);if(Zerosign!=2&Zerosign!=5&Zerosign!=8&moveaction!=l)fn2=move_right(c,Zerosign);if(Zerosign!=0&Zerosign!=3&Zerosign!=6&moveaction!=r)fn3

15、=move_left(c,Zerosign);if(Zerosign!=6&Zerosign!=7&Zerosign!=8&moveaction!=u)fn4=move_down(c,Zerosign);f1=zuixiao(fn1,fn2,fn3,fn4);f2=cixiao(fn1,fn2,fn3,fn4);if(f1=f2)if(fn1=fn2&fn1=f1)move_up(c,Zerosign);for(i=0;i9;i+)ei=ci;move_right(c,Zerosign);for(i=0;i9;i+)fi=ci;if(ceshi(e)ceshi(f)&jingguo(e)mov

16、e_up(c,Zerosign);moveaction=u;else move_right(c,Zerosign);moveaction=r;if(fn1=fn3&fn1=f1)move_up(c,Zerosign);for(i=0;i9;i+)ei=ci;move_left(c,Zerosign);for(i=0;i9;i+)fi=ci;if(ceshi(e)ceshi(f)&jingguo(e)move_up(c,Zerosign);moveaction=u;else move_left(c,Zerosign);moveaction=l;if(fn1=fn4&fn1=f1)move_up(

17、c,Zerosign);for(i=0;i9;i+)ei=ci;move_down(c,Zerosign);for(i=0;i9;i+)fi=ci;if(ceshi(e)ceshi(f)&jingguo(e)move_up(c,Zerosign);moveaction=u;else move_down(c,Zerosign);moveaction=d;if(fn2=fn3&fn2=f1)move_right(c,Zerosign);for(i=0;i9;i+)ei=ci;move_left(c,Zerosign);for(i=0;i9;i+)fi=ci;if(ceshi(e)ceshi(f)&

18、jingguo(e)move_right(c,Zerosign);moveaction=r;else move_left(c,Zerosign);moveaction=l;if(fn2=fn4&fn2=f1)move_right(c,Zerosign);for(i=0;i9;i+)ei=ci;move_down(c,Zerosign);for(i=0;i9;i+)fi=ci;if(ceshi(e)ceshi(f)&jingguo(e)move_right(c,Zerosign);moveaction=r;else move_down(c,Zerosign);moveaction=d;if(fn

19、3=fn4&fn3=f1)move_left(c,Zerosign);for(i=0;i9;i+)ei=ci;move_down(c,Zerosign);for(i=0;i9;i+)fi=ci;if(ceshi(e)ceshi(f)&jingguo(e)move_left(c,Zerosign);moveaction=l; else move_down(c,Zerosign);moveaction=d;else budeng(f1,f2,fn1,fn2,fn3,fn4,Zerosign);int duibi(int c9) /与目标节点比较for(int i=0;i=9)return 1;el

20、se return 0;int cunzaixing(int c9) /得出初始化节点是否存在路径到目标节点int nixu=0,nixu1=0,i,j;for( j=0;j9;j+)for(int i=j+1;ifinali&finalj!=0&finali!=0)nixu+;for(j=0;j9;j+)for( i=j+1;ici&cj!=0&ci!=0)nixu1+; if(nixu%2)-(nixu1%2)=0) return 1;else return 0;void main()/主函数int sd=1;printf(请输入初始结点如（2 8 3 1 6 4 7 0 5）以空格隔开的

21、九个0到9之间的不重复数: n);for(int i=0;i9;i+)scanf(%d,&bi); ci=bi;printf(您输入的初始矩阵为：n);show(c);deep-;if(cunzaixing(c)=0)printf(此矩阵不存在路径至目标矩阵！n);elsewhile(!duibi(c)&deep100)move(c);printf(第%d步移动后的矩阵为：n,sd+);show(c);for(int i=0;i(q1-r1)-(p1-q1)-(p1-r1)函数inite主要作用是负责将符号初始化成树的结构。函数clone复制一棵完全相同的符号树。函数restruct查找所有&

22、，|， 等符号，并将其拆分成新形式：！，-符号。函数searching王浩算法的主要函数。函数show和output:显示符号串和推理过程。五实验结果公式正确 六实验总结通过本次实验，使我更深入的理解了启发式搜索的原理以及实现，对于其优越性有一定认识，加深了对语法分析以及逻辑公式理解，同时熟练掌握了对树的操作。在编程实现过程中出现过不少问题，通过一次次调试得以解决，并一定程度上提高了我的编程能力，而且让我对人工智能这一课程有了更直接的认知。王浩算法源代码清单：#include#include#include#define MAX_L 5int i=0;int stepcount=1;enum

23、typeand,or,detrusion,equal,level,variable;struct nodechar *s;type kind;int polar;node *next;node *child;int start;struct stepstep *child;step *brother;node *lhead;node *rhead;int count;char name30;int inite(char *s,node *head)int len=strlen(s);int j=0,polar=1;node *now=NULL;node *last=NULL;if(s=NULL

24、)return 0;last=head;while(ilen)if(si=|)if(!(si+1=A|si+1=a)&si+1!=1&si+1!=0&si+1!=(&si+1!=!|i=0)return 0;now=(node*)malloc(sizeof(node);now-kind=or;now-s=NULL;now-next=NULL;now-child=NULL;now-polar=polar;now-start=0;if(last-kind=level&last-child=NULL)last-child=now;elselast-next=now;last=now;i+;else

25、if(si=&)if(!(si+1=A|si+1=a)&si+1!=1&si+1!=0&si+1!=(&si+1!=!|i=0)return 0;now=(node*)malloc(sizeof(node);now-kind=and;now-s=NULL;now-next=NULL;now-child=NULL;now-polar=polar;now-start=0;if(last-kind=level&last-child=NULL)last-child=now;elselast-next=now;last=now;i+;else if(si=!)if(!(si+1=A|si+1=a)&si

26、+1!=1&si+1!=0&si+1!=(&si+1!=!)return 0;polar=1-polar;i+;else if(si=-)if(si+1!=|(si+2!=!&si+2!=(&!(si+2=A|si+2=a)|i=0)return 0;now=(node*)malloc(sizeof(node);now-kind=detrusion;now-s=NULL;now-next=NULL;now-child=NULL;now-polar=polar;now-start=0;if(last-kind=level&last-child=NULL)last-child=now;elsela

27、st-next=now;last=now;i=i+2;else if(si=)|(si+3!=!&si+3!=(&!(si+3=A|si+3=a)|i=0)&si+3!=1&si+3!=0)return 0;now=(node*)malloc(sizeof(node);now-kind=equal;now-s=NULL;now-next=NULL;now-child=NULL;now-polar=polar;now-start=0;if(last-kind=level&last-child=NULL)last-child=now;elselast-next=now;last=now;i=i+3

28、;else if(si=A|si=a)now=(node*)malloc(sizeof(node);now-kind=variable;now-next=NULL;now-child=NULL;now-polar=polar;now-start=0;now-s=(char*)malloc(MAX_L*sizeof(char);if(last-kind=level&last-child=NULL)last-child=now;elselast-next=now;last=now;j=0;while(si=A|si=a)|(si=0)(now-s)j=si;i+;j+;if(si!=|&si!=&

29、si!=-&si!=s)j=0;polar=1;else if(si=1|si=0)if(si+1!=kind=equal;now-s=(char*)malloc(2*sizeof(char);(now-s)0=si;(now-s)1=0;now-next=NULL;now-child=NULL;now-polar=polar;now-start=0;if(last-kind=level&last-child=NULL)last-child=now;elselast-next=now;last=now;i+;else if(si=()if(!(si+1=A|si+1=a)&si+1!=1&si

30、+1!=0&si+1!=!&si+1!=()return 0;now=(node*)malloc(sizeof(node);now-kind=level;now-s=NULL;now-next=NULL;now-child=NULL;now-polar=polar;now-start=0;if(last-kind=level&last-child=NULL)last-child=now;elselast-next=now;last=now;i+;polar=1;if(!inite(s,last)return 0;else if(si=)if(si+1!=P&si+1!=1&si+1!=0&si

31、+1!=-&si+1!=kind=parent-kind;son-polar=parent-polar;son-s=parent-s;son-start=parent-start;if(parent-next!=NULL)son-next=clone(parent-next);else son-next=NULL;if(parent-child!=NULL)son-child=clone(parent-child);elseson-child=NULL;return son;void remove(node *head)node *now=NULL;now=head;if(now=NULL)r

32、eturn;if(now-kind=level&now-child-kind=variable&now-child-next=NULL)now-polar=(now-child-polar=now-polar);now-child-polar=1;while(now-kind=level&now-child-kind=level&now-child-next=NULL)now-polar=(now-polar=now-child-polar);now-child=now-child-child;if(now-next!=NULL)remove(now-next);if(now-child!=N

33、ULL)remove(now-child);void restruct(node* head)node *now=NULL;node *last=NULL;node *newone=NULL,*newtwo=NULL,*newthree=NULL,*newfour=NULL,*newnow=NULL;int order=1;while(orderchild;while(now!=NULL)if(now-kind=variable|now-kind=level)&order=1)if(now-next!=NULL&now-next-kind=and)newone=(node*)malloc(si

34、zeof(node);newone-child=NULL;newone-kind=level;newone-next=NULL;newone-polar=0;newone-s=NULL;newone-start=0;if(last-kind=level)last-child=newone;elselast-next=newone;newone-next=now-next-next-next;newone-child=now;now-next-next-polar=1-now-next-next-polar;now-next-kind=detrusion;now-next-next-next=N

35、ULL;now=newone;elselast=now;now=now-next;else if(now-kind=variable|now-kind=level)&order=2)if(now-next!=NULL&now-next-kind=or) newone=(node*)malloc(sizeof(node);newone-child=NULL;newone-kind=level;newone-next=NULL;newone-polar=1;newone-s=NULL;newone-start=0;if(last-kind=level)last-child=newone;elsel

36、ast-next=newone;newone-next=now-next-next-next;newone-child=now;now-polar=1-now-polar;now-next-kind=detrusion;now-next-next-next=NULL;now=newone;elselast=now;now=now-next;else if(now-kind=variable|now-kind=level)&order=3)if(now-next!=NULL&now-next-kind=equal)newone=(node*)malloc(sizeof(node);newone-

37、child=NULL;newone-kind=level;newone-next=NULL;newone-polar=0;newone-s=NULL;newone-start=0;newtwo=(node*)malloc(sizeof(node);newtwo-child=NULL;newtwo-kind=level;newtwo-next=NULL;newtwo-polar=1;newtwo-s=NULL;newtwo-start=0;newthree=(node*)malloc(sizeof(node);newthree-child=NULL;newthree-kind=detrusion

38、;newthree-next=NULL;newthree-polar=1;newthree-s=NULL;newthree-start=0;newfour=(node*)malloc(sizeof(node);newfour-child=NULL;newfour-kind=level;newfour-next=NULL;newfour-polar=0;newfour-s=NULL;newfour-start=0;if(last-kind=level)last-child=newone; elselast-next=newone;newone-next=now-next-next-next;ne

39、wone-child=newtwo;now-next-kind=detrusion;newtwo-child=now;now-next-next-next=NULL;newtwo-next=newthree;newthree-next=newfour;newfour-next=NULL;newnow=clone(now);newnow-next-kind=detrusion;newfour-child=newnow-next-next;newnow-next-next-next=newnow-next;newnow-next-next=newnow;newnow-next=NULL;now=n

40、ewone;elselast=now;now=now-next;else if(now-kind=level&order=4)restruct(now);last=now;now=now-next;elselast=now;now=now-next;order+;void show(node *head)node *now=NULL;now=head;while(now!=NULL)if(now-kind=level)if(now-polar=0)printf(!);if(now-start!=1|(now-polar=0&now-child-next!=NULL)printf();show(now-child);if(now-start!=1|(now-polar=0&now-child-next!=NULL)printf();now=now-next;if(now!=NULL&now-start=1)putchar(,);else if(now-kind=and)printf(&);now=now-next;else if(now-kind=or)print