人工智能实验报告

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

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

4、解的存在性，并与目标节点对比。b. 若不是目标节点则进行扩展，生成其全部后继节点。c. 对于每个后继节点均求其 f(n),并比较。d.将最小f(n)存入正确路径，并与目标节点进行对比。e.若不是目标节点则循环执行b,若是目标节点则输出5实验结果输入输出:源代码如下:#include<>int final9=1,2,3,8,0,4,7,6,5;实验内容：实现命题逻辑框架内的王浩算法。 将命题逻辑中的王浩算法推广至下述命题语言的情形之下:i命题变量符号：pl, p2, p3, Lii逻辑连接符： ，iii间隔符：(,) 在上述中所定义的命题语言中实现王浩算法。2. 实验目的熟练掌握命题

5、逻辑中的王浩算法。3. 实验要求 实验题目必须由个人独立完成，允许自行参考相关文献资料，但严禁同学间相互拷贝和抄袭程序以及文档资料。实验结束后一周内上交实验报告和实验文档资料。 提交的文档资料包括设计文档和程序源代码。设计文档和程序源代码以书面文档方式提供(用A4纸打印)；并提交电子文档备查。四数据结构给定公式，例如：(p1->(q1->r1)->(p1->q1)->(p1->r1)函数inite 主要作用是负责将符号初始化成树的结构。函数clone 复制一棵完全相同的符号树。函数 restruct 查找所有&， | ，<-> 等符号，并

6、将其拆分成新形式：！ ， -> 符号。函数searching王浩算法的主要函数。函数show和output:显示符号串和推理过程。五实验结果 公式正确奈曙入里证朗的公式，变量符号可由大小写字母和知绷 (t>l Xfll >rl>>K&l >rl»化成这含式；<pl - XqI - >rl > > - >< <pl ->q1 J-Xjrt->r1 »指导结果为二.一Cl >公理Q公理<3>会理pl口根嘱期则之<5>由外。根配现则plpf pl&quo

7、t;>>L»rl口艮市和21P1 .U17-rl由，G既稀据规则3(B>.翎<?>e(1 v<1.ri公理(10>1Pl 超1 . r 1 - >rl合理<li>. 1 .Ul, * y.1三门艰苑.现则芝<I2>1rd .uLqin ->!*!3(I35pl由限壶司则工C14>plql.a<15>It小7。根居规见必(16，Fpl-Xeil->rl? =>rl1:pl->q1,>->!pl,rlEMiG根十<1U>igl ->di P pl

8、 - > <al->rl > = >pl - >r 1L14ijI(iii Jrl >->!>白立甘艰揖翅妣.(20)id 一413rl>Cyl >M>水1啡据观贝4<21>->f Cljl.-Xgl->!*! J »,<pl ->q1>.据规以1(23!>=><pl(ql1 >>=><<pt-><|1-由g根据8初TK.实验总结通过本次实验，使我更深入的理解了启发式搜索的原理以及实现，对于其优越性有一定认识，加

9、深了对语法分析以及逻辑公式理解，同时熟练掌握了对树的操作。在编程实现过程中出现过不少问题，通过一次次调试得以解决，并一定程度上提高了我的编程能力,而且让我对人工智能这一课程有了更直接的认知。王浩算法源代码清单：#include<> #include<>#include<>#define MAX_L 5 int i=0;int stepcount=1;enum typeand,or,detrusion,equal,level,variable;struct nodechar *s;type kind;int polar;node *next;node *chi

10、ld;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)return 0;last=head;while(i<len)if(si='|')if(!(si+1<=Z&&si+1>='A'|si+

11、1<='z'&&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->st

12、art=0;if(last->kind=level&&last->child=NULL)last->child=now;elselast->next=now;last=now;i+;else if(si='&')if(!(si+1<='Z'&&si+1>='A'|si+1<='z'&&si+1>='a')&&si+1!='1'&&si+1!='0'

13、&&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;las

14、t=now;i+;else if(si='!')if(!(si+1<=Z&&si+1>='A'|si+1<='z'&&si+1>='a')&&si+1!='1'&&si+1!='0'&&si+1!='('&&si+1!='!')return 0;polar=1-polar;i+;else if(si='-')if(si+1!='

15、;>'|(si+2!='!'&&si+2!='('&&!(si+2<=Z&&si+2>='A'|si+2<='z'&&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;

16、now->start=0;if(last->kind=level&&last->child=NULL)last->child=now;elselast->next=now;last=now;i=i+2;else if(si='<')if(si+1!='-'|si+2!='>')|(si+3!='!'&&si+3!='('&&!(si+3<=Z&&si+3>='A'|si+3<=

17、'z'&&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

18、)last->child=now;elselast->next=now;last=now;i=i+3;else if(si<=Z&&si>='A'|si<='z'&&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(M

19、AX_L*sizeof(char);if(last->kind=level&&last->child=NULL)last->child=now;elselast->next=now;last=now;j=0;while(si<=Z&&si>='A'|si<='z'&&si>='a')|(si<='9'&&si>='0')(now->s)j=si;i+;j+;if(si!=T&&a

20、mp;si!=&&&si!='-'&&si!='<'&&si!='0'&&si!=')')return 0;(now->s)j='0'polar=1;else if(si='1'|si='0')if(si+1!='<'&&si+1!='-'&&si+1!=&&&si+1!=T&&si+1!=&

21、#39;)'&&si+1!='0')return 0;now=(node*)malloc(sizeof(node);now->kind=equal;(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=n

22、ow;last=now;i+;else if(si='(')if(!(si+1<='Z'&&si+1>='A'|si+1<='z'&&si+1>='a')&&si+1!='1'&&si+1!='0'&&si+1!='!'&&si+1!='(')return 0;now=(node*)malloc(sizeof(node);now-&g

23、t;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!=&

24、#39;1'&&si+1!='0'&&si+1!='-'&&si+1!='<'&&si+1!='&'&&si+1!='|'&&si+1!='0'&&si+1!=')')return 0;i+;return 1;else return 0;return 1;node* clone(node *parent)node *son=NULL;if(parent

25、=NULL)return NULL;son=(node*)malloc(sizeof(node);son->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(paren

26、t->child);elseson->child=NULL;return son;)void remove(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

27、(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!=NULL)remove(now->child);)void restruct(node* hea

28、d)node *now=NULL;node *last=NULL;node *newone=NULL,*newtwo=NULL,*newthree=NULL,*newfour=NULL,*newnow=NULL;int order=1;while(order<=4)last=head;now=last->child;while(now!=NULL)if(now->kind=variable|now->kind=level)&&order=1)if(now->next!=NULL&&now->next->kind=and)

29、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->next;newone->child=now;now->

30、;next->next->polar=1-now->next->next->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=2)if(now->next!=NULL&&now->next->kind=or)newone=(n

31、ode*)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;elselast->next=newone;newone->next=now->next->next->next;newone->child=now;now->polar=1-

32、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->child=

33、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);newth

34、ree->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;newfour->start=0;if(las

35、t->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;new

36、now=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=newone;elselast=now;now=now->next;else if(now->kind=level&&order=4)restruct(now);last=

37、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);i

38、f(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)printf("|");now=now->ne

39、xt;else if(now->kind=detrusion)printf("->");now=now->next;else if(now->kind=equal)printf("<->");now=now->next;else if(now->kind=variable)if(now->polar=0)printf("!");printf("%s",now->s);now=now->next;return; int searching(step *

40、one)node *now=NULL;node *last=NULL;node *newlev=NULL;node *nnow=NULL;node *nlast=NULL;step *nextone=NULL;step *nexttwo=NULL;int key=0;int mark=0;int re1=1;int re2=1;nextone=(step*)malloc(sizeof(step);nextone->brother=NULL;nextone->child=NULL;nextone->lhead=NULL;nextone->rhead=clone(one-&

41、gt;rhead);nextone->lhead=clone(one->lhead);strcpy(nextone->name,"");one->child=nextone;now=nextone->rhead;last=now;while(now!=NULL)if(now->polar=0)if(now=nextone->rhead)nextone->rhead=now->next;else last->next=now->next;now->next=NULL;remove(now);now->

42、;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;else if(now->child->next!=NULL&&now->child->next->kind=detrusion)nlast=now->child;nnow=now->child->

43、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;newl

44、ev->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->next;now=nextone->lhead;last=now;while(now!=NULL&&key!=1)if(now->polar=0)

45、if(now=nextone->lhead)nextone->lhead=now->next;else last->next=now->next;now->next=NULL;remove(now);now->next=nextone->rhead;nextone->rhead=now;now->polar=1-now->polar;now->start=1;now=last->next;strcpy(one->name," 根据规则2");mark=1;key=1;break;else i

46、f(now->child->next!=NULL&&now->child->next->kind=detrusion)nexttwo=(step*)malloc(sizeof(step);nexttwo->brother=NULL;nexttwo->child=NULL;nexttwo->lhead=NULL;nexttwo->rhead=clone(nextone->rhead);nexttwo->lhead=clone(nextone->lhead);strcpy(nexttwo->name,&q

47、uot;");nlast=now->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;now->start=1;nlast->next=NULL;remove(now);now=nexttwo->lhead;last=n

48、ow;while(now->child->next=NULL|now->child->next->kind!=detrusion)last=now;now=now->next;nlast=now->child;nnow=now->child->next;while(nnow->next->next!=NULL&&nnow->next->next->kind=detrusion) nlast=nnow->next;nnow=nnow->next->next;newlev=(node*)malloc(sizeof(node);newlev->child=nnow->next;newlev->kind=level;newlev->polar=1;newlev->next=NULL;newlev->start=1;nlast->next=NULL;if(now=nexttwo->lhead)newlev->next=now->next;nexttwo->lhead=newlev;elsenewlev->next=now->next;last-&