《智能控制第三章搜索推理技术幻灯片.ppt》由会员分享，可在线阅读，更多相关《智能控制第三章搜索推理技术幻灯片.ppt（62页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、智能控制第三章搜索推理技术*第1页，共62页，编辑于2022年，星期六3.1 图搜索策略v图搜索控制策略一种在图中寻找路径的方法。图中每个节点对应一个状态，每条连线对应一个操作符。这些节点和连线又分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。v图搜索过程*第2页，共62页，编辑于2022年，星期六图搜索的一般过程如下：1）建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中。2）建立一个叫做CLOSED的已扩展节点表，其初始为空表。3）LOOP：若OPEN表是空表，则失败退出。4）选择OPEN表上的第
2、一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。5）若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。3.1 图搜索策略*第3页，共62页，编辑于2022年，星期六6）扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。7）对那些未曾在G中出现过的M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指
3、针方向。8）按某一任意方式或按某个探试值，重排OPEN表。9）GOLOOP。3.1 图搜索策略*第4页，共62页，编辑于2022年，星期六开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表n为目标节点吗？为目标节点吗？把把n的后继节点放入的后继节点放入OPEN表的表的末端，提供返回节点末端，提供返回节点n的指针的指针修改指针方向修改指针方向重排重排OPEN表表失败失败成功成功图图3.1 图搜索过程框图图搜索过程框图是是是是否否否否3.1 图搜索策略(1)(3)(4)(5)(6)(7)(7)(8)(9)OPENCL
4、OSED(1)(2)*第5页，共62页，编辑于2022年，星期六3.2 盲目搜索 盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。v特点：不需重排OPEN表v种类：宽度优先、深度优先、等代价搜索等。3.2.1 宽度优先搜索v 定义 以接近起始节点的程度逐层扩展节点的搜索方法。v 特点：一种高代价搜索，但若有解存在，则必能找到它。v算法*第6页，共62页，编辑于2022年，星期六1）把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。2）如果OPEN是个空表，则没有解，失败退出；否则继续。3）把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点
5、表中。4）扩展节点n。如果没有后继节点，则转向上述第(2)步。5）把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。6）如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。3.2 盲目搜索*第7页，共62页，编辑于2022年，星期六开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表是否有后继节点是否有后继节点为目标节点？为目标节点？扩展扩展n，把，把n的后继节点放入的后继节点放入OPEN表的末端，表的末端，提供返回节点提供返回节点n的指针的指针失败失败成功成功
6、图图3.2 宽度优先算法框图宽度优先算法框图是是否否是是否否3.2 盲目搜索*第8页，共62页，编辑于2022年，星期六v 例子八数码难题（8-puzzleproblem）1238456712384567（目标状态）（初始状态）规定：将棋子移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展26个节点，共生成46个节点之后才求得解（目标节点）。3.2 盲目搜索*第9页，共62页，编辑于2022年，星期六1238456712384123845674123856712 384123845671238456712384567678910111213123845
7、675675671123845671238456712384567123845672345图3.4 八数码难题的宽度优先搜索树13456123845671238456712384567123845671 238456723242526271236782212384567123845671 238456712 3845671238456712384567123845671415161718192021123845673.2 盲目搜索*第10页，共62页，编辑于2022年，星期六3.2.2 深度优先搜索v 定义 首先扩展最新产生的(即最深的)节点。v算法 防止搜索过程沿着无益的路径扩展下去，往往给
8、出一个节点扩展的最大深度深度界限。与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在OPEN表的前端。3.2 盲目搜索*第11页，共62页，编辑于2022年，星期六深度优先搜索示意图SLOMFPQNFFF*第12页，共62页，编辑于2022年，星期六3.2.3 等代价搜索v 定义 是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。v 算法 在等价搜索算法中，把从节点i到其后续节点j的连接弧线代价记为c(i,j),把从起始节点S到任一节点i的路径代价记为g(i)。在搜索树上，假设g(i)也是从起
9、始节点S到节点i的最少代价路径上的代价。等代价搜索方法以g(i)的递增顺序扩展其节点，其算法如下：3.2 盲目搜索*第13页，共62页，编辑于2022年，星期六开始把把S S放入放入OPENOPEN表表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点为目标节点？失败成功图图3.2 等代价搜索算法框图等代价搜索算法框图是是否否是是否否令令g(s)=0S S是否目标节点是否目标节点？是是成功扩展i，计算其后继节点j的g(j)=g(i)+c(i,j)，并把后继节点j放入OPEN表否否3.2 盲目搜索图图3.2 等代价搜索算法框图等代价搜索算法框图*第14页，
10、共62页，编辑于2022年，星期六3.3 启发式搜索(heuristicallysearch)v特点：重排OPEN表，选择最有希望的节点加以扩展v种类：有序搜索、A*算法等3.3.1 启发式搜索策略和估价函数v盲目搜索可能带来“组合爆炸”v启发式信息 用来加速搜索过程的有关问题领域的特征信息。v启发式搜索:利用启发信息的搜索方法。*第15页，共62页，编辑于2022年，星期六v估价函数估算节点“希望”程度的度量 为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。f(n)表示节点n的估价函数值 v应用节点“希望”程度（估价函数值）重
11、排OPEN表3.3.2 有序搜索v实质 选择OPEN表上具有最小f值的节点（最有希望的节点）作为下一个要扩展的节点。3.3 启发式搜索*第16页，共62页，编辑于2022年，星期六开始开始把把S放入放入OPEN表，计算表，计算估价函数估价函数 f(s)OPEN表为空表？表为空表？选取选取OPEN表中表中f值最小的节点值最小的节点i放入放入CLOSED表表i为目标节点吗？为目标节点吗？扩展扩展i，得后继节点，得后继节点j，计算，计算f(j)，提供返回节点，提供返回节点i的指的指针，利用针，利用f(j)对对OPEN表重新排序，调整亲子关系及表重新排序，调整亲子关系及指针指针失败失败成功成功图图3.
12、9 有序搜索算法框图有序搜索算法框图是是否否是是否否v算法3.3 启发式搜索*第17页，共62页，编辑于2022年，星期六v 例子八数码难题（8-puzzleproblem）12384567（目标状态）12384567（初始状态）八数码难题的有序搜索树见下图：f(n)=d(n)+W(n)d(n):搜索树中节点搜索树中节点n的深度；的深度；W(n):对应于节点对应于节点n的数据库中错放的棋子个数的数据库中错放的棋子个数3.3 启发式搜索*第18页，共62页，编辑于2022年，星期六5643123845671238456712384567（6）（5）（5）（6）1238456712 384567（
13、5）（7）1238456712384567（7）813245671 238456712384567（5）（5）（7）图3.10 八数码难题的有序搜索树123845671238456712384567（4）（6）（6）2571123846（4）7 5 3.3 启发式搜索*第19页，共62页，编辑于2022年，星期六3.3.3 A*算法v估价函数的定义：对节点n定义f f*(n)=g*(n)+h*(n)(n)=g*(n)+h*(n),表示从S开始约束通过节点n的一条最佳路径的代价。希望估价函数f 定义为：f(n)=g(n)+h(n)g是g*的估计，h是h*的估计vA*算法的定义：定义定义1 1 在
14、GRAPHSEARCH过程中，如果第8步的重排OPEN表是依据f(x)=g(x)+h(x)进行的，则称该过程为A算法。定定义义2 2 在A算法中，如果对所有的x存在h(x)h*(x),则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。定定义义3 3 采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。当h=0时，A*算法就变为有序搜索算法。3.3 启发式搜索*第20页，共62页，编辑于2022年，星期六(1)把S放入OPEN表，记f=h，令CLOSED为空表。(2)重复下列过程，直至找到目标节点止。若OPEN为空表，则宣告失败。(3)选取OPEN表中未设置过的具有最小f值的节
15、点为最佳节点BESTNODE，并把它放入CLOSED表。(4)若BESTNODE为一目标节点，则成功求得一解。(5)若BESTNODE不是目标节点，则扩展之，产生后继节点SUCCSSOR。(6)对每个SUCCSSOR进行下列过程：(a)建立从SUCCSSOR返回BESTNODE的指针。(b)计算g(SUC)=g(BES)+k(BES,SUC)。(c)如果SUCCSSOROPEN，则称此节点为OLD，并把它添至BESTNODE的后继节点表中。(d)比较新旧路径代价。如果g(SUC)g(OLD),则重新确定OLD的父辈节点为BESTNODE，记下较小代价g(OLD),并修正f(OLD)值。(e)若
16、至OLD节点的代价较低或一样，则停止扩展节点。(f)若SUCCSSOR不在OPEN表中，则看其是否在CLOSED表中。(g)若SUCCSSOR在CLOSED表中，则转向（c）。(h)若SUCCSSOR既不在OPEN表中，又不在CLOSED表中，则把它放入OPEN表中，并添入BESTNODE后裔表，然后转向(7)(7)计算f值。(8)GOLOOPA*算法步骤：*第21页，共62页，编辑于2022年，星期六A*算法参考框图开始开始把把S放入放入OPEN表，记表，记f=hOPEN=NIL?失败失败选取选取OPEN表上未设置过的具有最小表上未设置过的具有最小f值值的节点的节点BESTNODE,放入放入
17、CLOSED表中表中BESTNODE是目标是目标节点？节点？成功成功扩展扩展BESTNODE，产生，产生后续节点后续节点SUCCESSOR建立从建立从SUCCESSOR返回返回BESTNODE的指针的指针计算计算g(SUC)=g(BES)+k(BES,SUC)SUC属属于于OPEN？SUC属于属于CLOSED？SUC=OLD，把它添加到，把它添加到BESTNODE的后续节点表中的后续节点表中g(SUC)Q)消解式消解式 Q(2)合并父辈子句父辈子句 P QP Q消解式消解式 QQ=Q(3)重言式父辈子句父辈子句 P Q P QP P消解式消解式 Q QP Q P Q(4)空子句(矛盾)P PN
18、IL*第30页，共62页，编辑于2022年，星期六3.4.3 含有变量的消解式 要把消解推理规则推广到含有变量的子句，必须找到一个作用于父辈子句的置换，使父辈子句含有互补文字。v 含有变量的子句之消解式v 例子Px,f(y)Q(x)Rf(a),yPf(f(a),zR(z，w)Qf(f(a)R(f(a)，y)R(f(y)，w)=f(f(a)/x,f(y)/z3.4 消解原理*第31页，共62页，编辑于2022年，星期六父辈子句父辈子句 消解式消解式P和和 PQ(即即PQ)QPQ和和 PQ QPQ 和和 PQQQ 和和PPP PNILPQ 和和 QR(即即PQ 和和 QR)PR(即即PR)B(x)
19、和和 B(x)C(x)C(x)P(x)Q(x)和和 Q(f(y)P(f(y),=f(y)/xP(x,f(y)Q(x)R(f(a),y)和和 Q(f(f(a)R(f(a),y)R(f(y),w)P(f(f(a),z)R(z,w)=f(f(a)/x,f(y)/z表 3.1 子句和消解式*第32页，共62页，编辑于2022年，星期六3.4.4 消解反演求解过程v消解反演 给出公式集：S，目标公式：Lv否定L，得L；v把L添加到S中去；v把新产生的集合L，S化成子句集；v应用消解原理，力图推导出一个表示矛盾的空子句（NIL）v 例子储蓄问题 前提：每个储蓄钱的人都获得利息。结论：如果没有利息，那么就没
20、有人去储蓄钱3.4 消解原理*第33页，共62页，编辑于2022年，星期六(1）规定原子公式：S(x,y)S(x,y)表示“x储蓄y”M(x)M(x)表示“x是钱”I(x)I(x)表示“x是利息”E(xE(x，y)y)表示“x获得y”(2）用谓词公式表示前提和结论：前提：前提：(x)(y)(S(x,y)M(y)(y)(I(y)E(x,y)结论：结论：(x)I(x)(x)(y)(M(y)S(x,y)证明证明：3.4 消解原理*第34页，共62页，编辑于2022年，星期六把前提化为子句形：1)S(x,y)M(y)I(f(x)2)S(x,y)M(y)E(x,f(x)把结论的否定化为子句形：3)I(z
21、)4)S(a,b)5)M(b)(3)化为子句形3.4 消解原理*第35页，共62页，编辑于2022年，星期六(4)消解反演求空子句（NIL）3.4 消解原理图3.12 储蓄问题反演树子句（1）子句（3）f(x)/zM(b)NIL子句（5）子句（7）子句（4）a/x,b/yS(x,y)M(y)子句子句（6）S(x,y)M(y)I(f(x)I(z)S(a,b)M(b)*第36页，共62页，编辑于2022年，星期六v反演求解过程从反演树求取答案步骤：v把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去。v按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。v用根部的子句作为一
22、个回答语句。v实质v把一棵根部有NIL的反演树变换为根部带有回 答语句的一棵证明树。3.4 消解原理*第37页，共62页，编辑于2022年，星期六“如果无论约翰如果无论约翰(John)(John)到哪里去，菲多到哪里去，菲多(Fido)(Fido)也就去那里，也就去那里，那么如果约翰在学校里，菲多在哪里呢那么如果约翰在学校里，菲多在哪里呢?”?”这两个事实可以解释为下列公式集这两个事实可以解释为下列公式集S S：(x)AT(JOHN,X)=AT(FIDO,X)x)AT(JOHN,X)=AT(FIDO,X)AT(JOHN,SCHOOL)AT(JOHN,SCHOOL)如果我们首先证明公式如果我们首
23、先证明公式(x)AT(FIDO,X)x)AT(FIDO,X)在逻辑上遵循在逻辑上遵循S S，然后寻求一个存在然后寻求一个存在x x的例，那么就能解决的例，那么就能解决“菲多在哪里菲多在哪里”的问题的问题消解反演求解方法：首先对被证明的公式加以否定，再把这个消解反演求解方法：首先对被证明的公式加以否定，再把这个否定式附加到集否定式附加到集S S中去，化这个扩充集的所有成员为子句形，然后用中去，化这个扩充集的所有成员为子句形，然后用消解证明这个子句集是不可满足的。消解证明这个子句集是不可满足的。例子：*第38页，共62页，编辑于2022年，星期六这里要注意的是：目标公式这里要注意的是：目标公式 (
24、x)AT(FIDO,x)x)AT(FIDO,x)的否定产生的否定产生 (x)x)AT(FIDO,x)AT(FIDO,x)，其子句形式为其子句形式为:AT(FIDO,x)AT(FIDO,x)(1)(1)目标公式否定的子句形式为目标公式否定的子句形式为 :AT(FIDO,x)AT(FIDO,x)把它添加至目标公式的否定之否定把它添加至目标公式的否定之否定的子句中去，得重言式的子句中去，得重言式 AT(FIDO,x)AT(FIDO,x)AT(FIDO,x)AT(FIDO,x)；(2)用下图所示的反演树进行消解，并在根部得到子句用下图所示的反演树进行消解，并在根部得到子句:AT(FIDO:AT(FID
25、O，SCHOOL)SCHOOL)；(3)(3)从根部求得答案从根部求得答案AT(FIDOAT(FIDO，SCHOOL)SCHOOL)，用此子句作为回答语句。，用此子句作为回答语句。消解反演求解过程：图3.14从消解求取答案例题的反演树*第39页，共62页，编辑于2022年，星期六3.5规则演绎系统v定义基于规则的问题求解系统运用IfThen规则来建立，每个if可能与某断言(assertion)集中的一个或多个断言匹配。有时把该断言集称为工作内存，then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统。在这种系统中，通常称每个if部分为前项，称每个then部分为后项。*第4
26、0页，共62页，编辑于2022年，星期六3.5.1规则正向演绎系统v定义 正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从if到then的方向进行推理的。v求解过程v事实表达式的与或形变换 在基于规则的正向演绎系统中，把事实表示为非蕴涵形式的与或形，作为系统的总数据库。不把这些事实化为子句形，而是把它们表示为谓词演算公式，并把这些公式变换为叫做与或形的非蕴涵形式。3.5 规则演绎系统*第41页，共62页，编辑于2022年，星期六例如，有事实表达式：(u)(v)Q(v，u)(R(v)P(v)S(u，v)把它化为：Q(v,A)R(v)P(v)S(A,v)对变量更名标
27、准化，使得同一变量不出现在事实表达式的不同主要合取式中。更名后得表达式：Q(w,A)R(v)P(v)S(A,v)必须注意到Q(v，A)中的变量v可用新变量w代替，而合取式R(v)P(v)中的变量v却不可更名，因为后者也出现在析取式S(A,v)中。与或形表达式是由符号和连接的一些文字的子表达式组成的。呈与或形的表达式并不是子句形，而是接近于原始表达式形式，特别是它的子表达式不是复合产生的。3.5 规则演绎系统*第42页，共62页，编辑于2022年，星期六v事实表达式的与或图表示Q(w,A)R(v)P(v)S(A,v)Q(w,A)R(v)P(v)S(A,v)R(v)P(v)S(A,v)R(v)P(
28、v)图3.15一个事实表达式的与或树表示 与或形的事实表达式可用与或图来表示。下图的与或树表示出上述例子的与或形事实表达式。图中，每个节点表示该事实表达式的一个子表达式。3.5 规则演绎系统*第43页，共62页，编辑于2022年，星期六表示某个事实表达式的与或图的叶节点均由表达式中的文字来标记。图中标记有整个事实表达式的节点，称为根节点，它在图中没有祖先。公式的与或图表示有个有趣的性质，即由变换该公式得到的子句集可作为此与或图的解图的集合(终止于叶节点)读出；也就是说，所得到的每个子句是作为解图的各个叶节点上文字的析取。这样，由表达式Q(w,A)R(v)P(v)S(A,v)得到的子句为Q(w,
29、A),S(A,v)R(v),S(A,v)P(v)对应动态图示：3.5 规则演绎系统*第44页，共62页，编辑于2022年，星期六v与或图的F规则（前向推理规则）变换 这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。我们把允许用作规则的公式类型限制为下列形式：L W式中：L是单文字；W为与或形的惟一公式。举例说明如下：公式举例说明如下：公式 (x)(x)(y)(y)(z)P(x,y,z)z)P(x,y,z)(u)Q(x,u u)Q(x,u可以通过下列步骤加以变换：可以通过下列步骤加以变换：(1)(1)暂时消去蕴涵符号暂时消去蕴涵符号 (x)x)(y)(y)(z)P(x,y,z)(
30、z)P(x,y,z)(u)Q(x,u)u)Q(x,u)(2)(2)把否定符号移进第一个析取式内，调换变量的量词把否定符号移进第一个析取式内，调换变量的量词(x)(x)(y)(y)(z)z)P(x,y,z)(P(x,y,z)(u)Q(x,u)u)Q(x,u)(3)(3)进行进行SkolemSkolem化化 (x)(x)(y)y)P(x,y,f(x,y)(P(x,y,f(x,y)(u)Q(x,u)u)Q(x,u)(4)(4)把所有全称量词移至前面然后消去把所有全称量词移至前面然后消去 P(x,y,f(x,y)Q(x,u)P(x,y,f(x,y)Q(x,u)(5)(5)恢复蕴涵式恢复蕴涵式 P(x,
31、y,f(x,y)P(x,y,f(x,y)Q(x,u)Q(x,u)3.5 规则演绎系统*第45页，共62页，编辑于2022年，星期六上述变换的动态演示如下：3.5 规则演绎系统*第46页，共62页，编辑于2022年，星期六3.5.2规则逆向演绎系统v定义：逆向规则演绎系统是从then向if进行推理的，即从目标或动作向事实或状况条件进行推理的。v求解过程：v目标表达式的与或形式 逆向演绎系统能够处理任意形式的目标表达式。首先，采用与变换事实表达式同样的过程，把目标公式化成与或形，即消去蕴涵符号，把否定符号移进括号内，对全称量词Skolem化并删去存在量词。留在目标表达式与或形中的变量假定都已存在量
32、词量化。3.5 规则演绎系统*第47页，共62页，编辑于2022年，星期六例如，目标表达式例如，目标表达式(y)(y)(x)x)P(x)P(x)(x,y)(x,y)P(x)S(y)P(x)S(y)被化成与或形：被化成与或形：P(f(y)P(f(y)Q(f(y),y)Q(f(y),y)R(f(y)R(f(y)S(y)S(y)式中，式中，f(y)f(y)为一为一SkolemSkolem函数。函数。对目标的主要析取式中的变量分离标准化可得对目标的主要析取式中的变量分离标准化可得P(f(z)P(f(z)Q(f(y),y)Q(f(y),y)R(f(y)R(f(y)S(y)S(y)应应注注意意不不能能对对
33、析析取取的的子子表表达达式式内内的的变变量量y y改改名名而而使使每每个个析析取取式式具具有有不同的变量。不同的变量。3.5 规则演绎系统*第48页，共62页，编辑于2022年，星期六 与或形的目标公式也可以表示为与或图。不过，与事实表达式的与或图不同的是，对于目标表达式，与或图中的k k线连接符用来分开合取关系的子表达式线连接符用来分开合取关系的子表达式。在目标公式的与或图中，我们把根节点的任一后裔叫做子目标节点，而标在这些后裔节点中的表达式叫做子目标。相应的动态图：3.5 规则演绎系统*第49页，共62页，编辑于2022年，星期六v与或图的B规则（逆向推理规则）变换 现在应用B规则即逆向推
34、理规则来变换逆向演绎系统的与或图结构，这个B规则是建立在确定的蕴涵式基础上的，正如正向系统的F规则一样。不过，现在把这些B规则限制为 W L形式的表达式。其中，W为任一与或形公式，L为文字，而且蕴涵式中任何变量的量词辖域为整个蕴涵式。v作为终止条件的事实节点的一致解图3.5 规则演绎系统*第50页，共62页，编辑于2022年，星期六 正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成。这些与或图结构分别用正向系统的F规则和逆向系统的B规则来修正。3.5.3规则双向演绎系统3.5 规则演绎系统*第51页，共62页，编辑于2022年，星
35、期六3.6产生式系统(productionsystem)v定义定义：用来描述若干个不同的以一个基本概念为基础的系统。这个基本概念就是产生式规则或产生式条件和操作对的概念。v实质：实质：在产生式系统中，论域的知识分为两部分：用事实表示静态知识，如事物、事件和它们之间的关系；用产生式规则表示推理过程和行为。由于这类系统的知识库主要用于存储规则，因此又把此类系统称为基于规则的系统(rule-based system)。*第52页，共62页，编辑于2022年，星期六3.6.1产生式系统的组成控制策略图3.22产生式系统的主要组成总数据库产生式规则3.6 产生式系统 总数据库又叫综合数据库、上下文、黑板
36、等，用于存放求解过程中各种当前信息的数据结构，如问题的初始状态、事实或证据、中间推理结论和最后结果等。产生式规则是一个规则库，用于存放与求解问题有关的某个领域知识的规则之集合及其交换规则。控制策略为一推理机构，由一组程序组成，用来控制产生式系统的运行，决定问题求解过程的推理线路，实现对问题的求解。*第53页，共62页，编辑于2022年，星期六v选择规则到执行操作的步骤 1匹配 把当前数据库与规则的条件部分相匹配。2冲突解决 当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决。3操作 操作就是执行规则的操作部分。经过操作以后，当前数据库将被修改 3.6
37、产生式系统*第54页，共62页，编辑于2022年，星期六3.6.2产生式系统的推理v正向推理：从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立。实现正向推理的一般策略是：先提供一批数据(事实)到总数据库中，系统利用这些事实与规则的前提匹配，触发匹配成功的规则(即启用规则)，把其结论作为新的事实添加到总数据库中。继续上述过程，用更新过的总数据库中的所有事实再与规则库中另一条规则匹配，用其结论再修改总数据库的内容，直到没有可匹配的新规则，不再有新的事实加到总数据库为止。3.6 产生式系统*第55页，共62页，编辑于2022年，星期六例如，有规则集如下:规则1:I
38、FIF P1 THENTHEN P2 规则2:IFIF P2 THENTHEN P3 规则3:IFIF P3 THENTHEN q3 规则中的P1、P2、P3、q3可以是谓词公式或命题。设总数据库（工作存储器）中已有事实P1，则应用这三条规则进行正向推理，即从P1出发推导出q3的过程如下图所示。3.6 产生式系统*第56页，共62页，编辑于2022年，星期六v逆向推理：从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后逐一验证这些假设。举例如下：仍用上述的三条规则为例，应用反向推理方法，从P1出发推导出q3的过程如图所示：*第57页，共62页，编
39、辑于2022年，星期六逆向推理的具体实现策略是：先假定一个可能的目标，系统试图证明它，看此假设目标是否在总数据库中，若在，则假设成立。否则，看这些假设是否证据(叶子)结点，若是，向用户询问，若不是，则再假定另一个目标，即找出结论部分中包含此假设的那些规则，把它们的前提作为新的假设，试图证明它。这样周而复始，直到所有目标被证明，或所有路径被测试。正向推理正向推理逆向推理逆向推理驱动方式驱动方式数据驱动数据驱动目标驱动目标驱动推理方法推理方法从一组数据出发向前推导结论从一组数据出发向前推导结论从可能的解答出发，向后推理验证解答从可能的解答出发，向后推理验证解答启动方法启动方法从一个事件启动从一个事
40、件启动由询问关于目标状态的一个问题而启动由询问关于目标状态的一个问题而启动透明程度透明程度不能解释其推理过程不能解释其推理过程可解释其推理过程可解释其推理过程推理方向推理方向由底向上推理由底向上推理由顶向下推理由顶向下推理典型系统典型系统CLIPSCLIPS，OPSOPSPROLOGPROLOG表表3.2 3.2 正、逆向推理的比较正、逆向推理的比较*第58页，共62页，编辑于2022年，星期六v双向推理：双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。事实事实 P1规则规则1规则规则2P2匹配匹配 规则规则（n-2)规则规则（n-1
41、)Pn-1Pn假设假设 目标目标图图3.25 双向综合推理过程双向综合推理过程*第59页，共62页，编辑于2022年，星期六3.7系统组织技术3.7.1议程表v系统组织技术首先将一个大系统或复杂系统中的知识划分为一组相对独立的模块，然后考虑各子模块间在求解时的合作问题。v议程表(agenda)是一个系统能够执行的任务表列。与每个任务有关的有两件事，即提出该任务的理由和表示对该任务是有用的证据总权的评价。*第60页，共62页，编辑于2022年，星期六3.7.2 黑板法v黑板法由一组称为知识资源(KS)的独立模块和一块黑板组成求解系统。知识资源含有系统中专门领域的知识，而黑板则是一切KS可以访问的公用数据结构。3.7 系统组织技术3.7.3-极小搜索法v提供了一种选择最有希望假设的技术。*第61页，共62页，编辑于2022年，星期六3.8小结v经典搜索推理技术v图搜索技术v消解反演v高级搜索推理技术v规则演绎系统v产生式系统v系统组织技术*第62页，共62页，编辑于2022年，星期六