人工智能试验报告

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

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

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

4、节点则进行扩展，生成其全部后继节点。c. 对于每个后继节点均求其f(n),并比较。d.将最小f(n)存入正确路径，并与目标节点进行对比。e.若不是目标节点则循环执行b,若是目标节点则输出5实验结果输入输出：源代码如下：#includeintfinal9=123,8,0,4,7,6,5;目标状态节点inta10009,c9,e9,f9;路径节点和扩展节点intdeep=1,fn;/深度和估计值intb9;charmoveaction;/移动方向intfnjisuan(intb9)/估价函数intcompare=0,s=0,fn1,d9;d0=b0;d1=b1;d2=b2;d3=b5;d4=b8;

5、d5=b7;d6=b6;d7=b3;d8=b4;for(inti=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;/估价函数计算结果returnfn1;voidshow(intc9)/输出节点for(inti=0;i9;i+)adeepi=ci;for(i=0;i9;i+)if(i)%3=0)printf(n);printf(%dt,ci);deep+;printf(n);intjingguo(inte9)/测试当前节点是否已经经过避免回溯for(inti=0;

6、ideep;i+)intk=0;for(intj=0;j9;j+)if(ej=aij)k+;if(k=9)return0;return1;intmove_up(intc9,intZerosign)/上移操作for(inti=0;i9;i+)ci=bi;cZerosign=cZerosign-3;cZerosign-3=0;intfn1=fnjisuan(c);returnfn1;intmove_down(intc9,intZerosign)/下移操作for(inti=0;i9;i+)ci=bi;cZerosign=cZerosign+3;cZerosign+3=0;intfn1=fnjisua

7、n(c);returnfn1;intmove_left(intc9,intZerosign)/for(inti=0;i9;i+)ci=bi;cZerosign=cZerosign-1;cZerosign-1=0;intfn1=fnjisuan(c);returnfn1;intmove_right(intc9,intZerosign)/for(inti=0;i9;i+)ci=bi;cZerosign=cZerosign+1;cZerosign+1=0;intfn1=fnjisuan(c);returnfn1;intzuixiao(intfn1,intfn2,intfn3,intfn4)/intf

8、1,f2,f3;f1=(fn1=fn2)?fn1:fn2;f2=(fn3=fn4)?fn3:fn4;f3=(f1=f2)?f1:f2;returnf3;intcixiao(intfn1,intfn2,intfn3,intfn4)/intf1,f2,f3,f4;f1=(fn1fn2)?fn1:fn2;f2=(fn3fn2)?fn1:fn2;if(f1=f2)if(f3=f2)returnf3;elsereturnf2;elseif(f4=f1)returnf4;elsereturnf1;左移操作右移操作求次小值求最小值处理估价函数最voidbudeng(intf1,intf2,intfn1,in

9、tfn2,intfn3,intfn4,intZerosign)/小值唯一的时候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(c,Zerosign);moveaction=l;if(f2=fn4)move_down(c,Zerosign);moveaction=d;if(f1=fn2)if(moveaction!=l&jingguo(c)move_right(c,Z

10、erosign);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(moveaction!=r&jingguo(c)move_left(c,Zerosign);moveaction=l;elseif(f2=fn1)move_up(c,Zerosign);moveaction=u;if(f2=fn2)move_right(c

11、,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);moveaction=r;if(f2=fn3)move_left(c,Zerosign);moveaction=l;if(f2=fn1)move_up(c,Zerosign);moveaction=u;intceshi(intk9)/测试估价函

12、数intfn1=100,fn2=100,fn3=100,fn4=100,f1,Zerosign;for(inti=0;i9;i+)if(0=ki)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)

13、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);returnf1;voidmove(intc9)/确定移动方向intfn1=100,fn2=100,fn3=100,fn4=100,f1,f2,Zerosign;for(inti=0;i9;i+)if(0=ci)Zerosign=i;break;if(Zerosign!=0&Zerosign!=1&Zerosign!=2&movea

14、ction!=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=move_left(c,Zerosign);if(Zerosign!=6&Zerosign!=7&Zerosign!=8&moveaction!=u)fn4=move_down(c,Zerosign);f1=zuixiao(fn1,fn2,fn3,fn4);f

15、2=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)move_up(c,Zerosign);moveaction=u;elsemove_right(c,Zerosign);moveaction=r;if(fn1=fn3&fn1=f1)move_up(c,Zerosign);for(i=0;i9;i+)ei=ci;mov

16、e_left(c,Zerosign);for(i=0;i9;i+)fi=ci;if(ceshi(e)ceshi(f)&jingguo(e)move_up(c,Zerosign);moveaction=u;elsemove_left(c,Zerosign);moveaction=l;if(fn1=fn4&fn1=f1)move_up(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);moveactio

17、n=u;elsemove_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)&jingguo(e)move_right(c,Zerosign);moveaction=r;elsemove_left(c,Zerosign);moveaction=l;if(fn2=fn4&fn2=f1)move_right(c,Zerosign);for(i=0;

18、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;elsemove_down(c,Zerosign);moveaction=d;if(fn3=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

19、(c,Zerosign);moveaction=l;elsemove_down(c,Zerosign);moveaction=d;elsebudeng(f1,f2,fn1,fn2,fn3,fn4,Zerosign);intduibi(intc9)/与目标节点比较for(inti=0;i=9)return1;elsereturn0;intcunzaixing(intc9)/得出初始化节点是否存在路径到目标节点intnixu=0,nixu1=0,i,j;for(j=0;j9;j+)for(inti=j+1;ifinali&finalj!=0&finali!=0)nixu+;for(j=0;j9;j

20、+)for(i=j+1;ici&cj!=0&ci!=0)nixu1+;if(nixu%2)-(nixu1%2)=0)return1;elsereturn0;voidmain()/主函数intsd=1;printf(请输入初始结点如(283164705)以空格隔开的九个0到9之间的不重复数:n);for(inti=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);pr

21、intf(第步移动后的矩阵为：n,sd+);show(c);for(inti=0;i(q1-n)-(p1-q1)-(p1-n)函数inite主要作用是负责将符号初始化成树的结构。函数clone复制一棵完全相同的符号树。函数restruct查找所有&,|,等符号，并将其拆分成新形式：！，-符号。函数searching王浩算法的主要函数。函数show和output:显示符号串和推理过程。五.实验结果公式正确_:生茸上生职!帝碣人量证朝翦公,交量行号可由大小写字母和知绷(tlXfllrlplql)-XKdrl化成慈含式：般导造果为=2)(B(9(10(I35C14IE)(1?)(20)pZlQqLp

22、l.pJ.plJqlpjlplQl-Zrl-plrlpl/gl-Apl薪riplrl-ipl-rle*1.q1qi-ri1Pl.观1.rl-rl里1a.l11,*ifl-irlplrl-rlmqlJplbf1位.qLpl-Xql-rl=Fl由3)根网则工再gll=rlpl-qjlpl-Cql-ri,rlnl-qlRjkl-Xal-JrlijIXiil-!,plJrlpl-rl-Cpl-r1-fJ(pl*n1*11=-|1巾根室反II乐1?)柬据次原4圉叱湘揖现妣白门很据视!一日相6根据规贝!I三：根据视剂4TK.实验总结通过本次实验，使我更深入的理解了启发式搜索的原理以及实现，对于其优越性有一

23、定认识，加深了对语法分析以及逻辑公式理解，同时熟练掌握了对树的操作。在编程实现过程中出现过不少问题，通过一次次调试得以解决，并一定程度上提高了我的编程能力,而且让我对人工智能这一课程有了更直接的认知。王浩算法源代码清单：#include#include#include#defineMAXL5inti=0;intstepcount=1;enumtypeand,or,detrusion,equal,level,variable;structnodechar*s;typekind;intpolar;node*next;node*child;intstart;structstepstep*child;

24、step*brother;node*lhead;node*rhead;intcount;charname30;intinite(char*s,node*head)intlen=strlen(s);intj=0,polar=1;node*now=NULL;node*last=NULL;if(s=NULL)return0;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)return0;now=(node*)malloc(sizeof(node);now-kind=or;now-

25、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+;elseif(si=&)if(!(si+1=A|si+1=a)&si+1!=1&si+1!=0&si+1!=(&si+1!=!|i=0)return0;now=(node*)malloc(sizeof(node);now-kind=and;now-s=NULL;now-next=NULL;now-child=N

26、ULL;now-polar=polar;now-start=0;if(last-kind=level&last-child=NULL)last-child=now;elselast-next=now;last=now;i+;elseif(si=!)if(!(si+1=A|si+1=a)&si+1!=1&si+1!=0&si+1!=(&si+1!=!)return0;polar=1-polar;i+;elseif(si=-)if(si+1!=|(si+2!=!&si+2!=(&!(si+2=A|si+2=a)|i=0)return0;now=(node*)malloc(sizeof(node);

27、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;elselast-next=now;last=now;i=i+2;elseif(si=)|(si+3!=!&si+3!=(&!(si+3=A|si+3=a)|i=0)&si+3!=1&si+3!=0)return0;now=(node*)malloc(sizeof(node);now-kind=equal;now-s=NUL

28、L;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;elseif(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(ch

29、ar);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!=T&si!=&si!=-&si!=s)j=0;polar=1;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;i

30、f(last-kind=level&last-child=NULL)last-child=now;elselast-next=now;last=now;i+;elseif(si=()if(!(si+1=A|si+1=a)&si+1!=1&si+1!=0&si+1!=!&si+1!=()return0;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)

31、last-child=now;elselast-next=now;last=now;i+;polar=1;if(!inite(s,last)return0;elseif(si=)if(si+1!=P&si+1!=1&si+1!=0&si+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);elseson-next=NULL;if(parent-child!=NULL)son

32、-child=clone(parent-child);elseson-child=NULL;returnson;voidremove(node*head)node*now=NULL;now=head;if(now=NULL)return;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)n

33、ow-polar=(now-polar=now-child-polar);now-child=now-child-child;if(now-next!=NULL)remove(now-next);if(now-child!=NULL)remove(now-child);voidrestruct(node*head)node*now=NULL;node*last=NULL;node*newone=NULL,*newtwo=NULL,*newthree=NULL,*newfour=NULL,*newnow=NULL;intorder=1;while(orderchild;while(now!=NU

34、LL)if(now-kind=variable|now-kind=level)&order=1)if(now-next!=NULL&now-next-kind=and)newone=(node*)malloc(sizeof(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-n

35、ext;newone-child=now;now-next-next-polar=1-now-next-next-polar;now-next-kind=detrusion;now-next-next-next=NULL;now=newone;elselast=now;now=now-next;elseif(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=leve

36、l;newone-next=NULL;newone-polar=1;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-polar=1-now-polar;now-next-kind=detrusion;now-next-next-next=NULL;now=newone;elselast=now;now=now-next;elseif(now-kind=variable

37、|now-kind=level)&order=3)if(now-next!=NULL&now-next-kind=equal)newone=(node*)malloc(sizeof(node);newone-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;newt

38、wo-s=NULL;newtwo-start=0;newthree=(node*)malloc(sizeof(node);newthree-child=NULL;newthree-kind=detrusion;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;newf

39、our-start=0;if(last-kind=level)last-child=newone;elselast-next=newone;newone-next=now-next-next-next;newone-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-

40、child=newnow-next-next;newnow-next-next-next=newnow-next;newnow-next-next=newnow;newnow-next=NULL;now=newone;elselast=now;now=now-next;elseif(now-kind=level&order=4)restruct(now);last=now;now=now-next;elselast=now;now=now-next;order+;voidshow(node*head)node*now=NULL;now=head;while(now!=NULL)if(now-k

41、ind=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(,);elseif(now-kind=and)printf(&);now=now-next;elseif(now-kind=or)printf(|);now=now-ne

42、xt;elseif(now-kind=detrusion)printf(-);now=now-next;elseif(now-kind=equal)printf();now=now-next;elseif(now-kind=variable)if(now-polar=0)printf(!);printf(%s,now-s);now=now-next;return;intsearching(step*one)node*now=NULL;node*last=NULL;node*newlev=NULL;node*nnow=NULL;node*nlast=NULL;step*nextone=NULL;

43、step*nexttwo=NULL;intkey=0;intmark=0;intre1=1;intre2=1;nextone=(step*)malloc(sizeof(step);nextone-brother=NULL;nextone-child=NULL;nextone-lhead=NULL;nextone-rhead=clone(one-rhead);nextone-lhead=clone(one-lhead);strcpy(nextone-name,);one-child=nextone;now=nextone-rhead;last=now;while(now!=NULL)if(now

44、-polar=0)if(now=nextone-rhead)nextone-rhead=now-next;elselast-next=now-next;now-next=NULL;remove(now);now-next=nextone-lhead;nextone-lhead=now;now-polar=1-now-polar;now-start=1;now=last-next;strcpy(one-name,根据规则1);mark=1;key=1;break;elseif(now-child-next!=NULL&now-child-next-kind=detrusion)nlast=now

45、-child;nnow=now-child-next;while(nnow-next-next!=NULL&nnow-next-next-kind=detrusion)nlast=nnow-next;nnow=nnow-next-next;now-polar=1-now-polar;newlev=(node*)malloc(sizeof(node);newlev-child=nnow-next;newlev-kind=level;newlev-polar=1;newlev-next=NULL;newlev-start=1;nlast-next=NULL;remove(newlev);newlev-next=now-next;now-next=NULL;remove(now);now-next=newlev;strcpy(one-name,根据规则4);mark=1;key=1;break;elselast=now;now=now-nex