《人工智能及其应用》实验指导书
下面是实验报告的基本内容和书写格式。
实验名称
班级： 学号： 姓名：
一、实验目的 二、实验内容 三、实验结果
按照实验要求，给出相应结果。 四、实验总结
1. 分析隶属度、模糊关系和模糊规则的相互关系。 2. 总结实验心得体会
——————————————————————————————————
8
《人工智能及其应用》实验指导书
实验三 A*算法实验I
一、实验目的
熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解N数码难题，理解求解流程和搜索顺序。 二、实验原理
A*算法是一种启发式图搜索算法，其特点在于对估价函数的定义上。对于一般的启发式图搜索，总是选择估价函数f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的实际代价g(n)以及从节点
h*(n)为n节点到目的结点的最n到达目标节点的估价代价h(n),且h(n)?h*(n)，
优路径的代价。
八数码问题是在3×3的九宫格棋盘上，摆有8个刻有1～8数码的将牌。棋盘中有一个空格，允许紧邻空格的某一将牌可以移到空格中，这样通过平移将牌可以将某一将牌布局变换为另一布局。针对给定的一种初始布局或结构（目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。如下图1表示了一个具体的八数码问题求解。
图1 八数码问题的求解
三、实验内容
1. 参考A*算法核心代码，以8数码问题为例实现A*算法的求解程序（编程语言不限），要求设计两种不同的估价函数。
2. 设置相同的初始状态和目标状态，针对不同的估价函数，求得问题的解，并比较它们对搜索算法性能的影响，包括扩展节点数、生成节点数等。 3. 设置与上述2相同的初始状态和目标状态，用宽度优先搜索算法（即令估计代价h(n)＝0的A*算法）求得问题的解，以及搜索过程中的扩展节点数、生成节点数。
*4. 参考A*算法核心代码，实现A*算法求解15数码问题的程序，设计两种不同的估价函数，然后重复上述2和3的实验内容。 5. 提交实验报告和源程序。
9
《人工智能及其应用》实验指导书
四、实验报告要求
1. 分析不同的估价函数对A*算法性能的影响。
2. 根据宽度优先搜索算法和A*算法求解8、15数码问题的结果，分析启发式搜索的特点。
下面是实验报告的基本内容和书写格式。
实验名称
班级： 学号： 姓名：
一、实验目的 二、实验原理 三、实验结果
按照实验内容，把结果填入表1。
表1 不同启发函数h(n)求解8数码问题的结果比较
不在位数 初始状态 目标状态 最优解 123804765 扩展节点数 生成节点数 运行时间 启发函数h(n) 123804765 0 123804765 *表2 不同启发函数h(n)求解15数码问题的结果比较
不在位数 初始状态 目标状态 最优解 扩展节点数 生成节点数 运行时间 启发函数h(n) 0 10
《人工智能及其应用》实验指导书
四、实验总结
1. 画出A*算法求解N数码问题的流程图 2. 完成实验报告要求1和2。 3. 总结实验心得体会
——————————————————————————————————
11
《人工智能及其应用》实验指导书
实验四 A*算法实验II
一、实验目的
熟悉和掌握A*算法实现迷宫寻路功能，要求掌握启发式函数的编写以及各类启发式函数效果的比较。 二、实验原理
A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。公式表示为：f(n)=g(n)+h(n)，其中f(n)是节点n从初始点到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)小于等于n到目标节点的距离实际值h*(n)，这种情况下，搜索的点数多，搜索范围大，效率低，但能得到最优解。如果估价值大于实际值，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
寻路问题常见于各类游戏中角色寻路、三维虚拟场景中运动目标的路径规划、机器人寻路等多个应用领域。迷宫寻路问题是在以方格表示的地图场景中，对于给定的起点、终点和障碍物（墙），如何找到一条从起点开始避开障碍物到达终点的最短路径。
假设在一个n*m的迷宫里，入口坐标和出口坐标分别为(1,1)和(5,5)，每一个坐标点有两种可能：0或1，其中0表示该位置允许通过，1表示该位置不允许通过。
如地图：
0 0 0 0 0 1 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 0 0 1 0 最短路径应该是
A B 0 0 0 1 C 1 0 1 E D 1 1 1 F 1 J K L G H I 1 M
即： (1,1)-(1,2)-(2,2)-(3,2)-(3,1)-(4,1)-(5,1)-(5,2)-(5,3)-(4,3)-(4,4)-(4,5)-(5,5)
12