人工智能实验报告标准化文件发布号：（9312-EUATWW-MWUB-WUNN-INNUL-DQQTY-****大学人工智能基础课程实验报告（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数码问题的效率差别，给出一个是()p n 的上界的()h n 的定义，并测试使用该估价函数是否使算法失去可采纳性。

2. 实验目的熟练掌握启发式搜索A *算法及其可采纳性。

3. 实验原理使用启发式信息知道搜索过程，可以在较大的程度上提高搜索算法的时间效率和空间效率；启发式搜索的效率在于启发式函数的优劣，在启发式函数构造不好的情况下，甚至在存在解的情形下也可能导致解丢失的现象或者找不到最优解，所以构造一个优秀的启发式函数是前提条件。

4.实验内容1.问题描述在一个3*3的九宫格 里有1至8 八个数以及一个空格随机摆放在格子中，如下图：初始状态 目标状态现需将图一转化为图二的目标状态，调整的规则为：每次只能将空格与其相邻的一个数字进行交换。

实质是要求给出一个合法的移动步骤，实现从初始状态到目标状态的转变。

2.算法分析(1)解存在性的讨论对于任意的一个初始状态，是否有解可通过线性代数的有关理论证明。

按数组存储后，算出初始状态的逆序数和目标状态的逆序数，若两者的奇偶性一致，则表明有解。

（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.若不是目标节点则进行扩展，生成其全部后继节点。

c.对于每个后继节点均求其f(n),并比较。

d.将最小f(n)存入正确路径，并与目标节点进行对比。

e.若不是目标节点则循环执行b，若是目标节点则输出5实验结果输入输出：源代码如下：#include<>int final[9]={1,2,3,8,0,4,7,6,5};实验内容：实现命题逻辑框架内的王浩算法。

⑴将命题逻辑中的王浩算法推广至下述命题语言的情形之下:ⅰ命题变量符号：1p，2p，3p，ⅱ逻辑连接符：⌝，∧，∨，→，↔ⅲ间隔符：(，)⑵在上述⑴中所定义的命题语言中实现王浩算法。

2. 实验目的熟练掌握命题逻辑中的王浩算法。

3. 实验要求⑴实验题目必须由个人独立完成，允许自行参考相关文献资料，但严禁同学间相互拷贝和抄袭程序以及文档资料。

实验结束后一周内上交实验报告和实验文档资料。

⑵提交的文档资料包括设计文档和程序源代码。

设计文档和程序源代码以书面文档方式提供（用4A纸打印）；并提交电子文档备查。

四．数据结构给定公式，例如：(p1->(q1->r1))->((p1->q1)->(p1->r1))函数inite主要作用是负责将符号初始化成树的结构。

函数clone复制一棵完全相同的符号树。

函数restruct查找所有&，|， <->等符号，并将其拆分成新形式：！，->符号。

函数searching王浩算法的主要函数。

函数show和output:显示符号串和推理过程。

五．实验结果公式正确六．实验总结通过本次实验，使我更深入的理解了启发式搜索的原理以及实现，对于其优越性有一定认识，加深了对语法分析以及逻辑公式理解，同时熟练掌握了对树的操作。

在编程实现过程中出现过不少问题，通过一次次调试得以解决，并一定程度上提高了我的编程能力，而且让我对人工智能这一课程有了更直接的认知。

王浩算法源代码清单：#include<>#include<>#include<>#define MAX_L 5int i=0;int stepcount=1;enum type{and,or,detrusion,equal,level,variable};struct node{char *s;type kind;int polar;node *next;node *child;int start;};struct step{step *child;step *brother;node *lhead;node *rhead;int count;char name[30];}; 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(s[i]=='|'){if(!(s[i+1]<='Z'&&s[i+1]>='A'||s[i+1]<='z'&&s[i+1]>='a')&&s[i+1]!='1'&&s[i+1]!='0'&&s [i+1]!='('&&s[i+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;}else{last->next=now;}last=now;i++;}else if(s[i]=='&'){if(!(s[i+1]<='Z'&&s[i+1]>='A'||s[i+1]<='z'&&s[i+1]>='a')&&s[i+1]!='1'&&s[i+1]!='0'&&s [i+1]!='('&&s[i+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;}else{last->next=now;}last=now;i++;}else if(s[i]=='!'){if(!(s[i+1]<='Z'&&s[i+1]>='A'||s[i+1]<='z'&&s[i+1]>='a')&&s[i+1]!='1'&&s[i+1]!='0'&&s [i+1]!='('&&s[i+1]!='!')return 0;polar=1-polar;i++;}else if(s[i]=='-'){if(s[i+1]!='>'||(s[i+2]!='!'&&s[i+2]!='('&&!(s[i+2]<='Z'&&s[i+2]>='A'||s[i+2]<='z'&&s[i+ 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;}else{last->next=now;}last=now;i=i+2;}else if(s[i]=='<'){ if((s[i+1]!='-'||s[i+2]!='>')||(s[i+3]!='!'&&s[i+3]!='('&&!(s[i+3]<='Z'&&s[i+3]>='A'||s[i+3]<='z'&&s[i+3]>='a ')||i==0)&&s[i+3]!='1'&&s[i+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;}else{last->next=now;}last=now;i=i+3;}else if(s[i]<='Z'&&s[i]>='A'||s[i]<='z'&&s[i]>='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;}else{last->next=now;}last=now;j=0;while((s[i]<='Z'&&s[i]>='A'||s[i]<='z'&&s[i]>='a')||(s[i]<='9'&&s[i]>='0'))(now->s)[j]=s[i];i++;j++;}if(s[i]!='|'&&s[i]!='&'&&s[i]!='-'&&s[i]!='<'&&s[i]!='\0'&&s[i]!=')')return 0;(now->s)[j]='\0';polar=1;}else if(s[i]=='1'||s[i]=='0'){if(s[i+1]!='<'&&s[i+1]!='-'&&s[i+1]!='&'&&s[i+1]!='|'&&s[i+1]!=')'&&s[i+1]!='\0')return 0;now=(node*)malloc(sizeof(node));now->kind=equal;now->s=(char*)malloc(2*sizeof(char));(now->s)[0]=s[i];(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;}else{last->next=now;}last=now;i++;}else if(s[i]=='('){if(!(s[i+1]<='Z'&&s[i+1]>='A'||s[i+1]<='z'&&s[i+1]>='a')&&s[i+1]!='1'&&s[i+1]!='0'&&s [i+1]!='!'&&s[i+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;}else{last->next=now;}last=now;i++;polar=1;if(!inite(s,last))return 0;}else if(s[i]==')'){if(s[i+1]!='P'&&s[i+1]!='1'&&s[i+1]!='0'&&s[i+1]!='-'&&s[i+1]!='<'&&s[i+1]!='&'&&s[i+1]!='|'&&s[i+1]!='\0'&&s[i+1]!=')')return 0;i++;return 1;}else return 0;}return 1;}node* clone(node *parent){node *son=NULL;if(parent==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(parent->child);else son->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(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* head){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){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;else last->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=NULL;now=newone;}else{last=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;else last->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;}else{last=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=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;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; else last->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->child=newnow->next->next;newnow->next->next->next=newnow->next;newnow->next->next=newnow;newnow->next=NULL;now=newone;}else{last=now;now=now->next;}}else if(now->kind==level&&order==4){restruct(now);last=now;now=now->next;}else{last=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){printf("|");now=now->next;}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 *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->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->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->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;last=now;now=now->next;}}now=nextone->lhead;last=now;while(now!=NULL&&key!=1){if(now->polar==0){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 if(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,"");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=now;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;}else{newlev->next=now->next;last->next=newlev;}remove(newlev);nextone->brother=nexttwo;strcpy(one->name,"根据规则3");mark=1;key=1;break;}else{last=now;now=now->next;}}if(mark==0){one->child=NULL;now=one->lhead;nnow=one->rhead;while(now!=NULL){nnow=one->rhead;while(nnow!=NULL){if(!strcmp(now->child->s,nnow->child->s))break;nnow=nnow->next;}if(nnow!=NULL)break;now=now->next;}if(now==NULL)return 0;elsereturn 1;}re1=searching(nextone);if(nextone->brother!=NULL)re2=searching(nextone->brother);if(re1&&re2)return 1;elsereturn 0;}void output(step *one){if(one->child!=NULL)output(one->child);if(one->brother!=NULL)output(one->brother);one->count=stepcount;stepcount++;printf("(%d) ",one->count);show(one->lhead);printf("=>");show(one->rhead);printf(" ");if(one->child!=NULL&&one->child->brother==NULL)printf("由(%d)",one->child->count);else if(one->child!=NULL&&one->child->brother!=NULL)printf("由(%d)(%d)",one->child->count,one->child->brother->count);else printf("公理");puts(one->name);return;}void main(){char s[100];node head;step one;=NULL;=level;=NULL;=1;=NULL;=1;=NULL;=NULL;=NULL;=&head;puts("王浩算法推理器");while(1){puts("请输入要证明的公式，变量符号可由大小写字母和数字组成:");scanf("%s",s);if(inite(s,&head)){puts("\n化成蕴含式:");restruct(&head);remove(&head);show(&head);putchar('\n');if(searching(&one)){puts("推导结果为:");output(&one);break;}else {puts("无法推导出公式");break;}}else puts("输入的公式语法有错误");getchar();}}。