第三章-智能科学网站.ppt

* * 与节点：一个归约算子能够把单个问题变为几个子问题组成的集合，这时只有当所有子问题都有解，该父辈节点才有解。这种关系称为“与”关系，对应的节点称为与节点。 或节点：几个算子适用于同一个问题，从而产生不同的后继问题集合。这时只要有一个后继集合有解，则意味该父辈问题有解，此时关系是“或”关系，对应节点称为或节点。 * 问题归约描述对应的结构就是一个与或图，原始问题描述对应于起始节点（或根节点），本原问题所对应的节点叫做叶节点。在某些特殊情况下，不出现任何与节点（所有超弧的度都为1），此时的图成了普通图，问题归约描述也就成为状态空间描述。 * G为一与或图；G?为其侯选局部解图； 开始时图G只包括s，耗散值估计为h(s)， 6。 把G中原未出现的n的子节点添加到G中, 并计算其耗散值，若n的子节点为终节点则加能解标记。 * * * * * * * * * * 小结 重要的推理技术 归结演绎系统 产生式系统 自然演绎推理 非单调推理 * 史忠植 人工智能：自动推理 * 史忠植 人工智能：自动推理 * Thank You 人工智能 / * * * * * * 合一算法 求W={P(f(y), y), P(x, a)}的mgu. D0={f(y),x}. ? 1= ? ?{f(y)/x}= {f(y)/x}. W1= W0 ? ? 1 ={P(f(y), y), P(f(y), a)} D1={y, a}. ? 2= ? 1?{a/y}= {f(y)/x} ?{a/y} = {f(a)/x, a/y}. W2= W1 ? ? 2 ={P(f(a),a)} ? 2是mgu. * 史忠植 人工智能：自动推理 * 合一算法 性质： 若W是关于表达式的有限非空可合一集合，则合一算法将在第（2）步结束，并且最后的? k是W的mgu。 若一组表达式E1, …, En 是可合一的，则它们的mgu除了相差一个改名外，是唯一确定。 * 史忠植 人工智能：自动推理 * 归结式 定义:设C1和C2是两个无公共变量的子句,L1和L2 分别是C1 和C2 的文字,如果L1和~L2 有mgu: ?,则: (C1?-{L1?})?(C2?-{L2?}) 称为C1和 C2 的一个二元归结式,而L1 L2称为被归结的文字 若R(C1, C2)是C1, C2的二元归结式,则: C1? C2 = R(C1, C2) * 史忠植 人工智能：自动推理 * 归结式--例子 C1: P(x) ? Q(x) C2: ~P(a) ? R(x) 重命名C2: ~P(a) ? R(y) L1=P(x), L2=~P(a) L1与~L2有mgu ?={a/x} (C1? – L1?) ? (C2? – L2?) =({P(a),Q(a)} – {P(a)}) ? ({~P(a), R(y)} – {~P(a)}) ={Q(a)} ? {R(y)} ={Q(a), R(y)} Q(a) ? R(y) 是C1与C2的二元归结式. * 史忠植 人工智能：自动推理 * 归结式--例子 C1=P(x) ? Q(x) C2= ~P(g(y)) ? ~Q(b) ? R(x) ?1 ={g(y)/x}: R(C1, C2)=Q(g(y)) ? ~Q(b) ?R (x) ?2 ={b/x}: R(C1, C2)= ~ P(g(y)) ? P(b) ? R(x) * 史忠植 人工智能：自动推理 * 归结式因子 定义 如果一个子句C的几个文字有mgu ?, 则C ?称为子句C的因子 例子 设C=P(x) ?P(f(y) ?~Q(x) 假设? ={f(y)/x},则: C ?=P(f(y)) ?~Q(f(y)) * 史忠植 人工智能：自动推理 * 归结式 定义:设C1和C2是无公共变量的子句,其归结式是下列二元归结式之一: (1) C1和C2的二元归结式 (2) C1的因子和C2的二元归结式 (3) C1和C2的因子的二元归结式 (4) C1的因子和C2的因子的二元归结式 该归结式仍记为R(C1,C2) * 史忠植 人工智能：自动推理 * 归结式 例: C1= P(x) ?P(f(y) ?Q(g(y)) C2= ~P(f(g(x))) ?Q(b) C1的因子为: ?={f(y)/x}, C1 ?=P(f(y)) ?Q(g(y)) 则: R(C1,C2)=Q(g(g(x))) ?Q(b) * 史忠植 人工智能：自动推理 * 归结反演 谓词逻辑的归结反演是仅有一条推理规则的问题求解方法，为证明|-A?B，其中A、B是谓词公式。使用反演过程