《人工智能第三章搜索推理技术41287.docx》由会员分享，可在线阅读，更多相关《人工智能第三章搜索推理技术41287.docx（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章 搜索推理技术教学内容：本章在上一章知识表示的基础上研究问题求解的方法，是人工智能研究的又一核心问题。内容包括早期搜索推理技术，如图搜索策略和消解原理；以及高级搜索推理技术，如规则演绎系统、产生式系统、系统组织技术、不确定性推理和非单调推理。教学重点：图搜索策略、消解原理、规则演绎系统、产生式系统。教学难点：启发发式搜索、规规则双向演绎绎系统等。教学方法：课堂堂教学为主，辅辅以恰当的实实验。注意结结合前面所学学知识表示的的基础内容，将将其与问题求求解方法融为为一体。及时时提问、收集集学生学习情情况。尽量使使用实例和网网络课程中的的多媒体素材材进行讲解。教学要求：重点点掌握一般图图搜索策略
2、和和消解原理，掌掌握各种搜索索方法和产生生式系统原理理，了解规则则演绎系统的的基本原理，对对系统组织技技术、不确定定性推理和非非单调推理等等高级推理技技术作一般性性了解。3.1 图搜索索策略教学内容：本节节介绍图搜索索的一般策略略，作为各种种图搜索技术术的基础。教学重点：图搜搜索的一般过过程、OPEEN表和CLLOSE表的的概念。教学难点：OPPEN表和CCLOSE表表的物理意义义。教学方法：课堂堂教学为主，通通过提问彻底底弄清图搜索索的基本概念念。教学要求：重点点掌握图搜索索一般策略，掌掌握OPENN表和CLOOSE表的构构成及作用。1、图搜索策略略的定义图搜索策略略可看作一种种在图中寻找找
3、路径的方法法。初始节点点和目标节点点分别代表初初始数据库和和满足终止条条件的数据库库。求得把一一个数据库变变换为另一数数据库的规则则序列问题就就等价于求得得图中的一条条路径问题。研研究图搜索的的一般策略，能能够给出图搜搜索过程的一一般步骤。2、图搜索算法法中的几个重重要名词术语语（1）OPPEN表与CCLOSE表表（2）搜索索图与搜索树树3、图搜索(GGRAPHSSEARCHH)的一般过过程(1) 建建立一个只含含有起始节点点S的搜索图图G，把S放放到一个叫做做OPEN的的未扩展节点点表中。(2) 建建立一个叫做做CLOSEED的已扩展展节点表，其其初始为空表表。(3) LLOOP：若若OPE
4、N表表是空表，则则失败退出。(4) 选选择OPENN表上的第一一个节点，把把它从OPEEN表移出并并放进CLOOSED表中中。称此节点点为节点n。(5) 若若n为一目标标节点，则有有解并成功退退出，此解是是追踪图G中中沿着指针从从n到S这条条路径而得到到的(指针将将在第7步中中设置)。(6) 扩扩展节点n，同同时生成不是是n的祖先的的那些后继节节点的集合MM。把M的这这些成员作为为n的后继节节点添入图GG中。(7) 对对那些未曾在在G中出现过过的(既未曾曾在OPENN表上或CLLOSED表表上出现过的的)M成员设设置一个通向向n的指针。把把M的这些成成员加进OPPEN表。对对已经在OPPEN或
5、CLLOSED表表上的每一个个M成员，确确定是否需要要更改通到nn的指针方向向。对已在CCLOSEDD表上的每个个M成员，确确定是否需要要更改图G中中通向它的每每个后裔节点点的指针方向向。(8) 按按某一任意方方式或按某个个探试值，重重排OPENN表。(9) GGO LOOOP。提问：图搜索是是针对什么知知识表示方法法的问题求解解方法？4、图搜索方法法分析：图搜索过程程的第8步对对OPEN表表上的节点进进行排序，以以便能够从中中选出一个“最好”的节点作为为第4步扩展展用。这种排排序可以是任任意的即盲目目的(属于盲盲目搜索)，也也可以用以后后要讨论的各各种启发思想想或其它准则则为依据(属属于启发
6、式搜搜索)。每当当被选作扩展展的节点为目目标节点时，这这一过程就宣宣告成功结束束。这时，能能够重现从起起始节点到目目标节点的这这条成功路径径，其办法是是从目标节点点按指针向SS返回追溯。当当搜索树不再再剩有未被扩扩展的端节点点时，过程就就以失败告终终(某些节点点最终可能没没有后继节点点，所以OPPEN表可能能最后变成空空表)。在失失败终止的情情况下，从起起始节点出发发，一定达不不到目标节点点。提问：什么是图图搜索? 其其中，重排OOPEN表意意味着什么，重重排的原则是是什么?3.2盲目搜索索教学内容：介绍绍三种盲目搜搜索方法，即即宽度优先搜搜索、深度优优先搜索和等等代价搜索。教学重点：盲目目搜
7、索的特点点，宽度优先先搜索。教学难点：等代代价搜索中代代价的概念。教学方法：以实实例强化内容容的学习，通通过提问引导导学生对三种种方法的特点点进行比较。教学要求：掌握握盲目搜索的的特点，比较较三种盲目搜搜索方法的优优缺点。3.2.1宽度度优先搜索1、定义如果搜索是是以接近起始始节点的程度度依次扩展节节点的，那么么这种搜索就就叫做宽度优优先搜索(bbreadtth-firrst seearch)。2、特点这种搜索是是逐层进行的的；在对下一一层的任一节节点进行搜索索之前，必须须搜索完本层层的所有节点点。3、宽度优先搜搜索算法(1) 把把起始节点放放到OPENN表中(如果果该起始节点点为一目标节节点
8、，则求得得一个解答)。(2) 如如果OPENN是个空表，则则没有解，失失败退出；否否则继续。(3) 把把第一个节点点(节点n)从OPENN表移出，并并把它放入CCLOSEDD的扩展节点点表中。(4) 扩扩展节点n。如如果没有后继继节点，则转转向上述第(2)步。(5) 把把n的所有后后继节点放到到OPEN表表的末端，并并提供从这些些后继节点回回到n的指针针。(6) 如如果n的任一一个后继节点点是个目标节节点，则找到到一个解答，成成功退出；否否则转向第(2)步。4、宽度优先搜搜索方法分析析：宽度优先搜搜索是图搜索索一般过程的的特殊情况，将将图搜索一般般过程中的第第8步具体化化为本算法中中的第6步，
9、这这实际是将OOPEN表作作为“先进先出”的队列进行行操作。宽度优先搜搜索方法能够够保证在搜索索树中找到一一条通向目标标节点的最短短途径；这棵棵搜索树提供供了所有存在在的路径(如如果没有路径径存在，那么么对有限图来来说，我们就就说该法失败败退出；对于于无限图来说说，则永远不不会终止)。5、例：把宽度度优先搜索应应用于八数码码难题时所生生成的搜索树树，这个问题题就是要把初初始棋局变为为如下目标棋棋局的问题：1 2 38 47 6 5提问：宽度优先先搜索方法中中OPEN表表需要按什么么方式进行操操作？A先进后出 B先进先先出3.2.2深度度优先搜索1、定义在此搜索中中，首先扩展展最新产生的的(即最
10、深的的)节点。深深度相等的节节点可以任意意排列。这种盲目(无信息)搜搜索叫做深度度优先搜索(depthh-firsst seaarch)。2、特点首先，扩展展最深的节点点的结果使得得搜索沿着状状态空间某条条单一的路径径从起始节点点向下进行下下去；只有当当搜索到达一一个没有后裔裔的状态时，它它才考虑另一一条替代的路路径。3、深度界限为了避免考考虑太长的路路径(防止搜搜索过程沿着着无益的路径径扩展下去)，往往给出出一个节点扩扩展的最大深深度棗深度界界限。任何节节点如果达到到了深度界限限，那么都将将把它们作为为没有后继节节点处理。4、含有深度界界限的深度优优先搜索算法法请同学们课课后自学，并并回答课
11、后思思考题。思考题：有界深深度优先搜索索方法能够保保证在搜索树树中找到一条条通向目标节节点的最短途途径吗？3.2.3等代代价搜索1、定义宽度优先搜搜索可被推广广用来解决寻寻找从起始状状态至目标状状态的具有最最小代价的路路径问题，这这种推广了的的宽度优先搜搜索算法叫做做等代价搜索索算法。2、等代价搜索索中的几个记记号起始节点记记为S；从节点i到到它的后继节节点j的连接接弧线代价记记为c(i，jj)；从起始节点点S到任一节节点i的路径径代价记为gg(i)。3、等代价搜索索算法（请同学们们课后认真阅阅读本算法，指指出与宽度优优先、深度优优先算法有何何特别之处。）4、等代价搜索索方法分析如果所有的的连
12、接弧线具具有相等的代代价，那么等等代价算法就就简化为宽度度优先搜索算算法。思考：试比较各各种盲目搜索索搜索方法的的效率，找出出影响算法效效率的原因。3.3 启发式式搜索教学内容：启发发式搜索策略略概述和有序序搜索。启发发式搜索弥补补盲目搜索的的不足，提高高搜索效率。教学重点：启发发式搜索策略略、启发信息息和有序搜索索。教学难点：估价价函数的设计计、A*算法法原理。教学方法：通过过实例加深对对原理的理解解，鼓励同学学扩大阅读范范围。教学要求：掌握握启发式搜索索策略和估价价函数的设计计方法，了解解A*算法原原理。3.3.1启发发式搜索策略略和估价函数数1、为什么需要要启发式搜索索盲目搜索效效率低，
13、耗费费过多的计算算空间与时间间，这是组合合爆炸的一种种表现形式。2、定义进行搜索技技术一般需要要某些有关具具体问题领域域的特性的信信息，把此种种信息叫做启启发信息。利利用启发信息息的搜索方法法叫做启发式式搜索方法。3、启发式搜索索策略有关具体问问题领域的信信息常常可以以用来简化搜搜索。一个比比较灵活(但但代价也较大大)的利用启启发信息的方方法是应用某某些准则来重重新排列每一一步OPENN表中所有节节点的顺序。然然后，搜索就就可能沿着某某个被认为是是最有希望的的边缘区段向向外扩展。应应用这种排序序过程，需要要某些估算节节点“希望”的量度，这这种量度叫做做估价函数(evaluution funct
14、tion)。4、估价函数为获得某些些节点“希望”的启发信息息，提供一个个评定侯选扩扩展节点的方方法，以便确确定哪个节点点最有可能在在通向目标的的最佳路径上上 。ff(n)表示节点nn的估价函数数值建立估价函函数的一般方方法：试图确确定一个处在在最佳路径上上的节点的概概率；提出任任意节点与目目标集之间的的距离量度或或差别量度；或者在棋盘盘式的博弈和和难题中根据据棋局的某些些特点来决定定棋局的得分分数。这些特特点被认为与与向目标节点点前进一步的的希望程度有有关。3.3.2 有有序搜索1、定义用估价函数数f来排列GRAAPHSEAARCH第8步中OPENN表上的节点点。应用某个个算法(例如等代价价算
15、法)选择OPENN表上具有最最小f值的节点作作为下一个要要扩展的节点点。这种搜索索方法叫做有有序搜索(oordereed seaarch)或或最佳优先搜搜索(besst-firrst seearch)，而其算法法就叫做有序序搜索算法或或最佳优先算算法。尼尔逊(NNilssoon)曾提出出一个有序搜搜索的基本算算法。估价函函数f是这样确定定的：一个节节点的希望程程序越大，其其f值就越小。被被选为扩展的的节点，是估估价函数最小小的节点。2、实质选择OPEEN表上具有有最小f值的节点作作为下一个要要扩展的节点点，即总是选选择最有希望望的节点作为为下一个要扩扩展的节点。3、有序状态空空间搜索算法法(1
16、) 把把起始节点SS放到OPENN表中，计算算f(S)并把把其值与节点点S联系起来。(2) 如如果OPENN是个空表，则则失败退出，无无解。(3) 从从OPEN表中中选择一个ff值最小的节节点i。结果有几几个节点合格格，当其中有有一个为目标标节点时，则则选择此目标标节点，否则则就选择其中中任一个节点点作为节点ii。(4) 把把节点i从OPEN表中中移出，并把把它放入CLLOSED的的扩展节点表表中。(5) 如如果i是个目标节节点，则成功功退出，求得得一个解。(6) 扩扩展节点i，生成其全全部后继节点点。对于i的每一个后后继节点j：(a)计算f(j)。(b)如果j既既不在OPEEN表中，又又不在
17、CLOOSED表中，则则用估价函数数f把它添入OPPEN表。从从j加一指向其其父辈节点ii的指针，以以便一旦找到到目标节点时时记住一个解解答路径。(c)如果j已已在OPENN表上或CLOOSED表上上，则比较刚刚刚对j计算过的f值和前面计计算过的该节节点在表中的的f值。如果新新的f值较小，则则(i) 以以此新值取代代旧值。(ii) 从j指向i，而不是指指向它的父辈辈节点。(iii) 如果节点点j在CLOSEED表中，则则把它移回OOPEN表。(7) 转转向(2)，即GO TTO(2)。4、有序搜索方方法分析宽度优先搜搜索、等代价价搜索和深度度优先搜索统统统是有序搜搜索技术的特特例。对于宽宽度优
18、先搜索索，选择f(i)作为节节点i的深度。对对于等代价搜搜索，f(ii)是从起始始节点至节点点i这段路径的的代价。有序搜索的的有效性直接接取决于f的选择，如如果选择的ff不合适，有有序搜索就可可能失去一个个最好的解甚甚至全部的解解。如果没有有适用的准确确的希望量度度，那么f的选择将涉涉及两个方面面的内容：一一方面是一个个时间和空间间之间的折衷衷方案；另一一方面是保证证有一个最优优的解或任意意解。5、例：八数码码难题采用了简单单的估价函数数f(n)=d(n)+W(n)其中：d(n)是搜索索树中节点nn的深度；W(n)用来计计算对应于节节点n的数据库中中错放的棋子子个数。因此此，起始节点点棋局2
19、8 31 47 6 5的f值等于0+4=4。3.3.3 AA*算法A*算法是是一种有序搜搜索算法，其其特点在于对对估价函数的的定义上。1、几个记号令k(nii，nj)表示任意两两个节点ni和nj之间最小代代价路径的实实际代价(对于两节点点间没有通路路的节点，函函数k没有定义)。于是，从从节点n到某个具体体的目标节点点ti，某一条最最小代价路径径的代价可由由k(n,tti)给出。令h*(n)表示示整个目标节节点集合tti上所有k(n,ti)中最小的一一个，因此，h*(n)就是从n到目标节点最小代价路径的代价，而且从n到目标节点能够获得h*(n)的任一路径就是一条从n到某个目标节点的最佳路径(对于
20、任何不能到达目标节点的节点n，函数h*没有定义)。2、估价函数的的定义定义g*为为g*(n)=k(S,n)定义函数ff*，使得在在任一节点nn上其函数值值f*(n)就是从节点点S到节点n的一条最佳佳路径的实际际代价加上从从节点n到某目标节节点的一条最最佳路径的代代价之和，即即f*(n)=gg*(n)+h*(n)希望估价函函数f是f*的一个估估计，此估计计可由下式给给出：f(n)=g(n)+h(n)其中：g是是g*的估计；h是h*的估计。对对于g(n)来说，一个个明显的选择择就是搜索树树中从S到n这段路径的的代价，这一一代价可以由由从n到S寻找指针时时，把所遇到到的各段弧线线的代价加起起来给出(
21、这条路径就就是到目前为为止用搜索算算法找到的从从S到n的最小代价价路径)。这个定义义包含了g(n)g*(n)。h*(n)的估计h(nn)依赖于有有关问题的领领域的启发信信息。这种信信息可能与八八数码难题中中的函数W(n)所用的的那种信息相相似。把h叫做启发函函数。3、A*算法定定义定义1 在在GRAPHHSEARCCH过程中，如如果第8步的重排OPEN表是依依据f(x)=g(x)+h(x)进行的，则则称该过程为为A算法。定义2 在在A算法中，如如果对所有的的x存在h(x)h*(x),则称h(x)为h*(x)的下界，它它表示某种偏偏于保守的估估计。定义3 采采用h*(xx)的下界h(xx)为启发
22、函函数的A算法，称为为A*算法。当当h=0时，A*算法就变变为有序搜索索算法。4、A*算法A*算法描描述参考教材材。提问：由g*(n)和g(n)的定义义知g*(n)g(n)A对 B错错思考：试比较宽宽度优先搜索索、有界深度度优先搜索及及有序搜索的的搜索效率，并并以实例数据据加以说明3.4 消解原原理教学内容：消解解原理是针对对谓词逻辑知知识表示的问问题求解方法法。本节内容容主要包括子子句集的求取取、消解推理理的规则和消消解反演问题题求解方法。教学重点：子句句集的求取、消消解推理的规规则和消解反反演问题求解解方法。教学难点：消解解反演的思想想。教学方法：实例例讲解，注重重课堂练习。教学要求：重点
23、点掌握子句集集的求解步骤骤和消解反演演过程，掌握握消解推理的的规则。消解原理的的基础知识：（1）谓词词公式、某些些推理规则以以及置换合一一等概念。（2）子句句：由文字的的析取组成的的公式(一个原子公公式和原子公公式的否定都都叫做文字)。（3）消解解：当消解可可使用时，消消解过程被应应用于母体子子句对，以便便产生一个导导出子句。例例如，如果存存在某个公理理E1E2和另一公理理E2E3，那么E1E3在逻辑上成成立。这就是是消解，而称称E1E3为E1E2和E2E3的消解式(rresolvvent)。3.4.1子句句集的求取1、步骤(1) 消消去蕴涵符号号只应用和和符号，以以AB替换AB。提问：现有公
24、式式(AB) B C，在消去去蕴涵符号后后得到公式：A(AB) B C B(AB) B CC(AAB) B C D (AB) B C(2) 减减少否定符号号的辖域每个否定符符号最多只只用到一个谓谓词符号上，并反复应用用狄摩根定律。例例如：以AB代代替(AB)以AB代代替(AB)以A代替(A)以(x)AA代替(x)A以(x)AA代替(x)A提问：设有公式式(x)(y)(y)P(x,y)(x)Q(xx,y)，在在经过对变量量标准化后得得到公式为：A(x)(yy)(y)P(x,y)(y)Q(yy,y)B(x)(yy)(x)P(x,x)(x)Q(xx,y)C(x)(yy)(z)P(x,z)(q)Q(q
25、q,y)D(x)(yy)(z)P(x,z)(q)Q(qq,z)E(x)(yy)(z)P(q,z)(q)Q(qq,z)(3) 对对变量标准化化在任一量词词辖域内，受受该量词约束束的变量为一一哑元(虚构变量)，它可以在在该辖域内处处处统一地被被另一个没有有出现过的任任意变量所代代替，而不改改变公式的真真值。合适公公式中变量的的标准化意味味着对哑元改改名以保证每每个量词有其其自己唯一的的哑元。(4) 消消去存在量词词用Skollem函数代代替存在的xx,就可以消消去全部存在在量词，并写写成：(y)Pg(y),y从一个公式式消去一个存存在量词的一一般规则是以以一个Skoolem函数数代替每个出出现的存
26、在量量词的量化变变量，而这个个Skoleem函数的变变量就是由那那些全称量词词所约束的全全称量词量化化变量，这些些全称量词的的辖域包括要要被消去的存存在量词的辖辖域在内。SSkolemm函数所使用用的函数符号号必须是新的的，即不允许许是公式中已已经出现过的的函数符号。例例如：(y)(x)PP(x,y)被(y)P(gg(y),yy)代替，其其中g(y)为一Skollem函数。如果要消去去的存在量词词不在任何一一个全称量词词的辖域内，则则用不含变量量的Skollem函数即即常量。例如如，(x)P(xx)化为P(A)，其中常量量符号A用来表示人人们知道的存存在实体。AA必须是个新新的常量符号号，它未
27、曾在在公式中其它它地方使用过过。(5) 化化为前束形把所有全称称量词移到公公式的左边，并并使每个量词词的辖域包括括这个量词后后面公式的整整个部分。所所得公式称为为前束形。(6) 把把母式化为合合取范式任何母式都都可写成由一一些谓词公式式和(或)谓词公式的的否定的析取取的有限集组组成的合取。这这种母式叫做做合取范式。(7) 消消去全称量词词消去明显出出现的全称量量词。提问：对于公式式(z)(y)(x)P(xx,y,z)(q)(w)(e)Q(qq,w,e,z)，在经经过消去存在在量词后，正正确的公式为为：A(y)PP(B,y,A)(w)Q(CC,w,D,A)B(y)PP(B,y,A)(w)Q(CC
28、,w,g(w),A) , g(w)为一SSkolemm函数C(y)PP(g1(y),yy,A)(w)Q(gg(y),ww,g(w),AA)式中，(g1(y)，g(y)和gg(w)为SSkolemm函数D(y)PP(g1(y),yy,A)(w)Q(gg(y),ww,g(y,w),A)式中，(g1(y)，g(y)和gg(y,w)为Skollem函数(8) 消消去连词符号号用A，BB代替(AB)，以消去去明显的符号号。反复代替替的结果，最最后得到一个个有限集，其其中每个公式式是文字的析析取。任一个个只由文字的的析取构成的的合适公式叫叫做一个子句句。(9) 更更换变量名称称可以更换变变量符号的名名称，
29、使一个个变量符号不不出现在一个个以上的子句句中。2、例将下列谓词词演算公式化化为一个子句句集(x)PP(x)(y)P(y)P(f(xx,y)(y)Q(x,yy)P(yy)3、说明并不是所有有问题的谓词词公式化为子子句集都需要要上述9个步骤。对对于某些问题题，可能不需需要其中的一一些步骤。3.4.2 消消解推理规则则1、消解式令L1为任任一原子公式式，L2为另一原子子公式；L1和L2具有相同的的谓词符号，但但一般具有不不同的变量。已已知两子句LL1和L2,如果L1和L2具有最一般般合一者，那么通过过消解可以从从这两个父辈辈子句推导出出一个新子句句()。这个新子子句叫做消解解式。它是由由取这两个子
30、子句的析取，然然后消去互补补对而得到的的。2、消解式求法法(1) 假假言推理父辈子句 P PQ(即PQ) / /消解式Q(2) 合并 (3) 重重言式(4) 空空子句(矛盾)P P / /NIL(5) 链链式(三段论)即取各子句句的析取，然然后消去互补补对。说明：对合并、重重言式、链式式(三段论)请同学们自自行阅读。3.4.3 含含有变量的消消解式1、消解式求法法为了对含有有变量的子句句使用消解规规则，必须找找到一个置换换，作用于父父辈子句使其其含有互补文文字。2、例子 P(x)Q(x)Qf(y) 置换换=f(y)/xPPf(y)3.4.4 消消解反演求解解过程1、基本思想把要解决的的问题作为
31、一一个要证明的的命题，其目目标公式被否否定并化成子子句形，然后后添加到命题题公式集中去去，把消解反反演系统应用用于联合集，并并推导出一个个空子句(NNIL)，产产生一个矛盾盾，这说明目目标公式的否否定式不成立立，即有目标标公式成立，定定理得证，问问题得到解决决，与数学中中反证法的思思想十分相似似。2、消解反演反演求解的的步骤给出一个公公式集S和目标公式式L，通过反证证或反演来求求证目标公式式L，其证明步步骤如下：(1)否定定L，得L；(2)把L添加到S中去；(3)把新新产生的集合合L，S化成子句句集；(4)应用用消解原理，力力图推导出一一个表示矛盾盾的空子句NNIL。反演求解的的正确性设公式L
32、在在逻辑上遵循循公式集S，那么按照照定义满足SS的每个解释释也满足L。决不会有有满足S的解释能够够满足L的，所以不不存在能够满满足并集SL的解释。如如果一个公式式集不能被任任一解释所满满足，那么这这个公式是不不可满足的。因因此，如果LL在逻辑上遵遵循S，那么SL是不可满满足的。可以以证明，如果果消解反演反反复应用到不不可满足的子子句集，那么么最终将要产产生空子句NNIL。因此此，如果L在逻辑上遵遵循S，那么由并并集SL消解得到到的子句，最最后将产生空空子句；反之之，可以证明明，如果从SSL的子句消消解得到空子子句，那么LL在逻辑上遵遵循S。3、反演求解过过程步骤：(1)把由由目标公式的的否定产
33、生的的每个子句添添加到目标公公式否定之否否定的子句中中去。(2)按照照反演树，执执行和以前相相同的消解，直直至在根部得得到某个子句句止。(3)用根根部的子句作作为一个回答答语句。分析：答案求取涉涉及到把一棵棵根部有NIIL的反演树树变换为在根根部带有可用用作答案的某某个语句的一一颗证明树。由由于变换关系系涉及到把由由目标公式的的否定产生的的每个子句变变换为一个重重言式，所以以被变换的证证明树就是一一棵消解的证证明树，其在在根部的语句句在逻辑上遵遵循公理加上上重言式，因因而也单独地地遵循公理。因因此被变换的的证明树本身身就证明了求求取办法是正正确的。例：储蓄问题前提：每个储蓄蓄钱的人都获获得利息
34、。结论：如果没有有利息，那么么就没有人去去储蓄钱思考：应用消解解反演求解如如下问题：“如果无论约翰翰(Johnn)到哪里去去，菲多(FFido)也也就去那里，那那么如果约翰翰在学校里，菲菲多在哪里呢呢?”3.5 规则演演绎系统教学内容：规则则演绎系统属属于高级搜索索推理技术，用用于解决比较较复杂的系统统和问题。本本节介绍规则则演绎系统的的定义及其三三种推理方法法：规则正向向演绎系统、规规则逆向演绎绎系统和规则则双向演绎系系统。教学重点：规则则演绎系统的的定义、正向向推理和逆向向推理过程。教学难点：双向向演绎的匹配配问题等。教学方法：课堂堂教学为主。通通过比较揭示示正向推理、逆逆向推理和双双向推
35、理的特特点。教学要求：掌握握规则演绎系系统的定义和和正向推理、逆逆向推理的过过程，了解规规则双向演绎绎系统。规则演绎系系统的定义：基于规则的的问题求解系系统运用下述述规则来建立立：IfThhen其中，Iff部分可能由由几个if组成，而而Then部分分可能由一个个或一个以上上的thenn组成。在所有基于于规则系统中中，每个iff可能与某断断言(asssertioon)集中的的一个或多个个断言匹配。有有时把该断言言集称为工作作内存。在许许多基于规则则系统中，tthen部分分用于规定放放入工作内存存的新断言。这这种基于规则则的系统叫做做规则演绎系系统(rulle bassed deeductiion
36、 syystem)。在这种系系统中，通常常称每个iff部分为前项项(anteecedennt)，称每每个thenn部分为后项项(conssequennt)。3.5.1规则则正向演绎系系统1、定义正向规则演演绎系统是从从事实到目标标进行操作的的，即从状况况条件到动作作进行推理的的，也就是从从if到then的方方向进行推理理的。2、正向推理过过程（1）事实实表达式的与与或形变换把事实表示示为非蕴涵形形式的与或形形，作为系统统的总数据库库。具体变换换步骤与前述述化为子句形形类似。注意：我们们不想把这些些事实化为子子句形，而是是把它们表示示为谓词演算算公式，并把把这些公式变变换为叫做与与或形的非蕴蕴涵
37、形式。例：有事实实表达式(u)(v)Q(v，u)(R(vv)P(v)S(u，v)把它它化为Q(vv,A)R(vv)P(v)S(A,vv)对变量更名名标准化，使使得同一变量量不出现在事事实表达式的的不同主要合合取式中，得得：Q(ww,A)R(vv)P(v)S(A,vv)（2）事实实表达式的与与或图表示将上例与或或形的事实表表达式用与或或图来表示，见见图3.1。图 3.1 一一个事实表达达式的与或树树表示一般把事实实表达式的与与或图表示倒倒过来画，即即把根节点画画在最下面，而而把其后继节节点往上画。上上节的与或图图表示，就是是按通常方式式画出的，即即目标在上面面。（3）与或或图的F规则变换这些规则
38、是是建立在某个个问题辖域中中普通陈述性性知识的蕴涵涵公式基础上上的。把允许许用作规则的的公式类型限限制为下列形形式：LW式中：L是是单文字；WW为与或形的的唯一公式。将这类规则则应用于与或或图进行推演演。假设有一一条规则L=W，根据据此规则及事事实表达式FF(L)，可可以推出表达达式F(W)。F(W)是用用W代替F中的所有L而得到的。当当用规则L=W来变换换以上述方式式描述的F(L)的与或或图表示时，就就产生一个含含有F(W)表示的新图图；也就是说说，它的以叶叶节点终止的的解图集以FF(W)子句句形式代表该该子句集。这这个子句集包包括在F(LL)的子句形形和L=WW的子句形间间对L进行所有可可
39、能的消解而而得到的整集集。该过程以以极其有效的的方式达到了了用其它方法法要进行多次次消解才能达达到的目的。（4）作为为终止条件的的目标公式应用F规则则的目的在于于从某个事实实公式和某个个规则集出发发来证明某个个目标公式。在在正向推理系系统中，这种种目标表达式式只限于可证证明的表达式式，尤其是可可证明的文字字析取形的目目标公式表达达式。用文字字集表示此目目标公式，并并设该集各元元都为析取关关系。结论：当正向演绎绎系统产生一一个含有以目目标节点作为为终止的解图图时，此系统统就成功地终终止。3.5.2 规规则逆向演绎绎系统1、定义基于规则的的逆向演绎系系统，其操作作过程与正向向演绎系统相相反，即为从
40、从目标到事实实的操作过程程，从theen到if的推理过过程。2、逆向推理过过程（1）目标标表达式的与与或形式逆向演绎系系统能够处理理任意形式的的目标表达式式。首先，采采用与变换事事实表达式同同样的过程，把把目标公式化化成与或形。（2）与或或图的B规则变换B规则是建建立在确定的的蕴涵式基础础上的，正如如正向系统的的F规则一样。不不过，我们现现在把这些BB规则限制为为WL (3.4)形式的表达式。其其中，W为任一与或或形公式，LL为文字，而而且蕴涵式中中任何变量的的量词辖域为为整个蕴涵式式。（3）作为为终止条件的的事实节点的的一致解图逆向系统成成功的终止条条件是与或图图包含有某个个终止在事实实节点
41、上的一一致解图。提问：逆向推理理与正向推理理的区别有哪哪些？3.5.3 规规则双向演绎绎系统1.基于规则的的正向演绎系系统和逆向演演绎系统的特特点和局限性性 正向演绎系系统能够处理理任意形式的的if表达式，但但被限制在tthen表达达式为由文字字析取组成的的一些表达式式。逆向演绎绎系统能够处处理任意形式式的thenn表达式，但但被限制在iif表达式为为文字合取组组成的一些表表达式。双向向(正向和逆向向)组合演绎系系统具有正向向和逆向两系系统的优点，克克服各自的缺缺点。2.双向(正向向和逆向)组合演绎系系统的构成 正向和逆向向组合系统是是建立在两个个系统相结合合的基础上的的。此组合系系统的总数据
42、据库由表示目目标和表示事事实的两个与与或图结构组组成，并分别别用F规则和B规则来修正正。3.终止条件 组合演绎系系统的主要复复杂之处在于于其终止条件件，终止涉及及两个图结构构之间的适当当交接处。当当用F规则和B规则对图进进行扩展之后后，匹配就可可以出现在任任何文字节点点上。在完成两个个图间的所有有可能匹配之之后，目标图图中根节点上上的表达式是是否已经根据据事实图中根根节点上的表表达式和规则则得到证明的的问题仍然需需要判定。只只有当求得这这样的一个证证明时，证明明过程才算成成功地终止。若若能够断定在在给定方法限限度内找不到到证明时过程程则以失败告告终。3.6 产生式式系统教学内容：本节节介绍产生
43、式式系统的定义义、组成和推推理技术。教学重点：产生生式系统与规规则演绎系统统的差别和产产生式系统的的组成。教学难点：产生生式系统的控控制策略等。教学方法：课堂堂教学和实验验相结合。重重点讲解原理理，通过实验验进一步领会会系统的精髓髓。充分利用用网络课程中中的多媒体素素材来表示抽抽象概念。教学要求：掌握握产生式系统统的组成结构构，通过实践践掌握产生式式系统的设计计和工作过程程。定义：在基于规则则系统中，每每个if可能与某某断言(asssertiion)集中中的一个或多多个断言匹配配，thenn部分用于规规定放入工作作内存的新断断言。当thhen部分用用于规定动作作时，称这种种基于规则的的系统为反
44、应应式系统(rreactiion syystem)或产生式系系统(prooductiion syystem)。提问：产生式系系统与规则演演绎系统有什什么区别？3.6.1 产产生式系统的的组成1.产生式系统统的组成 产生式系统统由3个部分组成成，即总数据据库(或全局数据据库)、产生式规规则和控制策策略，如图33.2所示。 图3.2 产生生式系统的主主要组成总数据库有有时也被称作作上下文，当当前数据库或或暂时存储器器。总数据库库是产生式规规则的注意中中心。产生式式规则的左边边表示在启用用这一规则之之前总数据库库内必须准备备好的条件。例例如在上述例例子中，在得得出该动物是是食肉动物的的结论之前，必必
45、须在总数据据库中存有“该动物是哺哺乳动物”和“该动物吃肉肉”这两个事实实。执行产生生式规则的操操作会引起总总数据库的变变化，这就使使其他产生式式规则的条件件可能被满足足。 产生式规则则是一个规则则库，用于存存放与求解问问题有关的某某个领域知识识的规则之集集合及其交换换规则。规则则库知识的完完整性、一致致性、准确性性、灵活性和和知识组织的的合理性，将将对产生式系系统的运行效效率和工作性性能产生重要要影响。控制策略为为一推理机构构，由一组程程序组成，用用来控制产生生式系统的运运行，决定问问题求解过程程的推理线路路，实现对问问题的求解。产产生式系统的的控制策略随随搜索方式的的不同可分为为可撤回策略略、回溯策略略、图搜索策策略等。2.产生式系统统的控制策略