人工智能实验报告

人工智能实验报告

标准化文件发布号：（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 5

int 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

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;