AI05-5归结策略.ppt

Introduction to Artificial Intelligence 第5章 知识与推理 5.6 归结策略 第5章 知识与推理 5.6.1 归结算法 算法 步1：将子句集S置入CLAUSES表 步2：若空子句NIL在CLAUSES表，则归结成功，退出 步3：若CLAUSES表存在可归结的字句对，归结，并将归结式并入CLAUSES表，转步2 步4：归结失败，退出 第5章 知识与推理 穷举算法 1: S S S1 2: S S1 S2 S1 3: S S2 S3 S1 S2 4: … 第5章 知识与推理 例子 P?Q ?P?Q P??Q ?P??Q Q 1,2 P 1,3 Q??Q 1,4 ?P?P 1,4 Q??Q 2,3 ?P?P 2,3 ?P 2,4 ?Q 3,4 P?Q 1,7 P?Q 1,8 P?Q 1,9 P?Q 1,10 Q 1,11 P 1,12 Q 2,6 ?P?Q 2,7 … S1 S2 第5章 知识与推理 归结法 盲目的全面归结 若从子句集S出发做所有可能的归结，并将归结式加入S中，再做第二层这样的归结，…直到产生空子句 产生组合爆炸 大量的不必要的归结式的产生，又将产生下一层的更大量的不必要的归结式的产生 控制策略 选择合适的子句对其做归结 少做些归结但仍然导出空子句 第5章 知识与推理 归结过程策略控制 要解决的问题：归结方法的知识爆炸 控制策略的目的：归结点尽量少 控制策略的原则：删除不必要的子句，或对参加归结的子句做限制 给出控制策略，以使仅选择合适的子句对其做归结。避免多余的、不必要的归结式出现 第5章 知识与推理 5.6.2 删除策略 在归结过程中可以随时删除以下子句: 含有永真式的子句 被子句集中其它子句归类的子句 思想： 在归结时能把子句集中无用的子句删除掉，就会缩小有哪些信誉好的足球投注网站范围，减少比较次数，从而提高归结效率 归结推理是完备的 少做了归结但不影响产生空子句 第5章 知识与推理 归类 设有两个子句C和D 置换σ使得Cσ?D成立 称子句C把子句D归类 理解：可以理解为，由于小的可以代表大的，所以小的吃掉大的了 第5章 知识与推理 例子1 C=P(x)，D=P(a)∨Q(y)归类 取σ={a/x}，便有Cσ=P(a)?{P(a)，Q(y)} {P(a)，Q(y)}的逻辑表达式是D=P(a) ∨Q(y) C与D是两个子句，它们的关系是“与”的关系，即C，D中有一个为假，整个谓词公式为假 当P(a) 为真时，C与D都为真，C可以代表D 当P(a) 为假时，虽然D的真值由Q(y)决定。但是，由于整个谓词公式的真值已经被确定了（为假），所以讨论Q(y)的真、假已经没有意义了；所以，C还是可以代表D 可以认为：由于C经过置换成为D的一部分，因此可以代表D 第5章 知识与推理 例子2 P(x)，P(a)?Q(y) {a/x} Q(y), P(x)?Q(y) {?} P(a,x)?P(y,b), P(a,b) {a/y,b/x} 第5章 知识与推理 例子3 P?Q ?P?Q P??Q ?P??Q Q 1,2 ?Q 3,4 ? 5,6 S1 S2 第5章 知识与推理 例子4 P(x)?Q(x)??R(x) ?Q(a) ?R(a)?Q(a) P(y) ?P(z)?R(z) ?R(a) 2,3 R(z) 4,5 {z/y} ? 6,7 {a/z} S1 S2 第5章 知识与推理 5.6.3 支撑集策略 设有不可满足子句集S的子集T，如果S-T是可满足的，则T是支撑集 S T 第5章 知识与推理 思想 尽量避免在可满足的子句集中进行归结，因为推倒不出空字句 实现 归结过程，只选取不同时属于S-T的子句，在其间进行归结 至少有一个子句来自于支撑集T或由T导出的归结式|两个亲本字句至少要有一个是目标公式否定的字句或其归结式 一个最容易找到的支撑集T是目标子句的非，即S～B 归结推理是完备的 第5章 知识与推理 例子 S={?I(x)?R(x), I(a), ?R(y)??L(y), L(a)} T=?I(x)?R(x) ?I(x)?R(x) I(a) ?R(y)??L(y) L(a) R(a) 1,2 {a/x} ?I(x)??L(x) 1,3 {x/y} ?L(a) 5,3 {a/y} ?L(a) 6,2 {a/x} ?I(a) 6,4 {a/x} ? 7,4 S1 S2 S3 第5章 知识与推理 例子 S={P∨Q，?P∨R，?Q∨R，?R} T=?R S1 S2 P∨Q ?P∨R ?Q∨R ?R ?P 2,4 ?Q 3,4 Q