人工智能实验报告Word格式文档下载.docx
《人工智能实验报告Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《人工智能实验报告Word格式文档下载.docx（38页珍藏版）》请在冰点文库上搜索。
实质是要求给出一个合法的移动步骤，实现从初始状态到目标状态的转变。
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<
stdio.h>
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;
7;
i++）if（（d[i+1]-d[i]）!
=1）s++;
fn1=2*compare+3*s+deep;
//估价函数计算结果
returnfn1;
}
voidshow（intc[9]）//输出节点
i++）a[deep][i]=c[i];
for（i=0;
i++）{
if（（i）%3==0）printf（"
\n"
）;
printf（"
%d\t"
c[i]）;
}
deep++;
printf（"
intjingguo（inte[9]）//测试当前节点是否已经经过避免回溯
deep;
intk=0;
for（intj=0;
j<
j++）
if（e[j]==a[i][j]）k++;
if（k==9）return0;
}return1;
intmove_up（intc[9],intZerosign）//上移操作
i++）c[i]=b[i];
c[Zerosign]=c[Zerosign-3];
c[Zerosign-3]=0;
intfn1=fnjisuan（c）;
intmove_down（intc[9],intZerosign）//下移操作
c[Zerosign]=c[Zerosign+3];
c[Zerosign+3]=0;
intmove_left（intc[9],intZerosign）//左移操作
c[Zerosign]=c[Zerosign-1];
c[Zerosign-1]=0;
intmove_right（intc[9],intZerosign）//右移操作
c[Zerosign]=c[Zerosign+1];
c[Zerosign+1]=0;
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;
f3=（fn1>
fn2）?
f4=（fn1>
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）;
r'
if（f2==fn3）{move_left（c,Zerosign）;
l'
if（f2==fn4）{move_down（c,Zerosign）;
if（f1==fn2）
jingguo（c））{move_right（c,Zerosign）;
else{
if（f2==fn1）{move_up（c,Zerosign）;
if（f1==fn3）
jingguo（c））{move_left（c,Zerosign）;
if（f1==fn4）
jingguo（c））{move_down（c,Zerosign）;
intceshi（intk[9]）//测试估价函数
intfn1=100,fn2=100,fn3=100,fn4=100,f1,Zerosign;
if（0==k[i]）{Zerosign=i;
break;
if（Zerosign!
=0&
Zerosign!
=1&
=2&
moveaction!
fn1=move_up（c,Zerosign）;
=5&
=8&
fn2=move_right（c,Zerosign）;
=3&
=6&
fn3=move_left（c,Zerosign）;
=7&
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;
if（0==c[i]）{Zerosign=i;
f2=cixiao（fn1,fn2,fn3,fn4）;
if（f1==f2）
{
if（fn1==fn2&
fn1==f1）
move_up（c,Zerosign）;
for（i=0;
i++）e[i]=c[i];
move_right（c,Zerosign）;
i++）f[i]=c[i];
if（（ceshi（e）<
ceshi（f））&
jingguo（e））{move_up（c,Zerosign）;
else{move_right（c,Zerosign）;
if（fn1==fn3&
{
move_up（c,Zerosign）;
for（i=0;
move_left（c,Zerosign）;
if（（ceshi（e）<
else{move_left（c,Zerosign）;
}
if（fn1==fn4&
{
move_up（c,Zerosign）;
for（i=0;
move_down（c,Zerosign）;
if（（ceshi（e）<
else{move_down（c,Zerosign）;
}
if（fn2==fn3&
fn2==f1）
{
move_right（c,Zerosign）;
for（i=0;
move_left（c,Zerosign）;
if（（ceshi（e）<
jingguo（e））{move_right（c,Zerosign）;
else{move_left（c,Zerosign）;
}
if（fn2==fn4&
{
move_right（c,Zerosign）;
for（i=0;
move_down（c,Zerosign）;
if（（ceshi（e）<
else{move_down（c,Zerosign）;
}
if（fn3==fn4&
fn3==f1）
{
move_left（c,Zerosign）;
for（i=0;
move_down（c,Zerosign）;
if（（ceshi（e）<
jingguo（e））{move_left（c,Zerosign）;
else{move_down（c,Zerosign）;
}
elsebudeng（f1,f2,fn1,fn2,fn3,fn4,Zerosign）;
intduibi（intc[9]）{//与目标节点比较
if（c[i]!
=final[i]）
break;
if（i>
=9）return1;
elsereturn0;
intcunzaixing（intc[9]）{//得出初始化节点是否存在路径到目标节点
intnixu=0,nixu1=0,i,j;
for（j=0;
for（inti=j+1;
if（final[j]>
final[i]&
final[j]!
final[i]!
=0）nixu++;
for（j=0;
for（i=j+1;
if（c[j]>
c[i]&
c[j]!
c[i]!
=0）nixu1++;
if（（nixu%2）-（nixu1%2）==0）
return1;
voidmain（）{//主函数
intsd=1;
请输入初始结点如（283164705）以空格隔开的九个0到9之间的不重复数:
\n"
scanf（"
%d"
&
b[i]）;
c[i]=b[i];
}printf（"
您输入的初始矩阵为：
show（c）;
deep--;
if（cunzaixing（c）==0）
此矩阵不存在路径至目标矩阵！
else{
while（!
duibi（c）&
deep<
100）{
move（c）;
printf（"
第%d步移动后的矩阵为：
sd++）;
show（c）;
for（inti=0;
i++）b[i]=c[i];
实验二王浩算法的实现
实现命题逻辑框架内的王浩算法。
⑴将命题逻辑中的王浩算法推广至下述命题语言的情形之下:
ⅰ命题变量符号：
ⅱ逻辑连接符：
ⅲ间隔符：
⑵在上述⑴中所定义的命题语言中实现王浩算法。
熟练掌握命题逻辑中的王浩算法。
3.实验要求
⑴实验题目必须由个人独立完成，允许自行参考相关文献资料，但严禁同学间相互拷贝和抄袭程序以及文档资料。
实验结束后一周内上交实验报告和实验文档资料。
⑵提交的文档资料包括设计文档和程序源代码。
设计文档和程序源代码以书面文档方式提供（用
纸打印）；
并提交电子文档备查。
四．数据结构
给定公式，例如：
（p1->
（q1->
r1））->
（（p1->
q1）->
r1））
函数inite主要作用是负责将符号初始化成树的结构。
函数clone复制一棵完全相同的符号树。
函数restruct查找所有&
，|，<
->
等符号，并将其拆分成新形式：
！
，->
符号。
函数searching王浩算法的主要函数。
函数show和output:
显示符号串和推理过程。
五．实验结果
公式正确
六．实验总结
通过本次实验，使我更深入的理解了启发式搜索的原理以及实现，对于其优越性有一定认识，加深了对语法分析以及逻辑公式理解，同时熟练掌握了对树的操作。
在编程实现过程中出现过不少问题，通过一次次调试得以解决，并一定程度上提高了我的编程能力，而且让我对人工智能这一课程有了更直接的认知。
王浩算法源代码清单：
stdlib.h>
string.h>
#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<
len）{
if（s[i]=='
|'
）{if（!
（s[i+1]<
Z'
s[i+1]>
A'
||s[i+1]<
z'
a'
）&
s[i+1]!
1'
0'
（'
!
'
||i==0）return0;
now=（node*）malloc（sizeof（node））;
now->
kind=or;
s=NULL;
next=NULL;
child=NULL;
polar=polar;
start=0;
if（last->
kind==level&
last->
child==NULL）{
last->
child=now;
}else{last->
next=now;
last=now;
i++;
}elseif（s[i]=='
）{
if（!
||i==0）
return0;
now=（node*）malloc（sizeof（node））;
now
升级会员 