第三章 确定性推理PPT课件

第三章确定性推理按所用知识的确定性，推理可以确定性和不确定性推理。

所谓确定性推理指的是推理所用的知识都是精确的，推出的结论也是精确的。

比如一个事件是否为真，其推理的结果只能是真或者假，绝对不可能出现第三种可能性。

确定性推理的方法有很多，具体有图搜索策略、盲目搜索、启发式搜索、消解原理、规则演绎系统、产生式系统等等第一节图搜索策略●搜索的基本概念➢搜索分为盲目搜索和启发式搜索⏹盲目搜索：无信息搜索，在搜索过程中只按预先规定的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略，效率不高，只适合求解简单问题⏹启发式搜索：有信息搜索，在搜索求解问题的过程中，根据问题本身的特性或搜索过程中产生的一些信息来不断地改变或调整搜索的方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解●图搜索策略在人工智能中，搜索问题一般包括两个重要的问题：➢搜索什么：搜索什么通常指的就是目标。

➢在哪里搜索：在哪里搜索就是“搜索空间”。

搜索空间通常是指一系列状态的汇集，因此称为状态空间。

所以，人工智能中的搜索可以分成两个阶段：➢状态空间的生成阶段➢在该状态空间中对所求问题状态的搜索一般图搜索（状态空间搜索）的基本思想1.问题状态用图数据结构的结点表示；2.从初始状态（结点）开始，对选定的结点选择满足条件的操作符，操作符作用后产生新的结点（状态）；3.检查新产生的子结点中是否有目标结点：有则找到了问题的解；4.否则重复上述过程直至产生目标结点，或全部结点处理完无解。

状态空间搜索的基本思想➢节点扩展的概念⏹扩展：就是用合适的算符对某个节点进行操作生成一组后继节点，扩展过程实际上就是求后继节点的过程⏹已扩展节点：对状态空间图中的某个节点，如果求出了它的后继节点，则此节点为已扩展的节点⏹未扩展节点：对状态空间图中的某个节点，如果尚未求出它的后继节点，则此节点称为未扩展节点在对状态空间图搜索求解时，将为扩展的节点存于一个名为OPEN的表中，而将已扩展的节点存于一个名为CLOSED的表中搜索的目的是为了寻找初始节点到目标节点的路径，所以在搜索过程中就得随时记录搜索轨迹。

第三章确定性推理第四节消解原理消解反演如欲证明Q为P1 ,P2 ,…,Pn的逻辑结论，只需证(P1∧P2∧…∧Pn)∧¬Q是不可满足的，或证明其子句集是不可满足的。

而子句集的不可满足性可用归结原理来证明。

➢应用归结原理证明定理的过程称为归结（消解）反演。

➢设F为已知前提的公式集，Q为目标公式(结论)，用归结反演进行证明的步骤是：1. 否定Q，得到¬Q；2. 把¬Q并入到公式集F中，得到{F, ¬Q};3. 把公式集{F, ¬Q}化为子句集S；4. 应用消解推理规则对子句集S中的子句进行归结，并把每次归结得到的归结式都并入S 中。

如此反复进行，若出现了空子句，则停止归结。

反演证明过程的正确性：设S＝{F1,…,F n }是前提条件，L是欲求证的结论则，从前提条件推出结论的问题，可以表示成： F1∧…∧F n L ＝～（F1∧…∧F n）∨L并证明其永真（永远成立）先将公式取“非”：～（～（F1∧…∧F n）∨L）＝（F1∧…∧F n）∧～ L＝ F1∧…∧F n∧～ L利用消解原理来证明它是永假的（即，构造一个反演）实际中，我们可以将F1∧…∧F n∧～ L中的每一个部分化成子句集（化法任选），合并后得到完整的子句集，然后利用消解原理导出空子句（反演）反演求解过程从反演树求取某一个问题的答案，其过程为：①将前提条件用谓词表示出来，并化成子句集 S②将目标公式（问题）用谓词表示出来，把由目标公式的否定所产生的子句及其非（目标公式否定之否定）用析取连接词相连组成一个新子句（重言式），加到 S 构成新的子句集S’③对子句集S’ ，进行消解演绎，直到得到某一个子句为止④将此子句作为问题的答案⏹举例：已知三个条件✓F1:：王(Wang)先生是小李(Li)的老师✓F2：小李与小张(Zhang)是同班同学✓F3：如果x与y是同班同学，则x的老师就是y的老师问题：小张的老师是谁？①定义谓词T(x , y) : x 是 y 的老师C(x , y) : x 与 y 是同班同学②用谓词表示前提条件与目标（问题）：前提：F1：T(Wang , Li)F2：C(Li , Zhang)F3： (∀x) (∀y) (∀z) (C(x,y)∧T(z,x) ⇒T(z,y))目标：G： (∃x)T(x,Zhang)～ G：～ (∃x)T(x,Zhang)=(∀x) (～ T(x,Zhang))③求出子句集：前提的子句集：T(Wang, Li)C(Li, Zhang)～ C(x,y) ∨～ T(z,x) ∨ T(z,y)目标的否定的子句及其非组成重言式：～ T(x,Zhang) ∨ T(x,Zhang)④完整的子句集：(1) T(Wang, Li)(2) C(Li, Zhang)(3) ～C(x,y) ∨～T(z,x) ∨ T(z,y)(4) ～T(u,Zhang) ∨ T(u,Zhang)⑤消解演绎的过程(1) T(Wang, Li)(2) C(Li, Zhang)(3) ～C(x,y) ∨～T(z,x) ∨ T(z,y)(4) ～T(u,Zhang) ∨ T(u,Zhang)(5) ～C(Li ,y) ∨ T(Wang,y) (1)(3) mgu={Wang/z, Li/x)}第五节规则演绎系统●规则演绎的基本概念上面所讲的归结反演系统把所有的表达式都转换为子句形式，这样做虽然在逻辑上是等价的，但也丧失了很多有用的信息。

第三章确定性推理●等代价搜索概念➢宽度优先搜索的一种推广。

➢不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。

➢搜索树中每条连接弧线上的有关代价，表示时间、距离等花费。

等代价搜索中的几个记号➢起始节点记为 S；➢从节点i到它的后继节点j的连接弧线代价记为 c(i,j)➢从起始节点S到任一节点i的路径代价记为g(i) 。

等代价搜索的算法：1.把起始节点S放到未扩展节点表OPEN中。

如果此起始节点为一目标节点,则求得一个解；否则令g(S)=0;2.如果OPEN是个空表，则没有解而失败退出;3.从OPEN表中选择一个节点i，使其g(i)为最小。

如果有几个节点都合格，那么就要选择一个目标节点作为节点i(要是有目标节点的话)；否则,就从中选一个作为节点i。

把节点i从OPEN 表移至扩展节点表CLOSED中;4.如果节点i为目标节点，则求得一个解;5.扩展节点i。

如果没有后继节点，则转向第(2)步;6.对于节点i的每个后继节点j,计算g(j)=g(i)+c(i,j)，并把所有后继节点j放进OPEN表. 提供回到节点i的指针;7.转向第(2)步。

代价树的广度优先搜索和宽度优先搜索在代价树的宽度优先搜索中，每次都是从OPEN表的全体节点中选择一个代价最小的节点送入CLOSED表进行观察，而代价树的深度优先搜索是从刚扩展出的子节点中选一个代价最小的节点送入CLOSED表进行观察。

代价树的深度优先搜索是不完备的。

在图所示的代价树中，首先对A进行扩展，得到 B1和C1，由于C1的代价小于的B1代价，所以首先把C1送入CLOSED表进行考察。

此时代价树的宽度优先搜索与代价树的深度优先搜索是一致的。

但往下继续进行时，两者就不一样了。

对进行C1 扩展得到D1，D1的代价为5。

此时OPEN表中有D1 和B1，B1的代价为4。

若按代价树的宽度优先搜索方法进行搜索，应选B1送入CLOSED表，但按代价树的深度优先搜索方法，则应选D1送入CLOSED 表。