演示文稿人工智能第三章.pptVIP

归结过程的控制策略 要解决的问题： 归结方法的知识爆炸。 控制策略的目的 归结点尽量少 控制策略的原则 给出控制策略，以使仅对选择合适的子句间方可做归结。避免多余的、不必要的归结式出现。或者说，少做些归结仍能导出空子句。 当前第31页\共有79页\编于星期五\3点 控制策略的方法(1) 删除策略 归类：设有两个子句C和D，若有置换?使得C? ? D成立，则称子句C把子句D归类。 若对S使用归结推理过程中，当归结式Cj是重言式和Cj被S中子句和子句集的归结式Ci(ij)所归类时，便将Cj删除。这样的推理过程便称作使用了删除策略的归结过程。 当前第32页\共有79页\编于星期五\3点 控制策略的方法(1) 删除策略 如P(x)∨～P(x), P(x)∨Q(x)～P(x) P(x)归类P(y)∨Q(z) σ={y/x} 纯文字删除。如果某文字L在子句集中不存在可与之互补的文字～L，则称该文字为纯文字。如S={P∨Q∨R,～Q∨R,Q,～R} 尽管使用删除策略的归结，少做了归结但不影响产生空子句，就是说删除策略的归结推理是完备的。 当前第33页\共有79页\编于星期五\3点 控制策略的方法(2) 支撑集策略 支撑集：设有不可满足子句集S的子集T，如果S-T是可满足的，则T是支撑集。 ? 采用支撑集策略时，从开始到得到空子句的整个归结过程中，只选取不同时属于S-T的子句，在其间进行归结。就是说，至少有一个子句来自于支撑集T或由T导出的归结式。 ? 当前第34页\共有79页\编于星期五\3点 控制策略的方法(2) 支撑集策略 例如：A1ΛA2ΛA3Λ～B中的～B可以作为支撑集使用。要求每一次参加归结的亲本子句中，至少应该有一个是由目标公式的否定（～B）所得到的子句或者它们的后裔。 支撑集策略的归结是完备的。同样，所有可归结的谓词公式都可以用采用支撑集策略达到加快归结速度的目的。问题是如何寻找合适的支撑集。一个最容易找到的支撑集是目标子句的非，即S～B。 当前第35页\共有79页\编于星期五\3点 S T 可满足 支撑集示意图 当前第36页\共有79页\编于星期五\3点 控制策略的方法(2) 支撑集策略 例如：S (1)～I(X)∨R(X) 目标公式的否定得到的子句 (2)I(a) (3)～R(Y)V～L(Y) (4)L(a) S1： (5) R(a) (1)与(2)归结 (6) ～I(x)V～L(x) (1)与(3)归结 (7)～L(a) (2)与(6)归结 (8)NIL (4)与(7)归结 当前第37页\共有79页\编于星期五\3点 控制策略的方法(3) 语义归结策略 语义归结策略是将子句S按照一定的语义分成两部分，约定每部分内的子句间不允许作归结。同时还引入了文字次序，约定归结时其中的一个子句的被归结文字只能是该子句中“最大”的文字。 语义归结策略的归结是完备的。 当前第38页\共有79页\编于星期五\3点 控制策略的方法(4) 线性归结 线性归结策略首先从子句集中选取一个称作顶子句的子句C0开始作归结。归结过程中所得到的归结式Ci立即同另一子句Bi进行归结得归结式Ci+1。而Bi属于S或是已出现的归结式Cj(ji)。即，如下图所示归结得到的新子句立即参加归结。 线性归结是完备的。 当前第39页\共有79页\编于星期五\3点 C0 C1 C2 C3 C4 C5 空 线性归结策略示意图 当前第40页\共有79页\编于星期五\3点 控制策略的方法(5) 单元归结策略 单元归结策略要求在归结过程中，每次归结都有一个子句是单元子句（只含一个文字的子句）或单元因子。显而易见，此种方法可以简单地削去另一个非单子句中的一个因子，使其长度减少，构成简单化，归结效率较高。 初始子句集中没有单元子句时，单元归结策略无效。所以说“反之不成立”，即此问题不能采用单元归结策略。 当前第41页\共有79页\编于星期五\3点 控制策略的方法(6) 输入归结策略 与单元归结策略相似，输入归结策略要求在归结过程中，每一次归结的两个子句中必须有一个是S的原始子句。这样可以避免归结出的不必要的新子句加入归结，造成恶性循环。可以减少不必要的归结次数。 如同单元归结策略，不是所有的可归结谓词公式的最后结论都是可以从原始子句集中的得到的。 当前第42页\共有79页\编于星期五\3点 第三章谓词逻辑与归结原理 概述 命题逻辑 谓词逻辑的归结法 归结过程的控制策略 Herbrand定理 当前第43页\共有79页\编于星期五\3点 第三章谓词逻辑与归结原理 概述 命题逻辑 谓词逻辑的归结法 归结过程的控制策略 Herb