人工智能第3章选讲.ppt

从s到n的最短路径的长度， e是图中每条弧的最小费用。
于是有g*(n)≥d*(n).e
又g(n)≥g*(n)≥d*(n).e ， f(n)= g(n)+h(n) ，且h(n) ≥0
因此 f(n)≥ g(n)≥ d*(n) .e
若A*不终止，OPEN表中节点的d*值会不断增大，因此
f值也会不断增大。
5
11
10/10/2020
A*算法的可采纳性
定理5 算法A*选择的任意扩展点都有f(n)≤f*(s)
证明：若n是目标点，由定理4，f(n)≤f*(s) 若n不是目标点，由定理2 ，A*算法终止前，
OPEN表中总有一点n’，使 f(nn’)≤f*(s) 证毕。
在OPEN表中的节点
(这样的n’是存在的：因为开始n0在OPEN上，算法结束前，
若扩展ni，则ni+1在OPEN上，此时不可能扩展到nk)。
由A*的定义，有f(n’)= g(n’)+ h(n’)
6
10/10/2020
A*算法的可采纳性……定理2
因为n’处在通往目标的最佳解路径上， 设(n0,n1,……, n’) 是s到n’的最佳解路径。n’的所有祖先都在CLOSED表上， 所以(n0,n1,……, n’)是A*发现的一条通向n’的最佳解路径， g(n’)= g*(n’)
13
10/10/2020
A*算法的比较
讨论：启发函数的启发能力在于它所具有的 启发性信息。 1. 当h(n)≡0时，反映了启发函数完全没有启 发信息，要扩展较多的节点． 2. 在具有可采纳性的前提下， 0≤h≤h*，h* 定出了h的上界，当h越接近h*时，它的启发 能力就越大．
14
10/10/2020

精选ppt
14
解：第一步： 定义问题状态的描述形式：
设Sk=(M,C,B)表示传教士和野人在河右岸 的状态。
其中：
M表示传教士在右岸的人数。
C表示野人在右岸的人数。
B用来表示船是不是在右岸。
(B=1表示在右岸，B=0表示在左岸)。
初始状态集：S={(3,3,1)}
目标状态集：G={(0,精0选,0pp)t }
精选ppt
19
的实质。
2.2 问题归约法
➢问题归约法的组成部分 （1）一个初始问题描述； （2）一套把问题变换为子问题的操 作符； （3）一套本原问题描述。
精选ppt
20
2.3 谓词逻辑法
➢ 一阶谓词逻辑表示法适于表示确定 性的知识。它具有自然性、精确性、严 密性及易实现等特点。
精选ppt
21
2.3 谓词逻辑法
精选ppt
18
2.2 问题归约法
➢问题归约法的概念
❖已知问题的描述，通过一系列变换把此 问题最终变为一个子问题集合；这些子 问题的解可以直接得到，从而解决了初 始问题。
❖该方法也就是从目标(要解决的问题)出发
逆向推理，建立子问题以及子问题的子
问题，直至最后把初始问题归约为一个
平凡的本原问题集合。这就是问题归约
L(1,0), L(2,0), L(精1选,1ppt), L(0,1), L(0,2) 16
第三步：求解过程。
R(2,0)
1,1,0 R(1,1)
L(2,0) 3,1,1 L(0,1) R(0,1)
3,0,0 L(0,2) R(0,2)
L(1,1) 2,2,1
L(2,0) R(2,0)
L(1,0)
所代表的对象的特性。弧线用于表示节点

正向推理，但并不能推导出最终目标；另一方面
从某假设出发进行逆向推理，但并不能推至原始
事实，而是让由正向推理所得到的中间结论恰好
与逆向推理所要求的证据相遇，此时推理结束。
逆向推理时所作的假设就是推理的最终结论。
3.1.
4
冲 突 消 解 策 略
在推理过程中，系统要不断地用自己当前已知的事实与知识
库中的知识进行匹配，匹配过程中会出现3种情况。
越来越接近最终目标分类，推理可分为单调推理和非单调推理。
（1）单调推理是指在推理的过程中随着推理的向前推进及新知识的加入，推出的
结论呈单调增加的趋势，并且结论越来越接近最终目标。单调推理在推理的过程
中不会出现反复的情况，如基于经典逻辑的演绎推理。
（2）非单调推理是指在推理过程中由于新知识的加入，不仅没有加强已推出的结
来，因此它不能增殖新知识。
归纳推理所推出的结论是没有包含在前提内容中的，这种由个别
事物或现象推出一般性知识的过程，是增殖新知识的过程。
例如，一位计算机维修员从书本学习知识到通过大量实例积累经验，
是一种归纳推理方式。计算机维修员运用这些一般性知识去维修计算
机的过程则属于演绎推理。
（3）默认推理又称为缺省推理，是在知识不完全的情况下假设某些条
（1）从用户提供的初始已知事实出发，在知识库KB中找出当前适
用的知识，构成知识集KS。
（2）按某种冲突消解策略从KS中选出一条知识进行推理，并将推
出的新事实加入数据库DB中，作为下一步推理的已知事实。
（3）在知识库中选取可适用知识进行推理，如此重复这一过程，
直到求得了问题的解或者知识库中再无可适用的知识为止。
题逻辑和一阶谓词逻辑，它们的真值都是确定的。因此，

• 产生式系统的组成 • 产生式系统的组成过程 • 产生式系统的控制策略与常用算法
（正向，反向）
a
16
第7章 知识表示
• 框架 • 语义网络
a
17
命题逻辑的归结原理
• 设C1， C2是命题逻辑中的两个子句 C1中有文字L1 ，C2中有文字L2 ，且L1与 L2互补， 从C1 、 C2中分别删除L1 、L2 ， 再将剩余部分析取起来，记构成的新子句为 C1 2，则C1 2为C1 、 C2的归结式。
C 1 C 2 (1 C {1 } L ( )2 C {2 } L )
a
9
化子句集的过程
• 1、消去蕴含词和等值词。 • 2、使否定词仅作用于原子公式。 • 3、适当改名使量词间不含同名指导变元。 • 4、消去存在量词。 • 5、消去全称量词。 • 6、化公式为合取范式。 • 7、适当改名，使子句间无同名变元。 • 8、消去合取词，以子句为元素组成一个集合S。
a
10
a
11
替换与合一
• 一个替换（Substitution）是形如 {t1/x1, t2/x2, …, tn/xn}的有限集合
• 设σ是原子公式集S的一个合一，如果
对S的任何一个合一θ都存在一个替换λ，
使得 θ ＝ σ •λ
则称σ为S的
最一般合一(Most General Unifier),简
称MGU。
• 与或树搜索
– 可解性判定 – 广度优先、有界深度优先
a
6
与或图搜索（续1）
• 有序搜索
– 解树（树根）代价的计算方法
• 和代价法 • 最大代价法
– 有序搜索过程
a
7
博弈树搜索
• 极小极大分析法 • α－ß剪枝技术