人工智能实验报告.docx

人工智能实验报告.docx

《人工智能实验报告.docx》由会员分享，可在线阅读，更多相关《人工智能实验报告.docx（27页珍藏版）》请在冰点文库上搜索。

人工智能实验报告

****大学

人工智能基础课程实验报告

（2011-2012学年第一学期）

启发式搜索王浩算法

班级：

***********

学号：

**********

姓名：

******

指导教师：

******

成绩：

2012年1月10日

实验一启发式搜索算法

1.实验内容：

使用启发式搜索算法求解8数码问题。

⑴编制程序实现求解8数码问题

算法，采用估价函数

，

其中：

是搜索树中结点

的深度；

为结点

的数据库中错放的棋子个数；

为结点

的数据库中每个棋子与其目标位置之间的距离总和。

⑵分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是

的上界的

的定义，并测试使用该估价函数是否使算法失去可采纳性。

2.实验目的

熟练掌握启发式搜索

算法及其可采纳性。

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<>

intfinal[9]={1,2,3,8,0,4,7,6,5};实验内容：

实现命题逻辑框架内的王浩算法。

⑴将命题逻辑中的王浩算法推广至下述命题语言的情形之下:

ⅰ命题变量符号：

，

，

，

ⅱ逻辑连接符：

，

，

，

，

ⅲ间隔符：

，

⑵在上述⑴中所定义的命题语言中实现王浩算法。

2.实验目的

熟练掌握命题逻辑中的王浩算法。

3.实验要求

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

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

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

设计文档和程序源代码以书面文档方式提供（用

纸打印）；并提交电子文档备查。

四．数据结构

给定公式，例如：

（p1->（q1->r1））->（（p1->q1）->（p1->r1））

函数inite主要作用是负责将符号初始化成树的结构。

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

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

！

，->符号。

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

函数show和output:

显示符号串和推理过程。

五．实验结果

公式正确

六．实验总结

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

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

王浩算法源代码清单：

#include<>

#include<>

#include<>

#defineMAX_L5

inti=0;

intstepcount=1;

enumtype{and,or,detrusion,equal,level,variable};

structnode{char*s;typekind;intpolar;node*next;node*child;intstart;};

structstep{step*child;step*brother;node*lhead;node*rhead;intcount;charname[30];};

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（i

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）return0;

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++;

}elseif（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）

return0;

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++;

}elseif（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]!

='!

'）

return0;

polar=1-polar;

i++;

}elseif（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）

return0;

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;

}elseif（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'）

return0;

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;

}elseif（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]!

='）'）

return0;

（now->s）[j]='\0';

polar=1;

}elseif（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'）

return0;

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++;

}elseif（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]!

='（'）

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）{

last->child=now;

}else{

last->next=now;

}last=now;

i++;

polar=1;

if（!

inite（s,last））return0;

}elseif（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]!

='）'）

return0;

i++;

return1;

}elsereturn0;

}return1;

}

node*clone（node*parent）{

node*son=NULL;

if（parent==NULL）returnNULL;

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）;

elseson->next=NULL;

if（parent->child!

=NULL）son->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）{

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）;

}

voidrestruct（node*head）{

node*now=NULL;

node*last=NULL;

node*newone=NULL,*newtwo=NULL,*newthree=NULL,*newfour=NULL,*newnow=NULL;

intorder=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;

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=NULL;

now=newone;

}else{

last=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=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-now->polar;

now->next->kind=detrusion;

now->next->next->next=NULL;

now=newone;

}else{

last=now;

now=now->next;

}

}elseif（（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;

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->child=newnow->next->next;

newnow->next->next->next=newnow->next;

newnow->next->next=newnow;

newnow->next=NULL;