中南大学人工智能报告

姓名

年级

指导老师

日期

实验目 熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用 A*算法求解 N 数码难题，理解求 的 解流程和搜索顺序。 使用的是实验环境中已经建立好的“多重路径修建”搜索图

搜索图

算法比

深度优先

Best First 贪婪算 (

A*算法

较 {0} {1.3.4} {3.4.2} {4.2.6} {2.6.5.7.8} {6.5.7.8} {5.7.8} {7.8} {8} {空}

法) {0} {1.3.4} {3.4.2} {4.2.6} {2.6.5.7.8} {6.5.7.8} {5.7.8} {7.8} {8} {空} {0} {1.3.4} {3.4.2} {4.2.6} {2.6.5.7.8} {6.5.7.8} {5.7.8} {7.8} {8} {空} {空} {0} {0.1} {0.1.3} {0.1.3.4} {0.1.3.4.2} {0.1.3.4.2.6} {0.1.3.4.2.6.5} {0.1.3.4.2.6.5.7} {0.1.3.4.2.6.5.7.8} f(x)*=g(x)*+h(x)*

Open 表

Close 表

{空} {空} {0} {0} {0.1} {0.1} {0.1.3} {0.1.3} {0.1.3.4} {0.1.3.4} {0.1.3.4.2} {0.1.3.4.2} {0.1.3.4.2.6} {0.1.3.4.2.6} {0.1.3.4.2.6.5} {0.1.3.4.2.6.5} {0.1.3.4.2.6.5.7} {0.1.3.4.2.6.5.7} {0.1.3.4.2.6.5.7. {0.1.3.4.2.6.5.7.8} 8} f(x)=g(x) f(x)=h(x)

估价函 数

节点 0->节点 1-> 节点 3->节点 4-> 搜索节 节点 2->节点 4-> 点次序 节点 6->节点 4-> 记录 节点 7->节点 5-> 节点 6->节点 8

节点 0->节点 1->节 点 3->节点 4->节点 2->节点 4->节点 6- 节点 0->节点 1->节点 3->节点 4->节点 2->节点 4->节 >节点 4->节点 7-> 点 6->节点 5->节点 7->节点 6->节点 8 节点 5->节点 6->节 点8 最终路径是 节点 0->节点 4->节点 8A*算法结合了启发式方法 (这种方法通过充分利用图给出的信 息来动态地作出决定而使搜索次数大大降低)和形式化方法 (这种方法不利用图给出的信息，而仅通过数学的形式分析， 如 Dijkstra 算法)。 它通过一个估价函数(Heuristic Function) f(h)来估计图中的当前点 p 到终点的距离(带权值),并由此决 定它的搜索方向，当这条路径失败时，它会尝试其它路径。

最终路径是 最终路径是 观测结 节点 0->节点 4->节点 节点 0->节点 4->节 果 8 点8 广度优先搜索算法是 一种搜索策略， 与之相 贪婪算法是一种 对应的还有深度优先 不追求最优解， 只希 搜索算法。 广度优先是 望得到较为满意解 的方法。 贪婪算法一 指从图 G 中 的某点为 般可以快速得到满 始点出发， 标记出所有 意的解， 因为它省去 学生结 与之相邻的点， 并再以 了为找最优解要穷 论 所有与之相邻的点为 尽所有可能而必须 始点， 搜索所有与这些 耗费的大量时间。 贪 点相邻的点， 从而逐层 婪算法常以当前情 向下扩展， 实现对图的 况为基础作最优选 遍历。 同理， 深度优 先 择， 而不考虑各种可 搜索是指从某点出发，能的整体情况， 所以 逐层向下扩展， 直到无 贪婪法不要回溯。 路可扩展时向上回溯，

我们说如果在一般的图搜索算法中应用了上面的估价函数对 OPEN 表进行排序的，就称 A 算法。在

A 算法之上，如果加上

一个条件，对于所有的结点 x,都有 h(x)<=h*(x),那就称为 A*算法。如果取 h(n)=0 同样是 A*算法，这样它就退化成了 有序算法。

它是优先考虑图的深 度 (指从某点的扩展深 度) ,而广度优先则优 先考虑图的广度 (指从 某点 的可扩展量) 。

A*算法是否成功，也就是说是否在效率上胜过蛮力搜索算法， 就在于 h(n)的选取，它不能大于实际的 h*(n),要保守一点， 但越接近 h*(n)给我们的启发性就越大， 是一个难把握的东西。

年级 姓名

实验目的 建立规则库

班级 熟悉和掌握产生式系统的运行机制，掌握基于规则推理 的基本方法。掌握人工智能的知识表示技术，能用产生 式表示法表示知识。

指导老 师

日期 推理 方法 □ □ 正向推理 反向推理 建立事实库% course(C) is true if C is a university course course(322). course(315). % department(C,D) is true if course C is offered in department D. department(322,comp_science) . department(315,math). % student(S) is true if S is a student enrolled(john,322). student(john). % enrolled(S,C) is true if

% cs_course(C) is true if course C is offered in % the computer science department cs_course(C) <- department(C,comp_science). % math_course(C) is true if course C is offered in % the mathematics department math_course(C) <- department(C,math). % cs_or_math_course(C) is true if course C is offered in % either the computer science department or the % mathematics department cs_or_math_course(C) <- cs_course(C). cs_or_math_course(C) <- math_course(C). % in_dept(S,D) is true if student S is enrolled % in a course offered in deparment D in_dept(S,D) <- enrolled(S,C) & department(C,D) & student(S) & course(C).

student S is enrolled in co

urse C enrolled(john,315).

预测结果

Quest 为“in_dept(john,math)”,最后能够得到求证。 备注(原因等) 1、 首先从规则库取出第一条规则 r1,将 r1中的前提部分与初始事实集中的事实相比较， 匹配失败；于是继续取第二条规则再试，匹配失败…直到 r5才得到 enrolled(john,C) 、 department(C, math)、student(john)course(C),暂取 C=322,构造出假设事实集！ 于 是 假 设 事 实 集 为 ： enrolled(john, 322) 、 department(322, math) 、 student(john)、course(322) 初 始 事 实 集 为 ： course(315) 、 department(315,math) 、 student(john) 、 enrolled(john,315)。 实验过程及结果 2、 可见，假设集与事实集匹配不成功，说明先前的取值有问题，返回再次取值。 (注意观测规则的 3、 取 C=315,构造出假设事实集！ 匹配过程和方法) 于 是 假 设 事 实 集 为 ： enrolled(john, 315) 、 department(315, math) 、 student(john)、course(315) 初 始 事 实 集 为 ： course(315) 、 department(315,math) 、 student(john) 、 enrolled(john,315)。 4、此后，一一匹配，均与事实集匹

配。 5、能够证明——in_dept(john,math)

学生结论 指导老师意见

运用正向和反向推理，产生式系统能够完成有一定难度的推理问题。

姓 名实 验 的

指导老师:

日期:

理解反向传播网络的结构和原理，掌握反向传播算法对神经元的训练过程，了解反向传播公式。通过构建 BP 网络实例，熟悉前 目 馈网络的原理及结构。

网 络 拓 朴 图

(输入节点 0,输入节点 1,输入节点 2,输入 (Known,New,Short,Home,Reads) (输入节点 0,输入节点 1,输入节点 4) (1,1,0, 1,0) (0,1,1, 0,1) (0,0,0,0,0) 节点 5) 练 (0,0,0,0) (0,0,1,0) (0,1,1,1) (1,0,0,0) (0,0,0)(0,1,0)(1,0,1) (1,0,0,1,0) (1,1,1,1,1) (1,0,0,0,0) 数 (1,0,1,1)(1,1,0,1)(1,1,1,1) (0,0,1,0,0) (0,1,1,0,1) (1,0,0,1,0)训

据 集

(1,1,0,0,0) (0,0,1,1,0) (1,1,0,0,0) (1,0,1,1,1) (1,1,1,0,1) (1,1,1,1,1) (1,0,1,0,1) (1,1,1,1,1) (0,1,1,0,1) 第 1 代误差 第 51 代误差 第 101 代误差 第 151 代误差 第 201 代误差 1.68 0.52 0.11 0.05 0.03 第 1 代误差 第 51 代误差 第 101 代误差 第 151 代误差 第 201 代误差 0.018 0.010 0.010 0.010 0.010 第 1 代误差 第 51 代误差 第 101 代误差 第 151 代误差 第 201 代误差 4.67 0.66 0.12 0.06 0.03

训 练 误 差 模 拟 的 问 题 或 函 数

多数赞成表决器

异或问题

MailReading(邮件信息识别)

经过 200 代的进化，误差以明显的阶梯型降低观 测 结 果

经过 200 代的进化，误差极大地降低

由于初始误差比较低，故经过 50 代的 进化，误差已经极大地降低，几乎不再变 化

学 生 结 论 :

单层的神经网络无法实现异或问题， 但是 经过训练的 BP 网络可以进行邮件识别， 神经计算能够实现“多数赞成表决器”功能 含有中间层的 BP 网络却可以很好的解决 解决信息识别的难题，可以极大地提高生 异或问题 产力

姓 名 实 验 目 的

年级

指导 老师

日期

熟悉和掌握自动规划的基本原理,方法和主要技术

搜 索 图

状 态 谓 词

empty:机械手为空手 on(A,B):木块 A 在木块 B 上

ontable(A):木块 A 在桌面上 clear(A):木块 A 顶上没有任何东西

定 义 动 作 谓 词 定 义 pickup(A,B):把木块 A 木块 B 起来。动作之前要求机械手为空，且木块 A 空的。 pickuptable(A):把木块 A 桌面上拿起来。动作之前要求机械手为空，且木块 A 是空的。 putdown(A,B):把木块 A 堆放在木块 B 上。动作之前要求机械手已抓着木块 A,且木块 B 上是空的。 putdowntable(A):把木块 A 堆放在桌面上。动作之前要求机械手已抓着木块 A。 holding(A):机械手抓着木块 A。

初 始 状 态 empty ontable(木块 1) on(木块 2, 木块 1) clear(木块 3) on(木块 3, 木块 1) ontable(木块 2) clear(

木块 2)

目 标 状 态

empty ontable(木块 3) on(木块 2, 木块 3) on(木块 1, 木块 2) clear(木块 1) 规 划 序 列 pickup(木块 3, 木块 1) —>putdowntable(木块 3) —>pickuptable(木块 2) —>putdown(木块 2, 木块 3) —>pickuptable(木块 1) —>putdown(木块 1, 木块 2) 依次读出规划操作，就得到一个能够达到目标状态的动作序列，这个动作序列也就是这个积木世界机器人问题目标的规划。通过延时可以看出机器 人成功地将木块从初始状态变换为目标状态。

观 测 结 果

学 生 结 论

本次自动规划采用 STRIPS 算法。从搜索图可看出，此自动规划是从目标状态描述开始逆向求解。分析每个状态的先决条件，若得到的条件和原先的 条件相同，说明该条件不可能得到满足，故返回选择另一种匹配路径，直至找到吻合的现有状态，说明规划成功，否则失败退出。通过再通过逆规 则(即中间—结局分析)回到目标状态，就能得到一个能够到达目标状态的动作序列。

本文来源：https://www.bwwdw.com/article/vrw1.html