人工智能实验报告.docx

人工智能实验报告.docx

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

人工智能实验报告

****大学

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

（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};//目标状态节点

inta[1000][9],c[9],e[9],f[9];//路径节点和扩展节点

intdeep=1,fn;//深度和估计值

intb[9];

charmoveaction;//移动方向

intfnjisuan（intb[9]）//估价函数

{

intcompare=0,s=0,fn1,d[9];

d[0]=b[0];d[1]=b[1];d[2]=b[2];d[3]=b[5];d[4]=b[8];d[5]=b[7];d[6]=b[6];d[7]=b[3];d[8]=b[4];

for（inti=0;i<9;i++）

{

if（b[i]!

=final[i]&&i!

=4）compare++;

}for（i=0;i<7;i++）if（（d[i+1]-d[i]）!

=1）s++;

fn1=2*compare+3*s+deep;//估价函数计算结果

returnfn1;

}

voidshow（intc[9]）//输出节点

{

for（inti=0;i<9;i++）a[deep][i]=c[i];

for（i=0;i<9;i++）{

if（（i）%3==0）printf（"\n"）;

printf（"%d\t",c[i]）;

}

deep++;

printf（"\n"）;

}

intjingguo（inte[9]）//测试当前节点是否已经经过避免回溯

{

for（inti=0;i

{

intk=0;

for（intj=0;j<9;j++）

if（e[j]==a[i][j]）k++;

if（k==9）return0;

}return1;

}

intmove_up（intc[9],intZerosign）//上移操作

{

for（inti=0;i<9;i++）c[i]=b[i];

c[Zerosign]=c[Zerosign-3];

c[Zerosign-3]=0;

intfn1=fnjisuan（c）;

returnfn1;

}

intmove_down（intc[9],intZerosign）//下移操作

{

for（inti=0;i<9;i++）c[i]=b[i];

c[Zerosign]=c[Zerosign+3];

c[Zerosign+3]=0;

intfn1=fnjisuan（c）;

returnfn1;

}

intmove_left（intc[9],intZerosign）//左移操作

{

for（inti=0;i<9;i++）c[i]=b[i];

c[Zerosign]=c[Zerosign-1];

c[Zerosign-1]=0;

intfn1=fnjisuan（c）;

returnfn1;

}

intmove_right（intc[9],intZerosign）//右移操作

{

for（inti=0;i<9;i++）c[i]=b[i];

c[Zerosign]=c[Zerosign+1];

c[Zerosign+1]=0;

intfn1=fnjisuan（c）;

returnfn1;

}

intzuixiao（intfn1,intfn2,intfn3,intfn4）//求最小值

{

intf1,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=（fn1<=fn2）?

fn1:

fn2;

f3=（fn1>fn2）?

fn1:

fn2;

f2=（fn3<=fn4）?

fn3:

fn4;

f4=（fn1>fn2）?

fn1:

fn2;

if（f1<=f2）

{

if（f3<=f2）returnf3;

elsereturnf2;

}

elseif（f4<=f1）returnf4;

elsereturnf1;

}

voidbudeng（intf1,intf2,intfn1,intfn2,intfn3,intfn4,intZerosign）//处理估价函数最小值唯一的时候

{

if（f1==fn1）

{

if（moveaction!

='d'&&jingguo（c））

{move_up（c,Zerosign）;moveaction='u';}

else

{

if（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,Zerosign）;moveaction='r';}

else{

if（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';}

else{

if（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';}

else{

if（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（intk[9]）//测试估价函数

{

intfn1=100,fn2=100,fn3=100,fn4=100,f1,Zerosign;

for（inti=0;i<9;i++）

if（0==k[i]）{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=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（intc[9]）//确定移动方向

{

intfn1=100,fn2=100,fn3=100,fn4=100,f1,f2,Zerosign;

for（inti=0;i<9;i++）

if（0==c[i]）{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=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;i<9;i++）e[i]=c[i];

move_right（c,Zerosign）;

for（i=0;i<9;i++）f[i]=c[i];

if（（ceshi（e）

else{move_right（c,Zerosign）;moveaction='r';}

}

if（fn1==fn3&&fn1==f1）

{

move_up（c,Zerosign）;

for（i=0;i<9;i++）e[i]=c[i];

move_left（c,Zerosign）;

for（i=0;i<9;i++）f[i]=c[i];

if（（ceshi（e）

else{move_left（c,Zerosign）;moveaction='l';}

}

if（fn1==fn4&&fn1==f1）

{

move_up（c,Zerosign）;

for（i=0;i<9;i++）e[i]=c[i];

move_down（c,Zerosign）;

for（i=0;i<9;i++）f[i]=c[i];

if（（ceshi（e）

else{move_down（c,Zerosign）;moveaction='d';}

}

if（fn2==fn3&&fn2==f1）

{

move_right（c,Zerosign）;

for（i=0;i<9;i++）e[i]=c[i];

move_left（c,Zerosign）;

for（i=0;i<9;i++）f[i]=c[i];

if（（ceshi（e）

else{move_left（c,Zerosign）;moveaction='l';}

}

if（fn2==fn4&&fn2==f1）

{

move_right（c,Zerosign）;

for（i=0;i<9;i++）e[i]=c[i];

move_down（c,Zerosign）;

for（i=0;i<9;i++）f[i]=c[i];

if（（ceshi（e）

else{move_down（c,Zerosign）;moveaction='d';}

}

if（fn3==fn4&&fn3==f1）

{

move_left（c,Zerosign）;

for（i=0;i<9;i++）e[i]=c[i];

move_down（c,Zerosign）;

for（i=0;i<9;i++）f[i]=c[i];

if（（ceshi（e）

else{move_down（c,Zerosign）;moveaction='d';}

}

}

elsebudeng（f1,f2,fn1,fn2,fn3,fn4,Zerosign）;

}

intduibi（intc[9]）{//与目标节点比较

for（inti=0;i<9;i++）

if（c[i]!

=final[i]）

break;

if（i>=9）return1;

elsereturn0;

}

intcunzaixing（intc[9]）{//得出初始化节点是否存在路径到目标节点

intnixu=0,nixu1=0,i,j;

for（j=0;j<9;j++）

for（inti=j+1;i<9;i++）

if（final[j]>final[i]&&final[j]!

=0&&final[i]!

=0）nixu++;

for（j=0;j<9;j++）

for（i=j+1;i<9;i++）

if（c[j]>c[i]&&c[j]!

=0&&c[i]!

=0）nixu1++;

if（（nixu%2）-（nixu1%2）==0）

return1;

elsereturn0;

}

voidmain（）{//主函数

intsd=1;

printf（"请输入初始结点如（283164705）以空格隔开的九个0到9之间的不重复数:

\n"）;

for（inti=0;i<9;i++）

{

scanf（"%d",&b[i]）;

c[i]=b[i];

}printf（"您输入的初始矩阵为：

\n"）;

show（c）;

deep--;

if（cunzaixing（c）==0）

printf（"此矩阵不存在路径至目标矩阵！

\n"）;

else{

while（!

duibi（c）&&deep<100）{

move（c）;

printf（"第%d步移动后的矩阵为：

\n",sd++）;show（c）;

for（inti=0;i<9;i++）b[i]=c[i];}

}

}

实验二王浩算法的实现

1.实验内容：

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

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

ⅰ命题变量符号：

，

，

，

ⅱ逻辑连接符：

，

，

，

，

ⅲ间隔符：

，

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

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