它们全部进行估价,从中选出最优节点进行扩展,而不管这个节点出现在搜索树的什么地方。 步1 把初始节点So放入OPEN表中,计算h(So)。? 步2 若OPEN表为空,则搜索失败, 退出。 ?
步3 移出OPEN表中第一个节点N放入CLOSED表中, 并冠以序号n。? 步4 若目标节点Sg=N, 则搜索成功, 结束。 ? 步5 若N不可扩展, 则转步2。?
步6 扩展N, 计算每个子节点x的函数值h(x), 并将所有子节点配以指向N的返回指针后放入OPEN表中, 再对OPEN表中的所有子节点按其函数值大小以升序排序,转步2。
局部择优搜索：局部择优搜索与全局择优搜索的区别是, 扩展节点N后仅对N的子节点按启发函数值大小以升序排序, 再将它们依次放入OPEN表的首部。 故算法从略。 （前5步一样）
步6 扩展N, 计算每个子节点x的函数值h(x), 扩展节点N后仅对N的子节点按启发函数值大小以升序排序, 再将它们依次放入OPEN表的首，转步2。
遗传算法(GA: Genetic Algorithm) 就是人们从生物界按自然选择和有性繁殖、遗传变异的自然进化现象中得到启发，而设计出的一种优化搜索算法。 遗传算法中的三种遗传操作：选择—复制、交叉和变异
删除策略：在归结过程中可随时删除一下子句：①含有纯文字的字句②含有永真式的子句 ③被子句集中别的子句类包含的子句。 例3.22 设已知：
(1)能阅读者是识字的； (2)海豚不识字；
(3)有些海豚是很聪明的。
试证明：有些聪明者并不能阅读。
证 首先，定义如下谓词：R(x)：x能阅读。L(x)：x识字。I(x)：x是聪明的。D(x)：x是海豚。 然后把上述各语句翻译为谓词公式：
(1) x(R(x)→L(x))?(2) x(D(x)→乛L(x))?(3) x(D(x)∧I(x))(4) x(I(x)∧乛R(x)) 求题设与结论否定的子句集，得
(1)乛R(x)∨L(x)(2)乛D(y)∨乛L(y)(3)D(a)(4)I(a)(5)乛I(z)∨R(z) 归结得
(6) R(a) (5)，(4)，{a/z} (7) L (a) (6)，(1)，{a/x} (8) 乛D(a) (7), (2), {a/y} (9)□ (8), (3)? 例3.23 已知:
(1)如果x和y是同班同学，则x的老师也是y的老师。 (2)王先生是小李的老师。 (3)小李和小张是同班同学。 问：小张的老师是谁？ 解 设谓词T(x,y)表示x是y的老师，C(x,y)表示x与y是同班同学，则已知可表示成如下的谓词公式：
F1: x y z(C(x,y)∧T(z,x)→T(z,y)) F2:T(Wang,Li) F3:C(Li,Zhang)
为了得到问题的答案，我们先证明小张的老师是存在的，即证明公式： G: x T(x,Zhang)
于是，求F1∧F2∧F3∧ G的子句集如下: (1) C(x,y)∨ T(z,x)∨T(z,y)
11
(2)T(Wang,Li) (3)C(Li,Zhang) (4) T(u,Zhang) 归结演绎，得
(5) C(Li,y)∨T(Wang,y) 由(1),(2),{Wang/z,Li/x} (6) C(Li,Zhang) 由(4),(5),{Wang/u,Zhang/y} (7)□ 由(3),(6)?
这说明，小张的老师确实是存在的。那么，为了找到这位老师，我们给原来的求证谓词的子句再增加一个谓词ANS(u)。于是，得到
(4)′ T(u,Zhang)∨ANS(u)?
现在，我们用(4)′代替(4)，重新进行归结，则得
(5)′ C(Li,y)∨T(Wang,y) 由(1)(2) (6)′ C(Li,Zhang)∨ANS(Wang) 由(4)′(5)′
(7)′ANS(Wang) 由(3)(6)′ 例3.24 设有如下关系:
(1)如果x是y的父亲，y又是z的父亲，则x是z的祖父。 (2)老李是大李的父亲。 (3)大李是小李的父亲。
问：上述人员中谁和谁是祖孙关系？
解 先把上述前提中的三个命题符号化为谓词公式： F1: x y z(F(x,y)∧F(y,z)→G(x,z)) F2: F(Lao,Da) F3: F(Da,Xiao) 并求其子句集如下:
(1)乛 F(x,y)∨乛 F(y,z)∨G(x,z) (2)F (Lao,Da) (3)F (Da,Xiao)? 设求证的公式为
G: x yG(x,y) (即存在x和y，x是y的祖父) 把其否定化为子句形式再析取一个辅助谓词GA(x,y)，得 (4)乛G(u,v)∨GA(u,v)? 对(1)~(4)进行归结,得
(5)乛F(Da,z)∨G(Lao,z) (1),(2),{Lao/x,Da/y} (6)G(Lao,Xiao) (3),(5),{Xiao/z} (7)GA(Lao,Xiao) (4),(6),{Lao/u,Xiao/v}? 所以，上述人员中，老李是小李的祖父。 子句的蕴含表示形式
原子公式及其否定称为文字 Horn子句与逻辑程序
至多含有一个正文字的子句称为Horn（有些文献中译为“霍恩”）子句。 产生式系统由三部分组成： 产生式规则库、 推理机和动态数据库. 产生式系统的推理可分为正向推理和反向推理两种基本方式。 正向推理?
正向推理算法一： ?
步1 将初始事实/数据置入动态数据库。?
步2 用动态数据库中的事实/数据, 匹配/测试目标条件, 若目标条件满足, 则推理成功, 结束。 步3 用规则库中各规则的前提匹配动态数据库中的事实/数据, 将匹配成功的规则组成待用规则
12
集。
步4 若待用规则集为空, 则运行失败, 退出。 ?
步5 将待用规则集中各规则的结论加入动态数据库, 或者执行其动作, 转步2。 反向推理?
步1 将初始事实/数据置入动态数据库, 将目标条件置入目标链。? 步2 若目标链为空, 则推理成功, 结束。 ?
步3 取出目标链中第一个目标, 用动态数据库中的事实/数据同其匹配, 若匹配成功, 转步2。 步4 用规则集中的各规则的结论同该目标匹配, 若匹配成功,则将第一个匹配成功且未用过的规则的前提作为新的目标, 并取代原来的父目标而加入目标链, 转步3。? 步5 若该目标是初始目标, 则推理失败, 退出。 ?
步6 将该目标的父目标移回目标链, 取代该目标及其兄弟目标, 转步3。 每个学生读过《三国演义》
≯x(student (x) → read (x, 三国演义))
? GSstudentreadbook
ISAISAISAISA Fsubjectobject Rxread1三国演义 A? 猴子摘香蕉问题。 – 用四元组来（w，x，y，z）表示状态， w：表示猴子的位置； x：表示猴子是否在箱顶； y：箱子的水平位置； z：猴子是否拿到香蕉。 初始位置为（a，0，b，0），目标位置为（ c，1，c，1 ） 规则集中的规则：
If（w，0，y，z）then goto（u），状态为（u，0，y，z） If（w，0，w，z）then pushbox（v），状态为（v，0，v，z） If（w，0，w，z）then climbbox，状态为（w，1，w，z） If（c，1，c，0）then grasp，状态为（ c，1，c，1 ）
学生框架例子 框架名：<学生> 性别:(男,女)
成绩:(优,良,中,差)
类型:(<小学生>,<中学生>,<大学生>,<研究生>) 民族:(汉族,回族,白族,朝鲜族,等) 缺省:汉族
籍贯:(河南,山东,河北,湖南等) 缺省:河南 老师框架例子 框架名:<教师> 类属:<知识分子>
工作:范围:(教学，科研) 缺省:教学
13
性别:(男，女) 学历:(中师，高师)
类型:(<小学教师>，<中学教师>，<大学教师>)
狭义上讲，知识或信息中的不确定性是指描述随机事件或随机现象所表现出的不确定性——这种不确定性一般用概率来刻画。
广义不确定性分类：(狭义)不确定性、不确切性(模糊性)、不完全性、不一致性、时变性等几种类型。
不确定性推理=符号推演+信度计算
机器学习就是让计算机模拟人的学习行为，或者说计算机也具有学习的能力。 ?
人工智能中的机器学习主要是指机器对自身的行为的修正或性能的改善和机器对客观规律的发现。机器学习的三要素：信息、发现和知识。他们分别是机器学习的对象、方法和目标。 基于学习策略的分类：模拟人脑的机器学习、直接采用教学方法的机器学习。
知识发现的任务：数据总结、概念描述、分类、聚类、相关性分析、偏差分析、建模。
根据连接的拓扑结构不同，神经网络可分为四大类：分层向前网络、反馈前向网络、广泛互联网络。 什么是决策树
决策树(decision tree)也称判定树，它是由对象的若干属性、属性值和有关决策组成的一棵树。其中的节点为属性（一般为语言变量），分枝为相应的属性值（一般为语言值）。 决策树学习的基本方法和步骤是: ?
首先,选取一个属性, 按这个属性的不同取值对实例集进行分类; 并以该属性作为根节点,以这个属性的诸取值作为根节点的分枝, 进行画树。 ?
然后,考察所得的每一个子类, 看其中的实例的结论是否完全相同。如果完全相同, 则以这个相同的结论作为相应分枝路径末端的叶子节点; 否则, 选取一个非父节点的属性, 按这个属性的不同取值对该子集进行分类, 并以该属性作为节点, 以这个属性的诸取值作为节点的分枝, 继续进行画树。 如此继续,直到所分的子集全都满足: 实例结论完全相同, 而得到所有的叶子节点为止。这样, 一棵决策树就被生成。
模式：能够表征或刻画被识对象类属特征的信息模型称为对象的模式(pattern)。
模式类：具有某些共同特性的模式的集合称为模式类, 判定一个待识模式类属的过程称为模式识别。
最常用的模式表示形式有向量和字符串。 模式设别的原理：
模式识别的全过程分为两步: 第一步是分类知识的生成过程, 其实是个纯粹的机器学习过程; 第二步才是真正的模式识别过程。
14
依据模式的表示形式,模式识别方法可分为基于特征向量的模式识别和基于字符串的模式识别, 前者称为统计模式识别, 后者称为结构模式识别。统计模式识别和结构模式识别是两种经典而基本的模式识别方法,
统计模式识别(距离分类法、几何分类法、概率分类法) 距离分类法：标准模式法，平均距离法、最临近法
要理解一个语句，需建立起一个和该简单句相对应的机内表达。而要建立机内表达，需要做以下两方面的工作：
(1)理解语句中的每一个词。
(2)以这些词为基础组成一个可以表达整个语句意义的结构。
实现机器的自然语言理解都涉及哪些工作？语法分析，语义分析、语用分析。
15