人工智能重点总结(正式版)(3)

(7)T(B)∨T(C)

下面先求谁是老实人。把¬T(x)∨Ansewer(x)并入S得到S1。即多一个子

句：

(8)¬T(x)∨Ansewer(x)

应用归结原理对S1进行归结：

(9)¬T(A)∨T(C)

(10)T(C)

(11)Ansewer(C)(1)和(7)归结(6)和(9)归结(8)和(10)归结

所以C是老实人，即C从不说假话。

下面证明A不是老实人，即证明¬T(A)。

对¬T(A)进行否定，并入S中，得到子句集S2，即S2比S多如下子句：

(8)¬(¬T(A)),即T(A)

应用归结原理对S2进行归结：

(9)¬T(A)∨T(C)

(10)¬T(A)

(11)NIL(1)和(7)归结(2)和(9)归结(8)和(10)归结

西电大三下学期09级人工智能重点整理

所以A不是老实人。同样可以证明B也不是老实人。

应用归结原理的练习

1.设已知：

（1）如果x是y的父亲，y是z的父亲，则x是z的祖父；

（2）每个人都有一个父亲。

试用归结演绎推理证明：对于某人u，一定存在一个人v，v是u的

祖父。

2.张某被盗，公安局派出五个侦察员去调查。研究案情时，侦察员A说

“赵与钱中至少有一人作案”；侦察员B说“钱与孙中至少有一人作

案”；侦察员C说“孙与李中至少有一人作案”；侦察员D说“赵与

孙中至少有一人与此案无关”；侦察员E说“钱与李中至少有一人与

此案无关”。如果这五个侦察员的话都是可信的，试用归结演绎推理

求出谁是盗窃犯。

3.2不确定性------只考模糊理论

简单模糊推理

知识中只含有简单条件，且不带可信度因子的模糊推理称为简单模

糊推理。

合成推理规则：对于知识

IFxisATHENyisB

首先构造出A与B之间的模糊关系R，然后通过R与证据的合成求

出结论。

如果已知证据是

xisA’

且A与A’可以模糊匹配，则通过下述合成运算求取B’：

B’=A’ R

如果已知证据是

yisB’

西电大三下学期09级人工智能重点整理

且B与B’可以模糊匹配，则通过下述合成运算求出A’：

A’=R B’

模糊集的运算

模糊集上的运算主要有：包含、交、并、补等等。

1.包含运算

定义2.14设A，B∈F(U)，若对任意u∈U，都有

μB(u)≤μA(u)

成立，则称A包含B，记为B A。

2.交、并、补运算

定义2.15设A，B∈F(U)，以下为扎德算子

A∪B:µA∪B(u)=max{µA(u),µB(u)}=µA(u)∨µB(u)u∈U

A∩B:µA∩B(u)=min{µA(u),µB(u)}=µA(u)∧µB(u)u∈U

¬A:µ¬A(u)=1 µA(u)

例2.9设U={u1,u2,u3}，

A=0.3/u1+0.8/u2+0.6/u3

B=0.6/u1+0.4/u2+0.7/u3

则：

A∩B=(0.3∧0.6)/u1+(0.8∧0.4)/u2+(0.6∧0.7)/u3

=0.3/u1+0.4/u2+0.6/u3

A∪B=(0.3∨0.6)/u1+(0.8∨0.4)/u2+(0.6∨0.7)/u3

=0.6/u1+0.8/u2+0.7/u3

¬A=(1-0.3)/u1+(1-0.8)/u2+(1-0.6)/u3

=0.7/u1+0.2/u2+0.4/u3

3.模糊变换

定义2.24设A={μA(u1),μA(u2),…,μA(un)}是论域U上的模糊

集，R是U×V上的模糊关系，则

A°R=B

西电大三下学期09级人工智能重点整理

称为模糊变换。

例2.18设A={0.2,0.5,0.3}

3.3搜索--广度优先、深度优先、全局择优三选一

状态空间的一些基本概念

1)很多问题的求解过程都可以看作是一个搜索过程。问题及其求解过

程可以用状态空间表示法来表示。

2)状态空间用“状态”和“算符”来表示问题。

状态

状态用以描述问题在求解过程中不同时刻的状态，一般用一个向

量表示：

…)SK=(Sk0,Sk1,SK=(Sk0,Sk1,…

算符

使问题从一个状态转变为另一个状态的操作称为算符。在产生式

系统中，一条产生式规则就是一个算符。

状态空间

西电大三下学期09级人工智能重点整理

由所有可能出现的状态及一切可用算符所构成的集合称为问题

的状态空间。

3)采用状态空间求解问题，可以用下面的一个三元组表示：

(S,F,G)

其中S是问题初始状态的集合；F是算符的集合；G是目标状态

的集合。

采用状态空间表示方法，首先要把问题的一切状态都表示出来，其

次要定义一组算符。

问题的求解过程是一个不断把算符作用于状态的过程。如果在使用

某个算符后得到的新状态是目标状态，就得到了问题的一个解。这个解

就是从初始状态到目标状态所采用算符的序列。使用算符最少的解称为

最优解。

对任何一个状态，可使用的算符可能不止一个。这样由一个状态所

生成的后继状态就可能有多个。此时首先对哪一个状态进行操作，就取

决于搜索策略。

OPEN表和CLOSE表

OPEN表用于存放刚生成的节点。对于不同的搜索策略，节点在

OPEN表中的排列顺序是不同的。

CLOSE表用于存放将要扩展的节点。对一个节点的扩展是指：用所

有可适用的算符对该节点进行操作，生成一组子节点

搜索的一般过程

1.把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G；

西电大三下学期09级人工智能重点整理

2.

3.

4.

5.检查OPEN表是否为空，若为空则问题无解，退出；把OPEN表的第一个节点取出放入CLOSE表，并计该节点为n；考察节点n是否为目标节点。若是，则求得了问题的解，退出；扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点

记做集合M，并把这些子节点作为节点n的子节点加入G中；

6.针对M中子节点的不同情况，分别进行如下处理：

1)对于那些未曾在G中出现过的M成员设置一个指向父节点（即

节点n）的指针，并把它们放入OPEN表；（不在OPEN表）

2)对于那些先前已经在G中出现过的M成员，确定是否需要修改

它指向父节点的指针；（在OPEN表中）

3)对于那些先前已在G中出现并且已经扩展了的M成员，确定是

否需要修改其后继节点指向父节点的指针；（在CLOSE表中）

7.

8.按某种搜索策略对OPEN表中的节点进行排序；转第2步。

一些说明

一个节点经一个算符操作后一般只生成一个子节点。但适用于一个

节点的算符可能有多个，此时就会生成一组子节点。这些子节点中

可能有些是当前扩展节点的父节点、祖父节点等，此时不能把这些

先辈节点作为当前扩展节点的子节点。

一个新生成的节点，它可能是第一次被生成的节点，也可能是先前

已作为其它节点的子节点被生成过，当前又作为另一个节点的子节

点被再次生成。此时，它究竟应选择哪个节点作为父节点？一般由

原始节点到该节点的代价来决定，处于代价小的路途上的那个节点

就作为该节点的父节点。

在搜索过程中，一旦某个被考察的节点是目标节点就得到了一个解。

该解是由从初始节点到该目标节点路径上的算符构成。

如果在搜索中一直找不到目标节点，而且OPEN表中不再有可供扩

展的节点，则搜索失败。

通过搜索得到的图称为搜索图，搜索图是状态空间图的一个子集。

西电大三下学 …… 此处隐藏：2003字，全部文档内容请下载后查看。喜欢就下载吧 ……