人工智能经典推理课件

3.1 3.1 图搜索策略图搜索策略 图搜索控制策略图搜索控制策略一种在图中寻找路径的方法。图中每个节点对应一个状态，每条连线对应一个操作符。这些节点和连线(即状态与操作符)又分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。一般图搜索过程一般图搜索过程 状态空间搜索的状态空间搜索的基本思想基本思想是：先把问题的初始状态作是：先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后为当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了该问题的解；若没出现，则再按照则搜索成功，找到了该问题的解；若没出现，则再按照某种搜索策略某种搜索策略从已生成的子节点中选择一个节点作为当从已生成的子节点中选择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子节前扩展节点。重复上述过程，直到目标状态出现在子节点中或没有可供扩展的节点为止。点中或没有可供扩展的节点为止。搜索术语（搜索术语（用图来描述状态空间）用图来描述状态空间）节点：对应于状态描述节点：对应于状态描述节点深度：根节点的深度为节点深度：根节点的深度为0,其他节点的深度规定其他节点的深度规定为父节点深度加为父节点深度加1,即即dn+1=dn+1。扩展节点：应用操作符将上一状态（节点扩展节点：应用操作符将上一状态（节点ni）变迁变迁到下一状态（节点到下一状态（节点nj），），ni表表示被扩展节点，示被扩展节点，nj 即是即是由由ni 扩展出的子节点。扩展出的子节点。路径：从节点路径：从节点ni到到nk的路径是由相邻节点间的弧线构的路径是由相邻节点间的弧线构成的折线，通常要求路径是无环的，否则会导致搜索成的折线，通常要求路径是无环的，否则会导致搜索过程进入死循环。过程进入死循环。搜索图：在搜索解答路径的过程中只画出搜索时直搜索图：在搜索解答路径的过程中只画出搜索时直接涉及到的节点和弧线，构成所谓的搜索图。接涉及到的节点和弧线，构成所谓的搜索图。Open表：存放已经生成但未扩展节点表：存放已经生成但未扩展节点Close表：存放已扩展或将要扩展的节点表：存放已扩展或将要扩展的节点S0表示问题的初始状态表示问题的初始状态G表示搜索过程所得到的搜索图表示搜索过程所得到的搜索图M表示当前扩展节点新生成的且不为自己先辈的子表示当前扩展节点新生成的且不为自己先辈的子节点集。节点集。开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表n为目标节点吗？为目标节点吗？把把n的后继节点放入的后继节点放入OPEN表的表的末端，提供返回节点末端，提供返回节点n的指针的指针修改指针方向修改指针方向重排重排OPEN表表失败失败成功成功图图3.1 图搜索过程框图图搜索过程框图是是是是否否否否图搜索过程图图搜索过程图树树/不修改指针不修改指针;图图/修改指针修改指针;修改指针修改指针:找最优解找最优解3.2 盲目搜索 特点：不需重排特点：不需重排OPENOPEN表表种类：宽度优先、深度优先、等代价搜索等。种类：宽度优先、深度优先、等代价搜索等。3.2.1 宽度优先搜索 定义 以接近起始节点的程度逐层扩展节点的搜索方法。特点：一种高代价搜索，但若有解存在，则必能找到它。算法开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表是否有后继节点是否有后继节点为目标节点？为目标节点？扩展扩展n，把，把n的后继节点放入的后继节点放入OPEN表的末端，提供返回节点表的末端，提供返回节点n的指针的指针失败失败成功成功图图3.2 宽度优先算法框图宽度优先算法框图是是否否是是否否3.2 盲目搜索例：例：八数码难题八数码难题 33九九宫宫棋棋盘盘，放放置置数数码码为为1-8的的8个个棋棋牌牌，剩剩下下一一个个空空格，只能通过棋牌向空格的移动来改变棋盘的布局。格，只能通过棋牌向空格的移动来改变棋盘的布局。求解的问题求解的问题给定初始布局（即初始状态）和目标布给定初始布局（即初始状态）和目标布局（即目标状态），如何移动棋牌才能从初始布局到达局（即目标状态），如何移动棋牌才能从初始布局到达目标布局目标布局 解答路径解答路径就是一个合法的走步序列就是一个合法的走步序列 用宽度优先搜索方法解决该问题：用宽度优先搜索方法解决该问题：为问题状态的表示建立数据结构：为问题状态的表示建立数据结构：33的一个矩阵的一个矩阵，*矩阵元素矩阵元素S ij0,1,8；其中其中1i,j3，*数字数字0指示空格，指示空格，*数字数字1-8指示相应棋牌。指示相应棋牌。制定操作算子集：制定操作算子集：*直观方法直观方法为每个棋牌制定一套可能的走步：左、上、为每个棋牌制定一套可能的走步：左、上、右、下四种移动。这样就需右、下四种移动。这样就需32个操作算子。个操作算子。*简易方法简易方法仅为空格制定这仅为空格制定这4种走步种走步，因为只有紧靠，因为只有紧靠空格的棋牌才能移动。空格的棋牌才能移动。*空格移动的唯一空格移动的唯一约束约束是不能移出棋盘。是不能移出棋盘。初始状态初始状态S S0 0：2 3 目标状态目标状态S Sg g：1 2 3 1 8 4 8 0 4 7 6 5 7 6 52 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目标目标82 3 41 8 7 6 54宽度优先搜索宽度优先搜索91011121314151617从图中得，解的路径是：从图中得，解的路径是：S0 38173.2.2 深度优先搜索 定义 首先扩展最新产生的(即最深的)节点。算法 防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度深度界限。与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在OPEN表的前端。（算法框图见教材）3.2 盲目搜索例：例：八数码难题八数码难题 2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 51 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 512341 2 3 8 47 6 5目标目标深度优先搜索深度优先搜索2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 6123456789101112131 2 3 8 47 6 5目标目标设深度界限设深度界限d dm m=4=4例：例：八数码难题八数码难题 3.2.3 等代价搜索 定义 是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。算法 若所有连接弧线具有相等代价，则简化为宽度优先搜索算法。3.2 盲目搜索3.3 启发式搜索特点：重排OPEN表，选择最有希望的节点加以扩展种类：有序搜索(A算法)、A*算法等3.3.1 启发式搜索策略和估价函数盲目搜索可能带来组合爆炸盲目搜索可能带来组合爆炸启发式信息启发式信息 用来加速搜索过程的有关问题领域的用来加速搜索过程的有关问题领域的特征信息特征信息。包括：。包括：用于决定要扩展的下一个节点的信息；用于决定要扩展的下一个节点的信息；在扩展一个节点时，用于决定要生成哪一个或哪几个后继节在扩展一个节点时，用于决定要生成哪一个或哪几个后继节点的信息；点的信息；用于决定某些应该从搜索树中抛弃或修剪的节点的信息；用于决定某些应该从搜索树中抛弃或修剪的节点的信息；启发式搜索启发式搜索使用使用启发式信息指导启发式信息指导的搜索过程称为的搜索过程称为启发式搜索启发式搜索.估价函数估价函数用来估算节点处于最佳求解路径上的希望程度的函数用来估算节点处于最佳求解路径上的希望程度的函数f(n)=g(n)+h(n)n 搜索图中的某个当前被扩展的节点；搜索图中的某个当前被扩展的节点；f(n)从从初初始始状状态态节节点点s,经经由由节节点点n到到达达目目标标节节点点ng，估计的最小路径代价；估计的最小路径代价；g(n)从从s到到n 的实际路径代价；的实际路径代价；h(n)从从n到到ng,估计的最小路径代价。估计的最小路径代价。例例八数码难题八数码难题 估价函数：估价函数：f(n)=d(n)+w(n)其中：其中：d(n)为为n的深度的深度 w(n)为不在位的棋子数为不在位的棋子数如起始节点如起始节点2 8 31 6 47 0 5则起始节点则起始节点S0的估价函数值为的估价函数值为：f(S0)=0+4=43.3.2 有序搜索v实质 选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。3.3 启发式搜索(1)全局择优搜索全局择优搜索：选择选择OPEN表上具有最小表上具有最小f值的节点作为下一个要扩值的节点作为下一个要扩展的节点，即总是选择最有希望的节点作为下一个要展的节点，即总是选择最有希望的节点作为下一个要扩展的节点。扩展的节点。(2)局部择优搜索局部择优搜索：从刚生成的子节点中选择具有最小从刚生成的子节点中选择具有最小f值的节点作值的节点作为下一个要扩展的节点。为下一个要扩展的节点。开始开始把把S放入放入OPEN表，表，计算估价函数计算估价函数 f(s)OPEN表为空表？表为空表？选取选取OPEN表中表中f值最小的节点值最小的节点i放入放入CLOSED表表i为目标节点吗？为目标节点吗？扩展扩展i，得后继节点，得后继节点j，计算，计算f(j)，提供返回，提供返回节点节点i的指针，利用的指针，利用f(j)对对OPEN表重新排表重新排序，调整亲子关系及指针序，调整亲子关系及指针失败失败成功成功图图3.9 有序搜索算法框图有序搜索算法框图是是否否是是否否3.3 启发式搜索算法 例子八数码难题（8-puzzle problem）12384567（目标状态）12384567（初始状态）八数码难题的有序搜索树见下图：3.3 启发式搜索5714563123845671238456712384567（4）（6）（6）2123845671238456712384567（6）（5）（5）1238456712 384567（5）（7）1238456712384567（6）（7）12384567（5）813245671 2384567（5）（7）图3.10 八数码难题的有序搜索树123846（4）73.3 启发式搜索53.3.3 A*算法估价函数的定义：估价函数的定义：对节点对节点n n定义定义f f*(n)=g*(n)=g*(n)+hn)+h*(n),*(n),表示从表示从S S开始约束开始约束通过节点通过节点n n的一条最佳路径的代价。的一条最佳路径的代价。希望估价函数希望估价函数f f 定义为：定义为：f(nf(n)=)=g(n)+h(ng(n)+h(n)g g是是g*g*的估计的估计 ，h h是是h*h*的估计的估计3.3 启发式搜索lg*(n)：从从s到到n的最小路径代价值的最小路径代价值lh*(n)：从从n到到g的最小路径代价值的最小路径代价值lf*(n)=g*(n)+h*(n)：从从s经过经过n到到g的最小路径的最小路径的总代价的总代价值值lg(n)、h(n)、f(n)分别是分别是g*(n)、h*(n)、f*(n)的估计值的估计值lg(ng(n)通常选择为当前所找到的从初始节点通常选择为当前所找到的从初始节点S S到节点到节点n n的的“最佳最佳”路径的代价值，显然有路径的代价值，显然有g(ng(n)g*(n)g*(n)在在A算法中，如果满足条件：算法中，如果满足条件：(1)(1)g(n)是对是对g*(n)的估计，且的估计，且g(n)0；(2)h(n)是是h*(n)的下界，即对任意节点的下界，即对任意节点n均有均有 0h(n)h*(n)则则A算法称为算法称为A*算法算法A*算法的定义：算法的定义：定义定义1 在在GRAPHSEARCH过程中，如果第过程中，如果第8步的重排步的重排OPEN表表是依据是依据f(n)=g(n)+h(n)进行的，则称该过程为进行的，则称该过程为A算法算法。定义定义2 在在A算法中，如果对所有的算法中，如果对所有的n存在存在h(n)h*(n),则称则称h(n)为为h*(n)的下界，它表示某种偏于保守的估计。的下界，它表示某种偏于保守的估计。定义定义3 采用采用h*(n)的下界的下界h(n)为启发函数的为启发函数的A算法，称为算法，称为A*算法算法。当当h=0时，时，A*算法就变为有序搜索算法。算法就变为有序搜索算法。A*算法的可纳性算法的可纳性 对任一个图，存在从对任一个图，存在从S S到目标的路径，如果一个搜索到目标的路径，如果一个搜索算法总是结束在一条从算法总是结束在一条从S S到目标的最佳路径上，则称此算到目标的最佳路径上，则称此算法是可采纳的。法是可采纳的。算法算法A A*保证只要最短路径存在，就一定能找出这条路保证只要最短路径存在，就一定能找出这条路径，所以算法径，所以算法A A*是可纳的。是可纳的。A*算法应用举例算法应用举例 八数码难题八数码难题 估价函数：估价函数：f(nf(n)=)=d(n)+w(nd(n)+w(n)其中：其中：d(nd(n)为为n n的深度的深度 w(nw(n)为为不在位的棋子数不在位的棋子数 取取h(nh(n)=)=w(nw(n),),则有则有w(n)hw(n)h*(n),h(nn),h(n)满足满足A*算法的限制条算法的限制条件。件。1238476528316475初始状态初始状态目标状态目标状态 在八数码难题中在八数码难题中,令估价函数令估价函数 f(nf(n)=)=d(n)+p(nd(n)+p(n)启发函数启发函数h(nh(n)=)=p(n),p(n),p(np(n)为不在位的棋子与其目标为不在位的棋子与其目标位置的位置的距离之和距离之和，则有，则有p(n)p(n)hh*(n),(n),满足满足A*算法的算法的限制条件。限制条件。2 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5目标12345h=5,g=0,f=5h=6,g=1,f=7h=4,g=1,f=5h=6,g=1,f=7h=5,g=2,f=7h=3,g=2,f=5h=5,g=2,f=7h=2,g=3,f=5h=4,g=3,f=7h=1,g=4,f=5h=0,g=5,f=5w(nw(n)不不在在位位的的棋棋子子数数，不不够够贴贴切切，错错误误选选用用节节点点加加以扩展。以扩展。p(np(n)更更接接近近于于h h*(n)(n)的的h(nh(n)，其其值值是是节节点点n n与与目目标标状状态态节节点点相相比比较较，每每个个错错位位棋棋子子在在假假设设不不受受阻阻拦拦的的情情况况下下，移动到目标状态相应位置所需走步的总和。移动到目标状态相应位置所需走步的总和。p(np(n)比比w(nw(n)更更接接近近于于h h*(n)(n)，因因为为p(np(n)不不仅仅考考虑虑了了错错位位因素，还考虑了错位的距离（移动次数）。因素，还考虑了错位的距离（移动次数）。说明说明h h值越大值越大,启发功能越强启发功能越强,搜索效率越高搜索效率越高.特别地特别地(1)(1)h(nh(n)=h*(n)=h*(n)搜索仅沿最佳路径进行搜索仅沿最佳路径进行,效率最高效率最高.(2)(2)h(nh(n)=0)=0 无启发信息无启发信息,盲目搜索盲目搜索,效率低效率低.(3)(3)h(nh(n)h*(n)h*(n)是一般的是一般的A A算法算法,效率高效率高,但不能保证找到最佳路径但不能保证找到最佳路径.有时为求解难题取有时为求解难题取h(nh(n)h*(n),)h*(n),以提高效率以提高效率.3.5 消解原理回顾：回顾：原子公式原子公式（atomic formulasatomic formulas）文字文字一个原子公式及其否定。一个原子公式及其否定。P(x),P(x)子句子句由文字的析取组成的合适公式。由文字的析取组成的合适公式。P(x)Q(x)空子句空子句-不包含任何子句的文字。用不包含任何子句的文字。用NIL表示表示子句集子句集-由子句或空子句所构成的集合由子句或空子句所构成的集合.消解消解对谓词演算公式进行分解和化简，消去一些符号，以求对谓词演算公式进行分解和化简，消去一些符号，以求得导出子句。得导出子句。3.5.1 子句集的求取v 步骤：共9步。v 例子:将下列谓词演算公式化为一个子句集(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)开始：(1)消去蕴涵符号 只应用和符号，以AB替换AB。(1)(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)3.5 消解原理(2)减少否定符号的辖域 每个否定符号最多只用到一个谓词符号上，并反复应用狄摩根定律。(3)对变量标准化 对哑元（虚构变量）改名，以保证每个量词有其自己唯一的哑元。3.5 消解原理(2)(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)(3)(x)P(x)(y)P(y)P(f(x,y)(w)Q(x,w)P(w)(4)消去存在量词 以Skolem函数代替存在量词内的约束变量，然后消去存在量词(5)化为前束形 把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。前束形=前缀 母式 全称量词串 无量词公式(4)(x)P(x)(y)P(y)P(f(x,y)Q(x,g(x)）P(g(x)式中，式中，w=w=g(xg(x)为一为一SkolemSkolem函数。函数。(5)(5)(x)(y)P(x)P(y)P(f(x,y)Q(x,g(x)P(g(x)3.5 消解原理(6)把母式化为合取范式 任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。(7)消去全称量词 所有余下的量词均被全称量词量化了。消去前缀，即消去明显出现的全称量词。3.5 消解原理(6)(6)(x)(y)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)(7)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)(8)消去连词符号 用A,B代替(AB)，消去符号。最后得到一个有限集，其中每个公式是文字的析取。(9)更换变量名称 可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。3.5 消解原理(8)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)(9)P(x1)P(y)Pf(x1,y)P(x2)Qx2,g(x2)P(x3)Pg(x3)3.5.2 消解推理规则消解推理规则消解式的定义消解式的定义令令L L1 1，L L2 2为两任意原子公式；为两任意原子公式；L L1 1和和L L2 2具有相同具有相同的谓词符号，但一般具有不同的变量。已知的谓词符号，但一般具有不同的变量。已知两子句两子句L L1 1和和L L2 2,如果如果L L1 1和和L L2 2具有最具有最一般合一一般合一，那么通过消解可以从这两个父，那么通过消解可以从这两个父辈子句推导出一个新子句辈子句推导出一个新子句()。这个。这个新子句叫做消解式。新子句叫做消解式。v 消解式求法取各子句的析取，然后消去互补对。3.5 消解原理几种从父辈子句求消解式的例子几种从父辈子句求消解式的例子假言推理假言推理 A A B 则 B合并合并 P Q P Q 则 Q重言式重言式 P Q P Q空子句空子句 P P链式链式 P Q Q R 则 P R3.5.3 含有变量的消解式含有变量的消解式 要要把把消消解解推推理理规规则则推推广广到到含含有有变变量量的的子子句句，必必须须找找到到一一个作用于父辈子句的置换，使父辈子句含有互补文字个作用于父辈子句的置换，使父辈子句含有互补文字。v 含有变量的子句之消解式含有变量的子句之消解式v 例子Px,f(y)Q(x)Rf(a),y Pf(f(a),zR(z，w)Q f(f(a)R(f(a)，y)R(f(y)，w)=f(f(a)/x,f(y)/z3.5 消解原理3.5.4 消解反演求解过程消解反演消解反演 给出给出SS，L L否定否定L L，得，得L L；把把L L添加到添加到S S中去；中去；把新产生的集合把新产生的集合L L，S S化成子句集；化成子句集；应用消解原理，力图推导出一个表示矛盾的空子句应用消解原理，力图推导出一个表示矛盾的空子句v 例例1 1储蓄问题储蓄问题 前提：每个储蓄钱的人都获得利息。前提：每个储蓄钱的人都获得利息。结论：如果没有利息，那么就没有人去储蓄钱结论：如果没有利息，那么就没有人去储蓄钱3.5 消解原理(1）规定原子公式：S(x,yS(x,y)表示“x储蓄y”M(xM(x)表示“x是钱”I(xI(x)表示“x是利息”E(xE(x，y)y)表示“x获得y”(2）用谓词公式表示前提和结论：用谓词公式表示前提和结论：前提：前提：(x)(x)(y)(S(x,y)M(y)y)(S(x,y)M(y)(y)(I(y)E(x,yy)(I(y)E(x,y)结论：结论：(x)I(xx)I(x)(x)(x)(y)(M(yy)(M(y)S(x,yS(x,y)(3)化为子句形化为子句形证明证明：3.5 消解原理把前提化为子句形：把前提化为子句形：1)S(x,yS(x,y)M(y)I(f(xM(y)I(f(x)2)S(x,yS(x,y)M(y)E(x,f(xM(y)E(x,f(x)把结论化为子句形：把结论化为子句形：3)I(zI(z)4)S(a,bS(a,b)5)M(bM(b)(4)消解反演求消解反演求NILNIL图图3.12 3.12 储蓄问题反演树储蓄问题反演树子句子句（1）子句子句（3）f(x)/zM(b)NIL子句子句（5）子句子句（7）子句子句（4）a/x,b/yS(x,y)M(y)子句子句（6）3.5 消解原理例例2：“快乐学生快乐学生”问题问题 假设：任何通过计算机考试并获奖的人都是快乐的。任何肯学习假设：任何通过计算机考试并获奖的人都是快乐的。任何肯学习或幸运的人都可以通过所有考试，张不肯学习但他是幸运的，任或幸运的人都可以通过所有考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。何幸运的人都能获奖。求证：张是快乐的。解：将问题用谓词表示如下：解：将问题用谓词表示如下：“任何通过计算机考试并获奖的人都是快乐的任何通过计算机考试并获奖的人都是快乐的”(x)(Pass(x,computer)Win(x,prize)Happy(x)“任何肯学习或幸运的人都可以通过所有考试任何肯学习或幸运的人都可以通过所有考试”(x)(y)(Study(x)Lucky(x)Pass(x,y)“张不肯学习但他是幸运的张不肯学习但他是幸运的”Study(zhang)Lucky(zhang)“任何幸运的人都能获奖任何幸运的人都能获奖”(x)(Lucky(x)Win(x,prize)结论结论“张是快乐的张是快乐的”的否定的否定 Happy(zhang)将谓词转化为子句集：将谓词转化为子句集：P1:Pass(x,computer)Win(x,prize)Happy(x)P2:Study(y)Pass(y,z)P3:Lucky(u)Pass(u,v)P4:Study(zhang)P5:Lucky(zhang)P6:Lucky(w)Win(w,prize)Q:Happy(zhang)所以：所以：S=P1,P2,P3,P4,P5,P6,S=P1,P2,P3,P4,P5,P6,Q对对S进行归结操作，直至推出进行归结操作，直至推出NIL。归结反演过程如归结反演过程如下：下：P6 Pass(x,computer)Win(x,prize)Happy(x)Lucky(w)Win(w,prize)Pass(w,computer)Happy(w)Lucky(w)置换置换w/x P1 Happy(zhang)Q Pass(zhang,computer)Lucky(zhang)置换置换zhang/wLucky(zhang)P5 Pass(zhang,computer)Lucky(u)Pass(u,v)P3 Lucky(zhang)置换置换zhang/u,computer/vLucky(zhang)P5NIL 归结出归结出NIL，证明结论为真。证明结论为真。从反演树求取问题的答案从反演树求取问题的答案步骤步骤1.把问题的已知条件用谓词公式表达出来，并转换成把问题的已知条件用谓词公式表达出来，并转换成子句集子句集S；2.把问题的目标的否定用谓词公式表达出来，并转换把问题的目标的否定用谓词公式表达出来，并转换成子句集成子句集Q；3.对对Q中的每个子句，构造其重言式（包含互补文字中的每个子句，构造其重言式（包含互补文字对的子句），代替相应的目标否定子句，加入到对的子句），代替相应的目标否定子句，加入到S中，中，得到得到S；4.对对S应用消解原理求出消解树，该消解树的根子句应用消解原理求出消解树，该消解树的根子句为所求答案。为所求答案。实质实质把一棵根部有把一棵根部有NIL的反演树变换为根部带有回的反演树变换为根部带有回 答语句的答语句的一棵证明树。一棵证明树。例例3：已知：李和张是同班同学，如果已知：李和张是同班同学，如果x和和y是同班同学，则是同班同学，则x的的教室也是教室也是y的教室，现在张在的教室，现在张在302教室上课，问：李现在在哪里上教室上课，问：李现在在哪里上课？课？解：定义谓词：解：定义谓词：C(x,y)x和和y是同班同学是同班同学 At(x,u)x在在u教室上课教室上课已知前提谓词公式表示如下：已知前提谓词公式表示如下：C(zhang,li)(x)(y)(u)(C(x,y)At(x,u)At(y,u)At(zhang,302)目标的否定用谓词公式表示如下：目标的否定用谓词公式表示如下：(v)At(li,v)将谓词转化为子句集：将谓词转化为子句集：P1:C(zhang,li)P2:C(x,y)At(x,u)At(y,u)P3:At(zhang,302)把目标的否定化为子句，用重言式把目标的否定化为子句，用重言式 Q:At(li,z)At(li,z)代替代替所以：所以：S=P1,P2,P3,S=P1,P2,P3,Q对对S进行归结操作，归结反演过程如下：进行归结操作，归结反演过程如下：P3 C(x,y)At(x,u)At(y,u)At(li,z)At(li,z)QAt(li,z)C(x,li)At(x,z)C(zhang,li)P1At(li,z)At(zhang,z)置换置换li/y,z/uAt(zhang,302)P2At(li,302)置换置换zhang/x置换置换302/z答案：李在答案：李在302教室。教室。正向演绎系统的基本思想正向演绎系统的基本思想逻辑蕴涵式与子句的区别：上面二个表达式在逻辑上是等价的，但所表达的概念有区别：上面二个表达式在逻辑上是等价的，但所表达的概念有区别：强调推理性：强调推理性(即：前件为真时后件为真即：前件为真时后件为真)：只是表示了：只是表示了A、B、C中有一个为真，则中有一个为真，则公式为真公式为真可见：将蕴涵式写成与其等价的子句形式会损失一些逻辑信可见：将蕴涵式写成与其等价的子句形式会损失一些逻辑信息。息。直接利用蕴涵式所做的证明系统就是基于规则的演绎系直接利用蕴涵式所做的证明系统就是基于规则的演绎系统。统。3.6 规则演绎系统 定义定义 基基于于规规则则的的问问题题求求解解系系统统运运用用IfThen规规 则则 来来 建建 立立，每每 个个 ifif可可 能能 与与 某某 断断 言言(assertion)(assertion)集集中中的的一一个个或或多多个个断断言言匹匹配配。有有时时把把该该断断言言集集称称为为工工作作内内存存，thenthen部部分分用用于于规规定定放放入入工工作作内内存存的的新新断断言言。这这种种基基于于规规则则的的系系统统叫叫做做规规则则演演绎绎系系统统。在在这这种种系系统统中中，通通常常称称每个每个ifif部分为前项，称每个部分为前项，称每个thenthen部分为后项。部分为后项。IF A THEN B IF A THEN B IF B THEN C IF B THEN C IF C THEN D IF C THEN D 已知已知 A A 3.6.1 规则正向演绎系统规则正向演绎系统定义定义 正向规则演绎系统是从正向规则演绎系统是从事实到目标进行操作的，即从状事实到目标进行操作的，即从状况条件到动作进行推理的，也就况条件到动作进行推理的，也就是从是从ifif到到thenthen的方向进行推理的。的方向进行推理的。3.6 规则演绎系统正向规则演绎的求解过程正向规则演绎的求解过程1.1.事实表达式的与或形变换事实表达式的与或形变换 在基于规则的正向演绎系统中，我们把事在基于规则的正向演绎系统中，我们把事实表示为实表示为非蕴涵形式的与或形非蕴涵形式的与或形，作为系统的总数据，作为系统的总数据库。库。方法：将规则前件的事实表达式从规则中分离方法：将规则前件的事实表达式从规则中分离出来，单独变换成与或形式的表达式，但是不必化出来，单独变换成与或形式的表达式，但是不必化简成子句。简成子句。例如：一个事实表达式：例如：一个事实表达式：消去存在量词，由常量代替变元消去存在量词，由常量代替变元x，得到一个与或表达式：得到一个与或表达式：利用等价变换，得到：利用等价变换，得到：对第一个合取项进行变量换名对第一个合取项进行变量换名(w/y)，目的是保证每个合取项的变量名都不相同目的是保证每个合取项的变量名都不相同得到公式：上式不是子句，但是一个与或表达式，可以直接用上式不是子句，但是一个与或表达式，可以直接用于正向推理系统。于正向推理系统。2.2.用与或图表示一个与或表达式：用与或图表示一个与或表达式：与或图中的节点代表子表达式与或图中的节点代表子表达式当表达式为析取式当表达式为析取式(E1E2 Ek)时，时，则每个子表达式表示为原表达式的一个后则每个子表达式表示为原表达式的一个后继节点，且用一个继节点，且用一个K连接符连接每个连接符连接每个Ei，表示为与关系。表示为与关系。当表达式为合取式当表达式为合取式(E1E2 Ek)时，时，则每个子表达式单独作为原表达式的一个则每个子表达式单独作为原表达式的一个子节点，用子节点，用1连接符连接，表示为或关系。连接符连接，表示为或关系。上例的事实表达式用与或图表示如下：上例的事实表达式用与或图表示如下：可以看出，每个端节点都是一个文字，所以与或图相当可以看出，每个端节点都是一个文字，所以与或图相当于把一个表达式按照与或关系拆分成文字表示。于把一个表达式按照与或关系拆分成文字表示。讨论：讨论：利用与或图求解图：利用与或图求解图：方法与可分解系统中的解图求法相同。不同的是与或图中方法与可分解系统中的解图求法相同。不同的是与或图中的节点之间的合取、析取关系是相反的。因此，求解图是按的节点之间的合取、析取关系是相反的。因此，求解图是按照照K连接方式求解，而不是按照真值求解。连接方式求解，而不是按照真值求解。上图中的三个解图分别构成三个子句：上图中的三个解图分别构成三个子句：Q(w,A),R(y)S(A,y),P(y)S(A,y)基于规则正向推理系统中的与或图是一种知识表达方式；基于规则正向推理系统中的与或图是一种知识表达方式；可分解系统中的与或图是一种图搜索方式，二者是不同的。可分解系统中的与或图是一种图搜索方式，二者是不同的。3.与或图的与或图的F规则变换规则变换 这些规则是建立在某个问题辖域中普通陈这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。我们把允许用述性知识的蕴涵公式基础上的。我们把允许用作规则的公式类型限制为下列形式：作规则的公式类型限制为下列形式：L W 式中：式中：L是单文字；是单文字；W为与或形的唯一公式。为与或形的唯一公式。3.6 规则演绎系统如果规则为如果规则为(L1L2)W形式，即前提是析取形式，则将形式，即前提是析取形式，则将其分解成二条规则其分解成二条规则 L1 W，L2 W如果规则为如果规则为(L1L2)W形式，即前提是合取形式，形式，即前提是合取形式，不予不予讨论。讨论。例：初始数据库的与或表达式为：例：初始数据库的与或表达式为：(PQ)R S (TU)规则：规则：S(XY)Z推理过程：推理过程：用与或图表示初始条件表达式用与或图表示初始条件表达式 寻找与规则前提匹配的文字寻找与规则前提匹配的文字 用匹配弧连接上述两个文字用匹配弧连接上述两个文字 将规则结论的与或图连接到前提上，扩充与或图将规则结论的与或图连接到前提上，扩充与或图 正向系统的推理树根节点在下部正向系统的推理树根节点在下部上面例题的推理树见下页。上面例题的推理树见下页。从上图的事实表达式部分可以得到四个子句：从上图的事实表达式部分可以得到四个子句：(1)(PQ)S(2)(PQ)(TU)(3)(RS)(4)R(TU)(PQ)R S (TU)XYXYZSSTUTUS(TU)(PQ)RPQRPQ规则：S(XY)Z从上图的规则结论部分可以得到二个子句：从上图的规则结论部分可以得到二个子句：(1)X Z(2)Y Z 用这二个子句代替前提中的用这二个子句代替前提中的S，得到四个新子句，得到四个新子句(1)(PQ)(XZ)(2)(PQ)(YZ)(3)R(XZ)(4)R(YZ)下面说明这四个子句就是用事实表达式和规则构成的子句集进行归结所得到下面说明这四个子句就是用事实表达式和规则构成的子句集进行归结所得到的全部归结式。的全部归结式。XYXYZS首先将事实表达式和规则写成子句形式：首先将事实表达式和规则写成子句形式：事实表达式事实表达式 (PQ)R S (TU)(PQ S)(PQ TU)(R S)(R TU)规则规则 S(XY)Z S(XY)Z (S X Z)(S Y Z)得到子句集：得到子句集：PQS,PQTU,RS,RTU,SXZ,SYZ 由上面的子句集求出归结式：由上面的子句集求出归结式：与与式：式：PQXZ与与式：式：PQYZ 与与式：式：RXZ与与式：式：RYZ由此可见，用归结方法与用与或树方法得到的归结式是相同的。由此可见，用归结方法与用与或树方法得到的归结式是相同的。例：事实表达式例：事实表达式 AB 规则规则 R1：A(CD)R2：B(EG)目标目标 CG推理树：推理树：由此解图得到子句集：由此解图得到子句集：CE,CG,DE,DG其中：其中：CG是目标是目标ABCGCDEGABABR1R23.6.2 规则逆向演绎系统规则逆向演绎系统定义定义 逆向规则演绎系统是从逆向规则演绎系统是从then向向if进行推理进行推理的，即从目标或动作向事实或状况条件进行推的，即从目标或动作向事实或状况条件进行推理的。理的。求解过程求解过程目标表达式的与或形式目标表达式的与或形式与或图的与或图的B规则变换规则变换作为终止条件的事实节点的一致解图作为终止条件的事实节点的一致解图3.6 规则演绎系统1 目标表达式的与或表示目标表达式的与或表示 逆向推理系统从目标开始，与正向系统相反，规则的使用是反向逆向推理系统从目标开始，与正向系统相反，规则的使用是反向的。的。目标表达式的与或形式：目标表达式的与或形式：(1)利用利用skolem函数对目标公式进行标准化（同以前讲的标准化过程函数对目标公式进行标准化（同以前讲的标准化过程相同）相同）(2)各析取项之间变元要各不相同（变量换名）各析取项之间变元要各不相同（变量换名）(3)子表达式之间为析取关系时，使用子表达式之间为析取关系时，使用1连接符连接连接符连接 子表达式之间为合取关系时，使用子表达式之间为合取关系时，使用K连接符连接连接符连接(4)与或图的根节点在上面与或图的根节点在上面例：目标公式：例：目标公式：标准化，得到：变量换名，得到：2 逆向推理系统逆向推理系统关于规则的限制：关于规则的限制：B规则的形式：规则的形式：W L其中：其中：W：任何与或公式：任何与或公式 L：单文字结论：单文字结论 规则中的变元全部是全称量词约束规则中的变元全部是全称量词约束 如果规则为如果规则为W(L1L2)形式，则分解为两条规则：形式，则分解为两条规则：W L1 和和 W L2推理过程：推理过程：(1)用与或图表示目标表达式用与或图表示目标表达式(2)寻找与规则结论匹配的文字寻找与规则结论匹配的文字(3)用匹配弧连接上述的二个匹配文字用匹配弧连接上述的二个匹配文字(4)将规则的结论与前提连接，扩充与或图，直至出现事实表达式的文字将规则的结论与前提连接，扩充与或图，直至出现事实表达式的文字(5)反向推理树的根节点在上面反向推理树的根节点在上面反向推理例题：反向推理例题：P83事实表达式：事实表达式：F1：D(FIDO)F2：B(FIDO)F3：W(FIDO)F4：M(MR)规则：规则：R1：（W(x1)D(x1)F(x1)R2：(F(x2)B(x2)A(y2,x2)R3：M(x3)C(x3)目标公式：目标公式：()()（C(x)D(y)A(x,y)）得到一个解图：得到一个解图：M(MR)D(FIDO)W(FIDO)D(FIDO)B(FIDO)判断是否是一致解图：判断是否是一致解图：C(x)A(x,y)D(y)A(y2,x2)M(x3)F(x2)B(x2)x3/xy2/x,x2/yFIDO/y逆向推理树逆向推理树C(x)D(y)A(x,y)C(x3)D(FIDO)M(MR)MR/x3F(x1)B(FIDO)FIDO/x2x1/x2D(x1)W(x1)W(FIDO)D(FIDO)FIDO/x1FIDO/x1(1)由反向推理树得到所有置换：由反向推理树得到所有置换：x3/x,MR/x3,FIDO/y,y2/x,x2/y,x1/x2,FIDO/x2,FIDO/x1,FIDO/x1(2)求出：求出：U1=(x,x3,y,x,y,x2,x2,x1,x1)U2=(x3,MR,FIDO,y2,x2,x1,FIDO,FIDO,FIDO)(3)求出合一复合：求出合一复合：U=(MR/x,FIDO/y)(4)利用合一复合对目标公式作置换，得到置换例：利用合一复合对目标公式作置换，得到置换例：C(MR)D(FIDO)A(MR,FIDO)该置换例就是推理结果该置换例就是推理结果 正向和逆向组合系统是建立在两个系统相结正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成。这些与或标和表示事实的两个与或图结构组成。这些与或图结构分别用正向系统的图结构分别用正向系统的F F规则和逆向系统的规则和逆向系统的B B规规则来修正。则来修正。3.6.3 规则双向演绎系统规则双向演绎系统3.6 规则演绎系统3.7 产生式系统产生式系统定义定义：用来描述若干个不同的以一个基本用来描述若干个不同的以一个基本概念为基础的系统。这个基本概念就是产概念为基础的系统。这个基本概念就是产生式规则或产生式条件和操作对的概念。生式规则或产生式条件和操作对的概念。实质：在产生式系统中，论域的知识分为实质：在产生式系统中，论域的知识分为两部分：用事实表示静态知识，如事物、两部分：用事实表示静态知识，如事物、事件和它们之间的关系；用产生式规则表事件和它们之间的关系；用产生式规则表示推理过程和行为。由于这类系统的知识示推理过程和行为。由于这类系统的知识库主要用于存储规则，因此又把此类系统库主要用于存储规则，因此又把此类系统称为基于规则的系统。称为基于规则的系统。3.7.1 产生式系统的组成产生式系统的组成图图3.22 产生式系统的主要组成产生式系统的主要组成控制策略总数据库规则库3.7 产生式系统规则库规则库用于存放与求解问题有关的某个领域知识用于存放与求解问题有关的某个领域知识的规则集。的规则集。在建立规则库时，应注意如下问题：在建立规则库时，应注意如下问题：（1）规则库知识的完整性、一致性、准）规则库知识的完整性、一致性、准确性、灵活性。确性、灵活性。（2）对知识进行合理的组织与管理）对知识进行合理的组织与管理：目：目的是使得推理避免访问与所求解的问题无的是使得推理避免访问与所求解的问题无关的知识，以提高问题求解效率。关的知识，以提高问题求解效率。总数据库总数据库总数据库又称为总数据库又称为事实库、上下文、黑板事实库、上下文、黑板等。它是等。它是一个用于存放问题求解过程中各种当前信息的数一个用于存放问题求解过程中各种当前信息的数据结构，例如：问题的初始状态、原始证据、推据结构，例如：问题的初始状态、原始证据、推理中得到的中间结论、最终结论等。理中得到的中间结论、最终结论等。当规则库中某条产生式的前提可与总数据库中当规则库中某条产生式的前提可与总数据库中的某些已知事实匹配时，该产生式就被激活，并的某些已知事实匹配时，该产生式就被激活，并把其结论放入总数据库中，作为后面推理的已知把其结论放入总数据库中，作为后面推理的已知事实。显然，事实。显然，总数据库的内容是在不断变化的，总数据库的内容是在不断变化的，是动态的是动态的。总数据库中的总数据库中的已知事实通常用字符串、向量、集已知事实通常用字符串、向量、集合、矩阵、表等数据结构表示合、矩阵、表等数据结构表示。控制策略控制策略 控制策略又称控制策略又称推理机构推理机构，由一组程序组成，负，由一组程序组成，负责整个产生式系统的运行，实现对问题的求解。责整个产生式系统的运行，实现对问题的求解。主要包括推理策略和搜索策略两部分。主要包括推理策略和搜索策略两部分。推理策略：主要解决推理方向、冲突消解等问题。推理策略：主要解决推理方向、冲突消解等问题。搜索策略：主要解决搜索线路、推理效果、推理效率等搜索策略：主要解决搜索线路、推理效果、推理效率等问题。问题。控制策略的主要工作：控制策略的主要工作：（1）按一定的策略从规则库中）按一定的策略从规则库中选择选择与总数据库中的与总数据库中的已知事实相已知事实相匹配的规则匹配的规则。（2）当发生）当发生冲突冲突（即匹配成功的规则不止一条）时，（即匹配成功的规则不止一条）时，调用相应的冲突解决策略予以消解。调用相应的冲突解决策略予以消解。（3）在执行某条规则时，若该规则的右部是一个或）在执行某条规则时，若该规则的右部是一个或多个结论，则多个结论，则把这些结论加到总数据库中把这些结论加到总数据库中；若规；若规则的右部是一个或多个操作，则则的右部是一个或多个操作，则执行这些操作执行这些操作。（4）对于不确定性知识，在执行每一条规则）对于不确定性知识，在执行每一条规则时，还要按一定的算法计算结论的不确定时，还要按一定的算法计算结论的不确定性。性。（5）对要执行的规则，如果该规则的后件满）对要执行的规则，如果该规则的后件满足问题的结束条件，则足问题的结束条件，则停止推理停止推理。（6）在问题的求解过程中，记住应用过的规）在问题的求解过程中，记住应用过的规则序列，以便最终能够给出问题的则序列，以便最终能够给出问题的解路径解路径。选择规则到选择规则到执行操作的步骤执行操作的步骤 1 匹配匹配 把当前数据库与规则的条件部分相匹把当前数据库与规则的条件部分相匹配。配。2 冲突冲突 当有一条以上规则的条件部分和当前当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪一条规数据库相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决。则，这称为冲突解决。3 操作操作 操作就是执行规则的操作部分。操作就是执行规则的操作部分。3.7 产生式系统选取规则的原则称为选取规则的原则称为控制策略控制策略（冲突消解）（冲突消解）不可撤回方式：不可撤回方式：属盲目性搜索属盲目性搜索,利用问题给利用问题给出的局部知识选一条可应用规则并作用当出的局部知识选一条可应用规则并作用当前总数据库前总数据库,接着再根据新状态继续选取规接着再根据新状态继续选取规则则,搜索过程一直进行下去搜索过程一直进行下去,不必考虑撤回不必考虑撤回用过的规则。用过的规则。回溯方式：回溯方式：在问题求解过程中选择一条规在问题求解过程中选择一条规则执行时，建立其回溯点，保留搜索路径，则执行时，建立其回溯点，保留搜索路径，如以后发现此规则不合适，按原路返回，如以后发现此规则不合适，按原路返回，重新选取另一条规则，继续搜索过程。重新选取另一条规则，继续搜索过程。图搜索方式：图搜索方式：用图表示问题求解过程，图中结点用图表示问题求解过程，图中结点代表问题的状态，结点间的弧代表应用的规则。代表问题的状态，结点间的弧代表应用的规则。用某种方法选择应用规则，并以图结构记录状态用某种方法选择应用规则，并以图结构记录状态变化过程，直到求出问题的解答。变化过程，直到求出问题的解答。小结：小结：不可撤回方式相当于沿着单独的一条路向下延伸不可撤回方式相当于沿着单独的一条路向下延伸搜索下去；搜索下去；回溯方式不保留完整的搜索树结构，只顾当前工回溯方式不保留完整的搜索树结构，只顾当前工作的一条路径，作的一条路径，回溯就是对这条路径进行修正；回溯就是对这条路径进行修正；图搜索方式记下完整的搜索树；图搜索方式记下完整的搜索树；3.7.2 产生式系统的推理产生式系统的推理 产生式系统的问题求解过程产生式系统的问题求解过程即为对解空间的搜索过程，也就是推理即为对解空间的搜索过程，也就是推理过程。按照搜索的方向可把产生式系统过程。按照搜索的方向可把产生式系统分为分为正向推理、逆向推理和双向推理正向推理、逆向推理和双向推理。3.7 产生式系统正向推理正向推理：从一组表示事实的谓词或命题出发，从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题使用一组产生式规则，用以证明该谓词公式或命题是否成立。是否成立。逆向推理逆向推理：从表示目标的谓词或命题出发，使用从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先一组产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后逐一验证这些假设。提出一批假设目标，然后逐一验证这些假设。双向推理双向推理：双向推理的推理策略是同时从目标向双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。某个步骤，实现事实与目标的匹配。3.7 产生式系统（1 1）正向推理）正向推理 从已知事实出发，正向使用推理规则的推理方式，