华南理工大学《人工智能》复习资料

Ch 2.

【状态空间表示】

S F G

<>

，，

S：初始状态的集合

F：操作的集合

G：目标状态的集合

例如：507

{}{}{}

Q a b c Q Q

<>

，，，，，

【状态空间图】

【状态空间图搜索使用的数据结构】

OPEN表：已生成但没考察的节点(待考察节点)

CLOSED表：考察过的节点及节点间关系(搜索树)

【广度/深度优先搜索特点】

广度优先：完备的(一定能找到最优解)，搜索效率低，OPEN

表为队列结构

深度优先：不能保证找到最优解，OPEN表为堆栈结构

有界深度优先搜索：即使能求出解，也不一定是最优

可变界深度优先搜索算法：深度可变，每次深度超过阈值

的点，都被当作待考察点(在CLOSED表中)

【启发式搜索算法分类】

按选择范围分类：

全局择优搜索：考虑所有待考察节点

局部择优搜索：只考虑当前节点的子节点

【A*算法】

f（x）＝g（x）＋h（x）

g(x)为当前点的代价

h(x)为距离目标的距离

A*对A算法的改进：

对h(x)作限制，使其总是小于实际最小距离h（x）≤ h* （x），

具有完备性

【与或图】

Q与Q1，Q2与等价（即Q可以分解为Q1+Q2）

Q1与{Q1i},{Q1i’}或等价（即Q1可以转换为{Q1i}或{Q1i’}）

【与或图中的概念】

本原问题：直接可解的问题。

终止节点：本原问题对应的节点

端节点：无子节点的节点

与节点：子节点为与关系

或节点：子节点为或关系

【与或图的广度/深度搜索】

Step1:S0放入OPEN表

Step2:OPEN表第一个点（记为N）取出放入CLOSED表，

冠以编号n。

Step3:若n可扩展：

(1)扩展N，其子节点放入OPEN表(深度:尾部，广度:首部)

(2)考查这些节点是否终止节点。若是，放入CLOSED表，

标为可解节点，并对先辈点标示。若S0被标可解，得解。

(3)从OPEN表删除具有可解先辈的节点。转Step2。

Step4:若N不可扩展：

(1)标示N为不可解。

(2)标示先辈节。若S0被标不可解，失败。

(3)从OPEN表删除具有不可解先辈的节点。转Step2。

【与或图启发式搜索】

由下往上更新函数值，函数值=子节点价值+子节点与父节点距离。例子见PP3 Ch3.P117-120

【博弈树】

与结点：对手(MIN)力图干扰MAX的选择。因此站在我方（MAX）的立场，由MIN出棋的结点具有与结点的性质。或结点：我方（MAX）力图通往取胜。MAX出棋的结点具有或结点的性质。

【α剪枝,β剪枝】

α剪枝：对MIN节点,若其倒推上确界β不大于MIN的父节点倒推下确界α,即α≥β,则不必扩展该MIN节点其余子节点

β剪枝：对MAX节点,若其倒推下确界α不小于MAX的父节点倒推上确界β,即α≥β,则不必扩展该MAX节点其余子节点

Ch 3.

【离散数学相关定义】

命题（proposition）：具有真假意义的语句

谓词(predicate)：刻画个体的性质、状态或个体间的关系，例如P(x,y): x是y的父亲

个体域：个体变元的变化范围。(如P(x,y)中，x,y是变元) 全总个体域:包揽一切事物的集合

函数：个体之间的对应关系,例如father(x): 值为x的父亲项：个体常元和变元都是项。若t1，t2，…，tn是项，则f（t1，t2，…，tn ）是项

原子公式：若t1，t2，…，tn为项，P（t1，t2，…，tn）称为原子谓词公式，简称原子或原子公式

谓词公式：原子公式是谓词公式。若A、B是谓词公式，则? A，A∪B等都是谓词公式

辖域：紧接于量词之后被量词作用的谓词公式

指导变量：量词后的变量

约束变量：量词辖域中，与该量词的指导变元相同的变量自由变量：除了约束变量之外的变量

一阶谓词：仅个体变元被量化的谓词

二阶谓词：个体变元、函数符号、谓词符号被量化

从谓词公式得到命题：

(1)把谓词中的个体变元代入个体常元

(2)把谓词中的个体变元全部量化

如P(x)表示"x是素数", 则?x P(x)，P(a)都是命题

合取范式：B1 ∧ B2 ∧…∧B n，如

(()())(()())(()())

P x Q x Q y R y P z S z

∨∧?∨∧?∨8

析取范式：B1 ∨B2 ∨…∨B n，如

(()())(

D y L a y P x C z P u L u v

?∧∨?∧∨?∧?

，（()())())(，))

谓词公式永真性：P对个体域D全部成立，则P在D上永

真。P在全总个体集成立，则P永真

谓词公式可满足性：P对个体域D至少有一个个体成立，

则P在D上可满足。

【常用逻辑等价式】

【常用推理定律】

【子句集】

文字：原子谓词公式及其否定

子句：任何文字的析取

【子句集特点】

1.没有蕴含词、等值词

2.“?”作用原子谓词

3.没有量词( ?、? )

4.合取范式

5.元素之间变元不同

6.集合形式

【由谓词公式得到子句集】

(对应子句集特点的序号)

1.根据蕴含等价式消去蕴含关系

2.根据量词转换律、双重否定律、摩根定律转换

3.存在量词：受?x约束，则定义f(x)替换y (Skolem函数)

不受?x约束，常量代替y (Skolem常量) 全称量词：直接消去

4.根据分配率合取

5.各个合取子句变量改名

6.把合取符号替换为逗号，组成集合

【Skolem标准型】

消去存在量词，把全称量词移到最左，右式为合取，如

?x [P(x，f(x)) ∧? R(x,g(x)) ]

Skolem标准型与原公式一般并不等价

【命题逻辑中的归结原理定义】

逻辑结论与前提：G是F1、F2 、…、F n的逻辑结论，当且仅当对每个解释I，如果F1、F2 、…、F n都为真，则G也为真。F1、F2 、…、F n为G的前提。

互补文字：L与?L

归结式：C1包含L1，C2包含L2，L1与L2互补。把L1和L2删除，并把剩余部分析取，得到C12

亲本子句：上例中C1与C2

消解基：上例中L1与L2

例如：

【归结原理定理】

1.谓词公式A不可满足当且仅当其子句集S不可满足。

2.G是公式F1、F2、…、F n的逻辑结论，当且仅当

F1 ∧F2 ∧…∧F n => G

3.G是公式F1、F2、…、F n的逻辑结论，当且仅当

F1 ∧F2 ∧…∧F n ∧ ? G不可满足

4.归结式是其亲本子句的逻辑结果

5.子句集S的C1，C2替换为C12得到S1，则

S1不满足=>S不满足

6.子句集S添加C12得到S2，则

S2不满足=>S不满足

【归结反演法】

否定目标公式G，? G加入到F1 ∧F2 ∧…∧F n中，得到子句集S。对S进行归结，并把归结结果并入S，直到得到空子句，原问题得证。

【替换定义】

替换：{t1/x1, t2/x2, …, tn/xn}

替换的分子：t1, t2, …, tn是项

替换的分母：x1, x2, …, xn是互不相同的个体变元(ti,,xi不同,xi不循环出现在tj中,如{f(x)/y,g(y)/x}不是替换) 基替换：t1, t2, …, tn是不含变元的项（称为基项）空替换：没有元素的替换，记作ε

表达式：项、原子公式、文字、子句的统称

基表达式：没有变元的表达式

例/特例：对公式E实施替换θ，记为Eθ，所得结果称为E在θ下的例

复合/乘积：

θ＝{t1/x1, t2/x2, …, tm/xm}，

λ＝{u1/y1, u2/y2, …, un/yn}，

删除{t1λ/x1,t2λ/x2,…,tmλ/xm ,u1/y1,u2/y2,…,un/yn}中：

(1)tiλ/xi 当tiλ＝xi

(2)ui/yi 当yi∈{x1,…, xn}

得到θ与λ的复合或乘积，记为θ?λ

例如：

θ= {a/x, f(u)/y ,y/z},λ={b/u,z/y,g(x)/z}

从{a/x，f(b)/y ，z/z，b/u，z/y，g(x)/z},删去：

z/z，z/y，g(x)/z

得到：θ·λ= {a/x，f(b)/y ，b/u}

【合一定义】

合一：F1λ=F2λ=…=Fnλ则λ为F的合一，F为可合一的（一个公式的合一一般不唯一）

最一般合一：σ为F的一个合一，如果对F任何合一θ都存在λ使得θ＝σ?λ，则σ为F的最一般合一，极为MGU（一个公式集的MGU不唯一）

差异集：S是具有相同谓词名的原子公式集，从各公式左边开始，同时向右比较，直到发现第一个不都相同的项为止，用这些项的差异部分组成的集合

【合一算法】

Step1：置k＝0，Fk＝F，σk ＝ε；

Step2：若Fk只含有一个谓词公式，则算法停止，σk就是最一般合一；

Step3：求Fk的差异集Dk；

Step4：若Dk中存在元素xk和tk ，其中xk是变元，tk 是项且xk不在tk中出现，则置Sk ＋1＝Fk{tk/ xk} ,σk+1= σk ?{tk/ xk} ，k＝k+1然后转Step2；

Step5：算法停止，F的最一般合一不存在。

对任一非空有限可合一的公式集，一定存在最一般合一，而且用合一算法一定能找到最一般合一

【合一算法例子】

求公式集F＝{Q(a,x,f(g(y))),Q(z,h(z,u),f(u))}的最一般合一解：

解

k＝0；

F0＝F，σ0＝ε，D0＝{a,z}

R

S

P

C∨

∨

?

=

12

σ1＝σ0·{a/z}= {a/z}

F1= F0{a/z}= {Q(a,x,f(g(y))),Q(a,h(a,u),f(u))}

k＝1；

D1={x, h(a,u)}

σ2= σ1·{h(a,u) /x}＝{a/z,h(a,u) /x}

F2= F1{a/z, h(a,u) /x}= {P(a, h(a,u) ,f(g(y))),P(a,h(a,u),f(u))}

k＝2；

D2＝{g(y),u}

σ3＝{a/z ,h(a, g(y)) /x ,g(y)/u}

F3= F2{g(y)/u}= {P(a,h(a,g(y)),f(g(y)))}

S3单元素集，σ3为MGU。

【谓词逻辑中的归结原理定义】

二元归结式（二元消解式）:

（C1σ－{L1σ}）∪（C2σ－{L2σ}）,其中：

亲本子句：C1，C2为无相同变元的子句

消解文字：L1，L2

σ为L1和?L2的最一般合一

因子：C σ。其中σ为C的子句文字的最一般合一

单因子：C σ为单元句子

【归结式】

子句的C1，C2归结式，是下列二元归结式之一:

（1）C1和C2的二元归结式；

（2）C1和C2的因子的二元归结式；

（3）C1因子和C2的二元归结式；

（4）C1的因子和C2的因子的二元归结式。

归结注意事项：

(1) 两个子句不能含有相同的变元

(2) 归结的子句内部含有可合一的文字，则需进行简化

【谓词逻辑的消解原理/归结原理】

谓词逻辑中的消解（归结）式是它的亲本子句的逻辑结果：C1 C2＝>（C1σ －{L1σ}）∪（C2σ－{L2σ}）

【谓词逻辑的定理】

如果子句集S是不可满足的，那么必存在一个由S推出空子句的消解序列。

【应用归结原理求取问题答案】

Step1：前提化为子句集S

Step2：确定目标谓词，化为子句，并析取助谓词新子句，并入到S形成S’。Step3：对S’应用归结原理。

Step4：当只剩辅助谓词时，归结结束。

(例子见CH3 P105 )

【归结策略】

Step1：子句集S置入CLAUSES表

Step2：若Nil在CLAUSES，归结成功

Step3：若CLAUSES存在可归结子句对，则归结，并将归结式并入CLAUSES表，step2

Step4：归结失败

【广度优先搜索归结策略】

用于确定归结策略step3的搜索次序

第一轮：0层（原子句集S）两两进行归结，产生1层

下一轮：1层与0、1层两两进行归结，得到2层

再一轮：2层与0、1、2层两两进行归结，得到3层

如此类推，直至出现Nil

【归结策略完备性】

一个归结策略是完备的，如果对于不可满足的子句集，使用该策略进行归结，最终必导出空子句Nil。

（广度优先是完备的，亦称水平浸透法）

【归结策略出发点】

（1）简化性策略。

（2）限制性策略。

（3）有序性策略（包含排序策略）

【归结策略类型】

删除策略

支持集策略

线性归结策略

单元归结策略

语义归结策略

祖先过滤型策略

【正向演绎推理--初始事实F0】

●任意谓词公式

●前束范式表示；消去量词，改名

●与或图表示：析取部分用与节点表示

合取部分用或节点表示

【正向演绎推理--F－规则】

●形如L=>W，L为单一文字

●W为任意与或型谓词公式；(消去量词，改名)

【正向演绎推理—目标谓词】

● 文字的析取式(消去量词，改名)

【正向演绎推理图解】

012':()(()())':()()':()()':()()

F P x Q x R x F P y S y F Q z N z

G S a N a ?∨∧?????∨

? P (x )∨(Q (x )∧R (x ))

Q (x )∧R (x )? P (x )

Q (x )

R (x )

Q (z )

? P (y )

N (x )

? S (x )

F 0

F 1 {x/z }

F 2 {x/y }

{a/x }

{a/x }

N (a )

? S (a )

【代换集一致性】

设有代换集{u 1,u 2,…，u n }，其中每个u i 都是代换{t i1/ v i1, t i2/ v i2,…， t im (i)/ v im (i)}

U1＝{v 11, …, v im(1),…， v n1, …, v nm(n)}（所有下边的变量） U2＝{t 11, …, t im(1),…， t n1, …, t nm(n)} （所有上边的项） {u 1,u 2,…，u n }是一致的，当且仅当U1和U2是可合一 合一复合：U1和U2的最一般合一

解树上所有代换是一致的，则该问题有解，最后的代换是合一复合U

【反向演绎推理--目标公式】

任意谓词公式(消去量词，改名) 与或图表示：与节点对应合取；

或节点对应析取

【反向演绎推理--B －规则】

● W=>L ；

● L 为单一文字；

● W 为任意与或型谓词公式(消去量词，改名)

【反向演绎推理—图解】

()

MEOWS MYERTLE {x /x 5}

{MYRTLE /x }

{FIDO /y }

{y /x 1}

{FIDO /y }

R 1

{FIDO /y }

{x /y 2,y /x 2}

()()(,)

CAT x DOG y AFRAID x y ∧∧?()CAT x ()DOG y (,)

AFRAID x y ?22(,)

AFRAID y x ?5()

CAT x ()

MEOWS x ()

BARKS y ?()

FRIENDLY y 1()

FRIENDLY x ()WAGS TAIL y -()

DOG y R 2

R 5

()

BARKS FIDO ?()WAGS TAIL FEDO -()

DOG FIDO ()

DOG FIDO {FIDO /y }

【正向/反向演绎对比】

【双向演绎推理】

● 分别从基于事实的F-规则正向推理出发，也从基于目

标的B-规则逆向推理出发，同时进行双向演绎推理。 ● 终止的条件：正向推理和逆向推理互相完全匹配。即

所有得到的正向推理与或树的叶节点，正好与逆向推理得到的与或图的叶节点一一对应匹配

【不确定性知识分类】

随机不确定性(概率) 模糊不确定性(软概念) 不完全性(事物了解不充分) 不一致性(时间推移)

【逆概率方法公式】

1

(|)()

(|)(|)()

i i i n

j

j j P E H P H P H E P E H

P H ==

∑

【逆概率—多个证据】

12121

21

(/)(/)(/)()

(/)

(/)(/)(/)()

i i m i i i m n

j

j m j j j P E H P E H P E H P H P H E E E P E H

P E H P E H P H =∑L L L

其实就是bayes 公式。严格要求各证据独立。

【修正因子】

方括号内为修正因子：

)

(])()

|([

)|(H P E P H E P E H P =

【可信度法—不确定性度量】

If E then H (CF(H, E))

其中CF(H, E)为可信度因子/规则强度 CF(H,E)=MB(H,E) - MD(H,E)

【MB 和MD 】

MB （Measure Belief ）： 信任增长度，因证据E 的出现使结论H 为真的信任增长度：

???

??--=否则)(1)

()}(),|(max{1

＝)(当1),(H P H P H P E H P H P E H MB

MD （Measure Disbelief ）：

不信任增长度，因E 的出现使H 为真的不信任增长度：

???

??--=否则)()

()}(),|(min{0＝)(当1),(H P H P H P E H P H P E H MD

因此，CF(H,E)为：

??

??

?

????<-->--=)

()|(当)()|()()(＝)|(当0

)()|(当)(1)

()|(),(H P E H P H P E H P H P H P E H P H P E H P H P H P E H P E H CF

【可信度法--不确定性传播】

组合证据：

E=E 1∧ E 2 ∧… ∧ E n ：

CF(E)=min{CF(E 1) ,CF(E 2) , … CF(E n )}

E=E 1 ∨ E 2 ∨ … ∨ E n ：

CF(E)=max{CF(E 1) ,CF(E 2) , … CF(E n )}

E=? E 1 ：

CF(E)=-CF(E 1)

推理结论的CF 值：

CF(H) = CF(H,E) ? max { 0, CF(E) }

重复结论的CF 值：

【主观贝叶斯法】

表示形式：

if E then (LS, LN ) H ( P(H) )

))(()

,(H P H E LN LS ????→?

【LS 和LN 】

LS ：充分性量度，E 对H 支持程度，范围为[ 0， ∞ ）：

LN ：必要性量度，? E 对H 支持程度，范围为[ 0， ∞ ）：

LS 、LN>0,不独立，有如下约束关系：

当LS>1时，LN<1； 当LS<1时，LN>1； 当LS=1时，LN=1；

通过LN,LS 把先验概率转化为后验概率： ● LS= O(H|E)/ O(H)

P(H|E) 越大，O(H|E)越大，则LS 越大，表明E 对H 为真的支持越强，当 LS → ∞ ，P(H|E) → 1，E 的存在对 H 为真是充分的

● LN=O(H| ? E) /O(H) P(H| ?E )越大，O(H|? E)越大，则LN 越大，表明? E 对 H 为真的支持越强。当 LN = 0 ，P(H| ? E) = 0，E 的不存在导致 H 为假，说明E 对H 是必要的

【几率函数】

【P(E|S)与P(H|S)】

其中C(E|S)由题目给出，用于刻画不确定性，值越大，证明在观察S 下，E 存在的可能性越大。

将两式结合，和得到CP 公式：

【贝叶斯网络图示】

● 以随机变量为节点，以条件概率为节点间关系强度的

有向无环图（Directed Acyclic Graph ，DAG ）

● 每个节点旁的条件概率表(简称CPT)中的值对应一个

条件事件的概率

【条件独立关系】

贝叶斯网络中节点相互独立： (1)给定父节点，一个节点与它的非后代节点是条件独立的 (2)给定一个节点的父节点、子节点以及子节点的父节点(Markov blanket)，这个节点对于其它节点都是条件独立的

【条件独立关系的判定】

d-分离（d-separation)：

给定y ，x 和z 条件独立：(|,)(|)P z x y P z y =

给定y ，x 和z 条件独立：(|,)(|)P z x y P z y =

给定y ，x 和z 不条件独立：(,)()()P x z P x P z =

【贝叶斯网络推理】

概率推理可分为：

因果推理、诊断推理、辩解推理、混合推理

【因果推理】

由原因到结果的推理，自上而下的推理，例如已知L 成立时，求P(M|L) (|)(,|)(,|)P M L P M B L P M B L =+?

【诊断推理】

由结果到原因的推理,自下而上的推理。例如已知?M 成立，求P(?L |?M )

(|)()

(|)()P M L P L P L M P M ?????=

?

【辩解推理】

仅仅给定?B ，求P(?L)。这种情况下，可以说?B 解释?M ，使?L 不确定。

(,|)()

(|,)(,)P M B L P L P L B M P M B ???????=

??

Ch 5.

【FIND-S 算法】

候选假设： “?”：可接受任何值 “φ”：不接受任何值 算法流程：

1.将h 初始化为H 中最特殊假设

2.对每个正例x （循环） 对h 的每个属性约束a i 如果x 满足a i

那么不做任何处理 否则

将h 中a i 替换为x 满足的更一般的约束

3.输出假设h

【候选消除算法】