第3章 搜索推理技术1

3.1

图搜索策略3.2

盲目搜索3.3

启发式搜索3.4

消解原理3.5

规则演绎系统3.6

产生式系统3.7

系统组织技术3.8

不确定性推理3.9

非单调推理3.10小结第3章搜索推理技术3.1图搜索策略图搜索控制策略一种在图中寻找路的方法。图中每个节点对应一个状态，每条连线对应一个操作符。节点和连线（即状态与操作）又分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。图搜索过程1.

建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表（简称OPEN表）。2.

建立一个叫做CLOSED的已扩展节点表（简称CLOSED表），其初始为空表。3.

LOOP：若OPEN表是空表，则失败退出。4.

选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n，它是CLOSED表中节点的编号。5.

若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到（指针将在第7步中设置）。图搜索过程6.扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。7.

对那些未曾在G中出现过的（既未曾在OPEN表上或CLOSED表上出现过的）M成员设置一个通向n的指针，把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。8.

按某一任意方式或按某个探试值，重排OPEN表。9.

GOLOOP。图搜索过程框图3.2盲目搜索概念没有启发信息的一种搜索形式一般只适用于求解比较简单的问题特点不需重排OPEN表种类宽度优先深度优先等代价搜索3.2.1宽度优先搜索1)定义以接近起始节点的程度为依据，进行逐层扩展的节点搜索方法。2)特点搜索是逐层进行的，即在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。一种高代价搜索，但若有解存在，则必能找到它。宽度优先搜索示意图宽度优先算法框图宽度优先搜索算法描述1.

把起始节点放到OPEN表中（如果该起始节点为一目标节点，则求得一个解答）。2.

如果OPEN是个空表，则没有解，失败退出；否则继续。3.

把第一个节点（节点n）从OPEN表移出，并把它放入CLOSED的扩展节点表中。4.

扩展节点n。如果没有后继节点，则转向上述第2步。宽度优先搜索算法描述5.

把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。6.

如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第2步。7.

扩展当前节点后生成的子节点总是置于OPEN表的后端，即OPEN表作为排队表使用，先进先出，使搜索优先向横方向发展。

宽度优先搜索是图搜索一般过程的特殊情况，这实际是将OPEN表作为“先进先出”的队列进行操作。搜索树:搜索过程产生的节点和指针构成一棵隐式定义的状态空间图的子树,称为搜索树。如果问题有解,宽度优先算法能够保证找到一条通向目标节点的最短路径(即找到最优解).如要问题无解,对于有限图,该算法会失败退出，对于无限图,则永远不会终止。宽度优先搜索算法说明八数码难题将牌移入空格的顺序：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展26个节点，才求得解（目标节点）。八数码难题的宽度优先搜索树3.2.2深度优先搜索1定义首先扩展最新产生（即最深的）节点。深度相等的节点可以任意排列。2)特点首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；仅当搜索到达一个没有后裔的状态时，才考虑另一条替代的路径。3)节点深度定义:起始节点(即根节点)的深度为0.任何其他节点的深度等于其父辈节点的深度加1.4)深度界限:–为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去),往往给出一个节点扩展的最大深度,称为深度界限.–任何节点如果达到了深度界限,那么都将把它们作为没有后继节点来处理.–即使应用了深度界限,深度优先搜索所求得的解答路径也不一定就是最短路径.3.2.2深度优先搜索深度优先搜索示意图深度优先搜索算法描述1.

把起始节点S放到未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解。2.

如果OPEN为一空表，则失败退出。3.

把第一个节点（节点n）从OPEN表移到CLOSED表。4.

如果节点n的深度等于最大深度，则转向(2)。5.

扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向(2)。6.

如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向(2)。深度优先搜索算法描述起始把S放入OPEN表OPEN表是否为空?把OPEN表中的第一个节点n移入CLOSED表扩展节点n,把其后裔n放入OPEN表的前端,提供返回节点n的指针失败是否是否有任何后继节点为目标节点?成功是否S是否为目标节点?成功是节点n的深度是否等于深度界限?是否否八数码难题的深度优先搜索树

思考题：有界深度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径吗？一般不能保证找到最优解。当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制。最坏情况时，搜索空间等同于穷举。与回溯法的差别：图搜索。是一个通用的与问题无关的方法。深度优先搜索的性质为什么需要启发式搜索

效率低，耗费过多的计算空间与时间。可能带来组合爆炸。分析前面介绍的宽度优先、深度优先搜索，或等代价搜索算法,其主要的差别是OPEN表中待扩展节点的顺序问题。人们就试图找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大为提高。3.3启发式搜索定义进行搜索技术一般需要某些有关具体问题的领域的特性信息，把此种信息叫做启发信息。把利用启发信息的搜索方法叫做启发性搜索方法。特点重排OPEN表，选择最有希望的节点加以扩展种类有序搜索、A*算法等3.3启发式搜索启发式搜索策略

有关具体问题领域的信息常常可以用来简化搜索。一个比较灵活(但代价也较大)的利用启发信息的方法，是应用某些准则来重新排列每一步OPEN表中所有节点的顺序。然后，搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数(evalutionfunction)。

3.3.1启发式搜索策略和估价函数估价函数

为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。一个节点的“希望”有几种定义方法一种方法是估算目标节点到此节点的距离；另一种方法认为，解答路径包括被估价过的节点，并计算全条路径的长度或难度。每个不同的衡量标准只能考虑该问题中这个节点的某些决定性特性，或者对给定节点与目标节点进行比较，以决定相关特性。表示方法f(n)——表示节点n的估价函数值3.3.1启发式搜索策略和估价函数建立估价函数的一般方法1.

试图确定一个处在最佳路径上的节点的概率；2.

提出任意节点与目标集之间的距离量度或差别量度；3.或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。3.3.1启发式搜索策略和估价函数评价函数的格式

应用这种评价函数来实现启发式搜索的典型是算法A，其将评价函数f设计为：

f(n)=g(n)+h(n)n--搜索图中的某个当前被扩展的节点；f(n)--从初始状态节点s,经由节点n到达目标状节点ng，估计的最小路径代价；g(n)--从s到n,估计的最小路径代价；h(n)--从n到ng,估计的最小路径代价；

3.3.1启发式搜索策略和估价函数启发式搜索算法框图启发式搜索算法描述1.

把起始节点S放到OPEN表中,计算f(S),并把其值与节点S联系起来。2.

如果OPEN表是个空表,则失败退出,无解。3.

从OPEN表中选择一个f值最小的节点i，结果有几个节点合格,当其中有一个为目标节点时,则选择此目标节点,否则就选择其中任一个节点作为节点i。4.

把节点i从OPEN表中移出,并把它放入CLOSED

的扩展节点表中。5.

如果i是个目标节点,则成功退出,求得一个解。启发式搜索算法描述6.

扩展节点i,生成其全部后继节点.对于i的每一个后继节点j:计算f(j)。如果j既不在OPEN表中,也不在CLOSED表中,则用估价函数f把它添入OPEN表。从j加一指向父辈节点i的指针(以便找到目标节点时记住一个解答路径)。如果j已在OPEN表或CLOSED表上,则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f值.如果新的f值较小,则：以此新值取代旧值。从j指向i,而不是指向它的父辈节点。如果节点j在CLOSED表中,则把它移回OPEN表。7.

转向(2),即GOTO(2)。

启发式搜索—A算法例子定义评价函数：

f(n)=g(n)+h(n)

g(n)为从初始节点到当前节点的耗散值

h(n)为当前节点“不在位”的将牌数

启发式搜索—A算法例子

1)记号:g*(n)：从s到n的最短路径的耗散值h*(n)：从n到g的最短路径的耗散值f*(n)=g*(n)+h*(n)：从s经过n到g的最短路径的耗散值

2)估价函数f是f*的一个估计:f(n)=g(n)+h(n)，其中g(n)是g*(n)的估计,h(n)是h*(n)的估计.g(n)：通常为从s到n这段路径的实际代价，则有g(n)≥g*(n);h(n)：是从节点n到目标节点Sg的最优路径的估计代价.它的选择依赖于有关问题领域的启发信息,叫做启发函数.例如八数码中的h(n)。最佳图搜索算法A*（A*算法）

3)定义

在A算法中，如果满足条件：

h(n)≤h*(n)

则A算法称为A*算法。

4)A*算法的特点若存在从初始节点S0到目标节点Sg的路径,则A*算法必能结束在最佳路径上。使用启发函数h(n)的A*算法，比不使用h(n)(h(n)≡0)的算法,求得最佳路径时扩展的节点数要少。一般来说,在满足h(n)≤h*(n)的条件下,h(n)的值越大,说明它携带的启发性信息越多,搜索时扩展的节点就越少,搜索效率就越高,当h(n)=h*(n)时,则不会去扩展多余的节点就可找到解。最佳图搜索算法A*（A*算法）思考题：八数码难题g:实际走的步数(节点深度)。w(n):当前节点“不在位”的将牌数。h(n)=p(n):移动到目标状态相应位置所需走步的总和.（在不设阻的情况下)思考题：八数码难题基础知识谓词公式、某些推理规则以及置换合一等概念。子句：由文字的析取组成的公式；一个原子公式和原子公式的否定都叫做文字。消解：当消解可使用时，消解过程被应用于母体子句对，以便产生一个导出子句。例如，如果存在某个公理E1∨E2和另一公理～E2∨E3，那么，E1∨E3在逻辑上成立。这就是消解，而称E1∧E3为E1∨E2和～E2∨E3的消解式。3.4消解原理子句集的求取

例子，将下列谓词演算公式化为一个子句集

3.4消解原理(∀x){P(x)⇒{(∀y)[P(y)⇒P(f(x,y))]∧～(∀y)[Q(x,y)⇒

P(y)]}}1.消去蕴涵符号只应用∨和～符号，以～A∨B替换A→B。(∀x)｛～P(x)∨{(∀y)［~P(y)∨P(f(x,y))］∧～(∀y)［~Q(x,y)∨P(y)］}}2.减少否定符号的辖域每个否定符号～最多只用到一个谓词符号上，并反复应用狄·摩根定律。

(∀x)｛～P(x)∨｛(∀y)［～P(y)∨P(f(x,y))］∧(∃y)［Q(x,y)∧～P(y)］｝｝3.4.1子句集的求取3.对变量标准化

对哑元（虚构变量）改名，以保证每个量词有其自己唯一的哑元。

(∀x){～P(x)∨{(∀y)［～P(y)∨P(f(x,y))］

∧(∃w)［Q(x,w)∧～P(w)］}}4.消去存在量词

以Skolem函数代替存在量词内的约束变量，然后消去存在量词

(∀x)｛～P(x)∨{(∀y)[~P(y)∨P(f(x,y))］∧［Q(x,g(x))∧～P(g(x))］｝｝式中，w=g(x)为一Skolem函数。3.4.1子句集的求取5.化为前束形把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。前束形=

{前缀}{母式}

全称量词串无量词公式

(∀x)(∀y){～P(x)∨{[～P(y)∨P(f(x,y))]∧[Q(x,g(x))∧～P(g(x))]}}6.把母式化为合取范式任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。

(∀x)(∀y){[～P(x)∨～P(y)∨P(f(x,y))]∧[～P(x)∨Q(x,g(x))]∧[～P(x)∨～P(g(x))]}3.4.1子句集的求取7.消去全称量词

所有余下的量词均被全称量词量化了。消去前缀，即消去明显出现的全称量词。

{[～P(x)∨～P(y)∨P(f(x,y))]∧[～P(x)∨Q(x,g(x))]∧[～P(x)∨～P(g(x))]}8.消去连词符号∧用{A,B}代替(A∧B)，消去符号，∧。最后得到一个有限集，其中每个公式是文字的析取。～P(x))∨～P(y)∨P(f(x,y))

～P(x)∨Q(x,g(x))

～P(x)∨～P(g(x))3.4.1子句集的求取9.更换变量名称可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。～P(x1)∨～P(y)∨P［f(x1,y)］～P(x2)∨Q［x2,g(x2)］～P(x3)∨～P［g(x3)］说明：并不是所有问题的谓词公式化为子句集都需要上述9个步骤。对于某些问题，可能不需要其中的一些步骤。3.4.1子句集的求取消解式的定义令L1，L2为两任意原子公式；L1和L2具有相同的谓词符号，但一般具有不同的变量。已知两子句L1∨α和～L2∨β，如果L1和L2具有最一般合一σ，那么通过消解可以从这两个父辈子句推导出一个新子句(α∨β)σ。这个新子句叫做消解式。3.4.2消解推理规则消解式求法3.4.2消解推理规则含有变量的子句之消解式要把消解推理规则推广到含有变量的子句，必须找到一个作用于父辈子句的置换，使父辈子句含有互补文字。3.4.3含有变量的消解式基本思想把要解决的问题作为一个要证明的命题，其目标公式被否定并化成子句形，然后添加到命题公式集中去,把消解反演系统应用于联合集，并推导出一个空子句(NIL)，产生一个矛盾，这说明目标公式的否定式不成立，即有目标公式成立，定理得证，问题得到解决。这与数学中反证法的思想十分相似。反演求解步骤给出一个公式集{S}

和自标公式L，通过反证或反演来求证目标公式L，其证明步骤如下：

1.

否定L，得～；

2.

把～L添加到S中去；

3.

把新产生的集合{～L，S}化成子句集；

4.

应用消解原理，力图推导出一个表示矛盾的空子句3.4.4消解反演求解过程反演求解的正确性设公式L在逻辑上遵循公式集S，那么按照定义满足S的每个解释也满足L。决不会有满足S的解释能够满足～L的，所以不存在能够满足并集S∪{～L}的解释。如果一个公式集不能被任一解释所满足，那么这个公式是不可满足的。因此，如果L在逻辑上遵循S，那么S∪{～L}是不可满足的。可以证明，如果消解反演反复应用到不可满足的子句集，那么最终将要产生是不可满足的。可以证明，如果消解反演反复应用到不可满足的子句集，那么最终将要产生空子句NIL。因此，如果L在逻辑上遵循S，那么由并集S∪{～L}消解得到的子句，最后将产生空子句；反之，可以证明，如果从S∪{～L}的子句消解得到空子句，那么L在逻辑上遵循S。3.4.4消解反演求解过程消解推理的常用规则3.4.4消解反演求解过程例子—储蓄问题前提：每个储蓄钱的人都获得利息。结论：如果没有利息，那么就没有人去储蓄钱消解反演求解过程—储蓄问题(1）规定原子公式：

S(x,y)

表示“x储蓄y”

M(x)

表示“x是钱”

I(x)

表示“x是利息”

E(x，y)

表示“x获得y”(2）用谓词公式表示前提和结论：前提：(x)[(y)(S(x,y))∧M(y)][(y)(I(y)∧E(x,y))]结论：～(x)I(x)(x)(y)(M(y)→～S(x,y))(3)

化为子句形证明：消解反演求解过程—储蓄问题把前提化为子句形：1)

～S(x,y)∨～M(y)∨I(f(x))2)

～S(x,y)∨～M(y)∨E(x,f(x))把结论化为子句形：3)

～I(z)4)S(a,b)5)M(b)(4)

消解反演求NIL设已知：(1)能阅读者是识字的；(2)海豚不识字；(3)有些海豚是很聪明的。试证明：有些聪明者并不能阅读。思考题：思考题：然后把上述各语句翻译为谓词公式：(1)

x(R(x)→L(x))(2)

x(D(x)→乛L(x))已知条件(3)

x(D(x)∧I(x))(4)

x(I(x)∧乛R(x))需证结论证：首先，定义如下谓词：R(x)：x能阅读。L(x)：x识字。I(x)：x是聪明的。D(x)：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)归结过程演绎树如图所示。思考题：从反演树求取答案步骤把问题的已知条件用谓词公式表示出来，并化为相应的子句集；把问题的目标的否定用谓词公式表示出来，并化为子句集；对目标否定子句集中的每个子句，构造该子句的重言式（即把该目标否定子句和此目标否定子句的否定之间再进行析取所得到的子句），用这些重言式代替相应的目标否定子句，并把这些重言式加入到前提子句集中，得到一个新的子句集。对这个新的子句集，应用消解原理求出其反演证明树，这时证明树的根子句不为空，称这个证明树为修改证明树；用修改证明树的根子句作为回答语句，则答案就在此根子句中。反演求解过程

如果无论约翰(JOHN)到哪里去,菲多(FIDO)也就去那里,那么如果约翰在学校里,菲多在哪里呢?

解：定义谓词：

AT（x,y）:表示x在y处

1.已知的谓词表示:{(∀x)[AT(JOHN,x)→AT(FIDO,x)],AT(JOHN,SCHOOL)}

化为子句集:{~AT(JOHN,y)∨AT(FIDO,y),AT(JOHN,SCHOOL)}反演求解过程2.目标否定的谓词表示：

~(∃x)AT(FIDO,x)=>(∀x)~AT(FIDO,x)

化为子句集:{~AT(FIDO,x)}3.构造目标否定子句的重言式,并代替原子句

{~AT(FIDO,x)∨AT(FIDO,x)}4.将3得到的子句集加入前提子句集中:G={~AT(JOHN,y)∨AT(FIDO,y),AT(JOHN,SCHOOL),~AT(FIDO,x)∨AT(FIDO,x)}反演求解过程5.对新子句集G应用消解原理求出反演树:G={~AT(JOHN,y)∨AT(FIDO,y),AT(JOHN,SCHOOL),~AT(FIDO,x)∨AT(FIDO,x)}反演求解过程定义基于规则的问题求解系统运用If→Then规则来建立，每个if可能与某断言(assertion)集中的一个或多个断言匹配。有时把该断言集称为工作内存，then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统。在这种系统中，通常称每个if部分为前项，称每个then部分为后项。3.5规则演绎系统规则正向演绎系统:是从已知事实出发,正向使用规则对事实表达式的与或树进行变换，直到找到一个含有目标节点的一致解树为止。已知事实:事实表达式的与或树。目标表达式：限制为文字的析取式。F规则:L→W,其中L为单文字,W为与或。结束条件:目标表达式是析取式.得到结束于目标节点的一致解树。3.5.1规则正向演绎系统1.事实表达式的与或形变换2.事实表达式的与或树表示3.规则的与或形变换4.目标公式的表示形式5.规则正向演绎推理过程3.5.1规则正向演绎系统1.事实表达式的与或形变换

–规则正向演绎系统中要求事实表达式化简为与

或形。(1)消去”蕴含”和”双条件”符号;(2)减小否定符号的辖域,使否定符号只作用于原子公式;(3)利用Skolem函数消去存在量词;(4)对变量进行换名，使得不同的主合取元，具有不同的变量名;(5)隐去全称量词，默认公式中的变量受全称量词约束。3.5.1规则正向演绎系统1.

事实表达式的与或形变换把事实表示为非蕴涵形式的与或形，作为系统的总数据库。例如有事实表达式：

(∃u)(∀v)｛Q(v,u)∧～［(R(v)∨P(v))∧S(u,v)］｝把它化为：

Q(v,A)∧｛［～R(v)∧～P(v)］∨～S(A,v)｝对变量更名标准化，使得同一变量不出现在事实表达式的不同主要合取式中，得：

Q(w,A)∧｛［～R(v)∧～P(v)］∨～S(A,v)｝

规则正向演绎系统的求解过程2.

事实表达式的与或图表示将上例与或形的事实表达式用与或图来表示，如下图所示：规则正向演绎系统的求解过程3.

与或图的F规则变换

这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。我们把允许用作规则的公式类型限制为下列形式：

L⇒W

式中：L是单文字；W为与或形的唯一公式。规则正向演绎系统的求解过程4.

作为终止条件的目标公式

应用F规则的目的在于从某个事实公式和某个规则集出发来证明某个目标公式。在正向推理系统中，这种目标表达式只限于可证明的表达式，尤其是可证明的文字析取形的目标公式表达式。用文字集表示此目标公式，并设该集各元都为析取关系。结论：当正向演绎系统产生一个含有以目标节点作为终止的解图时，此系统就成功地终止。

规则正向演绎系统的求解过程①命题逻辑的规则正向演绎过程

F规则变换:如果在与或树中有一个叶节点刚好与某F规则L→W的前件L匹配，则将该叶节点与L用一个匹配弧连接起来，将规则后件W添加到与或树中。这样,就对与或树用规则L→W实施了一次变换,得到了一个“更新”了的与或树。规则正向演绎系统的求解过程规则正向演绎系统的求解过程例:事实表达式的与或为:((P∨Q)∧R)∨(S∧(T∨U))

规则:S→(X∧Y)∨Z规则正向演绎系统的求解过程②谓词逻辑的规则正向演绎过程a)事实表达式进行与或树表示;b)规则转换成F规则L→W,其中L为单文字,W为与或形;c)目标表达式变换成子句形;d)对与或树进行F规则变换;e)结束条件:找到所有叶节点都与目标节点匹配的一致解树.规则正向演绎系统的求解过程F规则变换:

设与或树中有一个端节点的文字L′和L可合一,mgu是u，则这条规则可应用,这时用匹配弧连接的后裔节点是L，它是规则后项Wu对应的与或树表示的根节点,在匹配弧上标记有u,表示用u置换后可与规则匹配。规则正向演绎系统的求解过程例:事实与或形表示:P(A,y)∨(Q(x,A)∧R(B,y))

规则蕴涵式:P(z,B)→(S(z)∨X(B))图应用规则变换后得到的与或树有两个解树,对应的两个子句是:S(A)∨X(B)∨Q(x,A)S(A)∨X(B)∨R(B,B)事实和规则组成的子句集,对文字P进行归结:①P(A,y)∨Q(x,A)②P(A,y)∨R(B,y)③￢P(z,B)∨S(z)∨X(B)④R(B,B)∨S(B)∨X(B)②③归结σ={A/z,B/y}⑤Q(x,A)∨S(A)∨X(B)①③归结σ={A/z,B/y}规则正向演绎系统的求解过程定义逆向规则演绎系统是从then向if进行推理的，即从目标或动作向事实或状况条件进行推理的。逆向推理过程1.

目标表达式的与或形式

逆向演绎系统能够处理任意形式的目标表达式。首先，采用与变换事实表达式同样的过程，把目标公式化成与或形。

3.5.2规则逆向演绎系统2.

与或图的B规则变换

B规则是建立在确定的蕴涵式基础上的，正如正向系统的F规则一样。不过，我们现在把这些B规则限制为：

WL

形式的表达式。其中，W为任一与或形公式，L为文字，而且蕴涵式中任何变量的量词辖域为整个蕴涵式。3.

作为终止条件的事实节点的一致解图逆向系统成功的终止条件是与或图包含有某个终止在事实节点上的一致解图。

3.5.2规则逆向演绎系统基于规则的正向演绎系统和逆向演绎系统的特点和局限性正向演绎系统能够处理任意形式的if表达式，但被限制在then表达式为由文字析取组成的一些表达式。逆向演绎系统能够处理任意形式的then表达式，但被限制在if表达式为文字合取组成的一些表达式。双向(正向和逆向)组合演绎系统具有正向和逆向两系统的优点，克服各自的缺点。

3.5.3规则双向演绎系统双向(正向和逆向)组合演绎系统的构成正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成，并分别用F规则和B规则来修正。终止条件组合演绎系统的主要复杂之处在于其终止条件，终止涉及两个图结构之间的适当交接处。当用F规则和B规则对图进行扩展之后，匹配就可以出现在任何文字节点上。

3.5.3规则双向演绎系统3.6产生式系统产生式系统的组成产生式系统的推理产生式系统的控制策略产生式系统中的知识表示1.事实的表示：

–确定性的知识：命题、谓词、三元组

(对象,属性,值)或(关系,对象1,对象2)

老李和老张是朋友:

（Friend,Li,zhang）

–不确定性的知识：四元组

(对象，属性，值，可信度因子)

极少数花的颜色是黑的产生式系统的组成2.推理过程和行为(规则)的表示产生式或规则：P→QIFPTHENQ–P是产生式的前提，或称为前件

–Q是一组结论或操作，或称为后件

IF(动物,本领,会下蛋)AND(动物,本领,会飞)THEN(动物,类别,鸟)IF(病人,症状,咳嗽)AND(病人,症状,流涕)THEN(病人,疾病,感冒,0.85)产生式系统的组成产生式系统的组成产生式系统由3个部分组成，即总数据库(或全局数据库)、产生式规则和控制策略。

产生式系统的组成1.综合数据库

–是一个用来存放与求解问题有关的各种当前信息的数据结构。

–问题的初始状态、事实、证据、中间推理结论及最后结果等。2.产生式规则库

–是用来存放与求解问题有关的某个领域知识的规则的集合及其交换规则。3.控制系统：一组程序，用来控制系统的运行，决定推理方式和控制策略。

–从规则库中选择规则与综合数据库中的已知事实进行匹配。

–当匹配成功的规则多于一条时，按照某种策略从中选出一条规则去执行。

–匹配成功时，如果规则的后件是结论则加入综合数据库中，如果是操作则执行这些操作。

–如果当前执行规则的后件满足结束条件，则停止推理。

–记住应用过的规则序列，便于最终给出问题的解路径。产生式系统的组成图产生式系统推理流程

产生式系统的组成用于动物识别的产生式系统：

②r3,r4,r5,r6匹配失败有暗斑点长脖子长腿有奶有蹄初始综合数据库：长颈鹿，斑马目标集合：顺序选择规则试与事实匹配，将匹配成功的规则执行并做标记：有暗斑点长脖子长腿有奶有蹄哺乳动物综合数据库：①r1匹配失败，r2匹配成功:④r8,r9,r10匹配失败⑤r11匹配成功③r7匹配成功：有暗斑点长脖子长腿有奶有蹄哺乳动物有蹄类综合数据库：综合数据库：有暗斑点长脖子长腿有奶有蹄哺乳动物有蹄类

长颈鹿长颈鹿已在目标集合中，故推理成功结束．用于动物识别的产生式系统：控制策略与常用算法产生式系统的控制策略：当有多条规则可用时，对规则的选择和处理方式。1.不可撤回方式思想：无论所使用过的规则是否有效，都不再撤回它的应用。优点：控制过程简单。缺点：不一定能找到最优解。2.回溯方式思想：如果确定某条规则的应用不利于问题求解则撤回此规则的应用。两个问题：如何确定回溯条件和减少回溯次数。优点：容易实现且空间代价小。3.图搜索方式思想：用图或树把应用规则路径记录下来，从中选取最优路径。优点：有利于寻找最优解。控制策略与常用算法产生式系统的推理策略可分为：正向推理和反向推理两种基本方式。正向推理反向推理产生式系统的推理方式事实(数据)驱动、前向链接推理目标驱动、逆向链接推理控制策略与常用算法1.正向推理正向推理算法：步1将初始事实/数据置入动态数据库；步2用动态数据库中的事实/数据，匹配/测试目标条件，若目标条件满足，则推理成功，结束。步3用规则库中各规则的前提匹配动态数据库中的事实/

数据，将匹配成功的规则组成待用规则集；步4若待用规则集为空，则运行失败，退出。步5将待用规则集中各规则的结论加入动态数据库，或者执行其动作，转步2；可以看出，随着推理的进行，动态数