文档介绍：****大学
人工智能基础课程实验报告
（2011-2012学年第一学期）
启发式搜索王浩算法
班 级:
学 号:
姓 名:
指导教师：
成 绩:
***********
**********
******
******
2012年1月10日
实验一启发式搜索算法
：
使用启发式搜索算法求解 8数码问题。
⑴编制程序实现求解 8数码问题A算法，采用估价函数 w n f n d n ,
P n
其中：d n是搜索树中结点n的深度；w n为结点n的数据库中错放的棋子个数； p n为结点n的
数据库中每个棋子与其目标位置之间的距离总和。
⑵分析上述⑴中两种估价函数求解 8数码问题的效率差另ij,给出一个是 P n的上界的h n的
定义，并测试使用该估价函数是否使算法失去可采纳性。
.实验目的
熟练掌握启发式搜索 A算法及其可采纳性。
.实验原理
使用启发式信息知道搜索过程，可以在较大的程度上提高搜索算法的时间效率和空间效 率；
启发式搜索的效率在于启发式函数的优劣，在启发式函数构造不好的情况下，甚至在存在解的 情形下也可能导致解丢失的现象或者找不到最优解，所以构造一个优秀的启发式函数是前提条件。
.实验内容
.问题描述
在一个3*3的九宫格 里有1至8八个数以及一个空格随机摆放在格子中，如下图：
目标状态
初始状态
现需将图一转化为图二的目标状态，调整的规则为：每次只能将空格与其相邻的一个数字进行 交换。实质是要求给出一个合法的移动步骤，实现从初始状态到目标状态的转变。
.算法分析
(1)解存在性的讨论
对于任意的一个初始状态，是否有解可通过线性代数的有关理论证明。按数组存储后，算出 初始状态的逆序数和目标状态的逆序数，若两者的奇偶性一致，则表明有解。
(2)估价函数的确定
通过对八数码的特性的研究，找出一个相对好的函数，f(n)=d(n)+h(n) 其中 h(n)=2*compare(n)+3*S(n);d(n) 为已搜索的深度；(compare (n)为当前节点与目标结点相同位置
不相同的个数，S(n)为当前节点的无序度。)
(3)节点的处理
取得一个结点后，判断是否有解，然后对其进行扩展，用估价函数从中取得一个最优节点， 依次循环将路径得到，直到取的最后的目标状态。
(4)算法设计
输入初始结点，判断解的存在性，并与目标节点对比。
若不是目标节点则进行扩展，生成其全部后继节点。
对于每个后继节点均求其 f(n),并比较。
(n)存入正确路径，并与目标节点进行对比。
b,若是目标节点则输出
5实验结果
输入输出:
源代码如下:
#include<>
int final[9]={1,2,3,8,0,4,7,6,5}; 实验内容 ：
实现命题逻辑框架内的王浩算法。
⑴ 将命题逻辑中的王浩算法推广至下述命题语言的情形之下 :
i命题变量符号： pl, p2, p3, L
ii逻辑连接符： ，，， ，
iii间隔符：(,)
⑵ 在上述⑴中所定义的命题语言中实现王浩算法。
实验目的
熟练掌握命题逻辑中的王浩算法。
实验要求
⑴ 实验题目必须由个人独立完成， 允许自行参考相关文献资料， 但严禁同学间相互拷贝和抄袭
程序以及文档资料。实验结束后一周内上交实验报告和实验文档资料。
⑵ 提交的文档资料包括设计文档和程序源代码。设计文档和程序源代码以书面文档方式提供
(用A4纸打印)；并提交电子文档备查。
四．数据结构
给定公式，例如： (p1->(q1->r1))->((p1->q1)->(p1->r1))
函数 inite 主要作用是负责将符号初始化成树的结构。
函数 clone 复制一棵完全相同的符号树。
函数 restruct 查找所有 &， | ， <-> 等符号，并将其拆分成新形式： ！ ， -> 符号。
函数 searching 王浩算法的主要函数。
函数show和output:显示符号串和推理过程。
五．实验结果 公式正确
奈曙入里证朗的公式，变量符号可由大小写字母和知绷^ (t>l Xfll >rl>> K&l >rl»
化成这含式；
<pl - XqI - >rl > > - >< <pl ->q1 J-Xjrt->r1 »
指导结果为二 .・一
Cl >
公理
Q
公理
<3>