人工智能原理ch4 and ch5 read

第四章一般搜索原理知识 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示的目的是为了便于计算机求解，是为了解决问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 。从问题的描述（表示）到问题的解决，有个求解的过程，也就是搜索过程。在这一过程中采用适当的搜索技术，包括各种规则、过程和算法等推理技术，力求找到问题的解答。本章讨论一些早期的搜索技术或用于解决比较简单问题的搜索原理（启发式搜索、宽度优先、深度优先、有序搜索）。4.1盲目搜索盲目搜索又叫做无信息搜索。一般只适用于求解比较简单的问题。O规则库搜索树：R1R2A.B.R1:如X/12为整，则X/6为整。R2R3R1R4C.D.E..R2:如X/20为整，则X/10为R3R4R2R3R4SF..G.H.R3:如X/6为整，则X/2为整。R4SR4R4SR4:如X/10为整，则X/5为整。SSS输入数据库：N/12，N/20S=success判断是否N/5这是一个产生式系统的例子。节点用表示。每一个节点对应于一个状态，反映当时数据库的情况。如节点O：N/12，N/20；节点A：N/12，N/20，N/6；节点D：N/12，N/20，N/6，N/2。每条连线对应于一个操作符。棋局对应走步，这里对应于一条产生式规则。该搜索树给出了所有可能的求解证明渠道。抽象地描述：给定初始节点和目标节点，求图中的一条合理路径（所谓合理有的指只要找到就行；有的要求搜索步骤最少或路径最短等等）。就这个例子，我们看一下宽度优先搜索、深度优先搜索是如何进行的。当然，并不是所有问题都可以画出图示的搜索树（深度不深、每条支路都有解且支路不多）。4.1.1宽度优先搜索如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索。也就是说，这种搜索是逐层进行的。在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。宽度优先搜索算法（ 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 框图）如下：（1）把起始节点放到OPEN表中（如果该起始节点为目标节点，则求得一个解答）。OPENCLOSEDO（2）如果OPEN表是个空表，则没有解，失败退出。否则继续。（3）把第一个节点从OPEN表中移出，并把它放入CLOSED的扩展节点表中。（4）扩展该节点。如果没有后继节点，则转向上述第（2）步。（5）把该节点的所有后继节点放到OPEN表的末端，并提供这些后继节点返回该节点的指针。（6）如果该节点的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向（2）。OABOOABCDOABCDESOPEN表CLOSED表OBSR2R4(回溯)宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径。注：1、在OPEN表中已有的节点，新扩展有关节点不放OPEN表中。2、CLOSED表中放数位置前后不重要。4.1.2深度优先搜索另一种盲目（无信息）搜索叫做深度优先搜索。在深度优先搜索中，我们首先扩展最新产生的（即最深的）节点。节点深度定义如下：(1)起始节点（即根节点）的深度为0。(2)任何其它节点的深度等于其父辈节点深度加1。首先、扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接收的解答序列的已知深度上限还要深。为了避免考虑太长的路径（防止搜索过程沿着无益的路径扩展下去），往往给出一个节点扩展的最大深度—深度界限。任何节点如果达到了深度界限，那么都将它们作为没有后继节点处理。和宽度优先法不同之处在于：扩展的节点，其后继节点放入OPEN表的前端OABOOACDBOACFSDBOPEN表CLOSED表OACSR1R2R4(回溯)三步操作，不是最短。如知道最短2步，深度界限定为2，肯定有解且可找到最短路径。但有些情况下（多数），不限定深度不好。4.2启发式搜索盲目搜索的效率低，耗费过多的计算空间与时间。如果能够找到一种用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大大提高。“启发”（heuristic）是关于发现和发明规则及方法的研究。在状态空间搜索中，启发式被定义为一系列规则，它从状态空间中选择最有希望到达问题解的路径。人工智能求解者在两种基本情况下运用启发式策略：(1)一个问题由于问题陈述和数据获取方面固有的模糊性可能使它没有一个确定的解。医疗诊断即是一例：所给出的一系列症状可能有多个原因，医生运用启发式搜索来选择最有可能的论断，并依此产生治疗计划。视觉问题又是一例。看到的景物经常是模糊的。各方面原因造成。河和桥、马路。海面上船、鲸鱼或潜水艇。视觉系统可运用启发式策略选择一给定景像的最有可能的解释。(2)一个问题可能有确定解，但是求解过程中的计算机的代价令人难以接收。在很多问题上（如象棋）中，状态空间的增长特别快，可能的状态数随着搜索的深度呈指数级增长、分解。在这种情况下，用盲目搜索的办法就不行了（不象前面所举的简单例子）。给定棋局，可能的下一状态、对手可能的应对步骤太多。这时需用启发式策略通过指导搜索向最有希望的方向前进，以降低复杂性。通过删除某些状态及其延伸，以消除组合爆炸，并得到令人能接收的解。然而，和发明创造的所有规则一样，启发式策略也是极易出错的。在解决问题的过程中，启发仅仅是下一步将要采取措施的一个猜想。常常根据经验和直觉来判断。由于只利用有限信息，一个启发式搜索可能得到一个次最佳解，也有可能一无所获。上述两种情况第一种多出现在专家系统中，第二种情况多出现在博奕和定理证明中。下面的讨论主要限制在第二种情况。在这种情况下，一般都是：初始状态、算符和目标状态的定义都是完全确定的，然后决定一个搜索空间。进行搜索时，一般需要某些有关具体领域的特性信息。我们把这种信息叫做启发信息，并把利用启发信息的搜索方法叫做启发性搜索方法。在本节中，我们介绍一种有序搜索（也称为最好优先搜索）方法。这种搜索总是选择“最有希望”的节点作为下一个被扩展的节点。何为“最有希望”，取决于你所选的估价函数f(n)（性能指标）。有序搜索算法中，一个节点的希望程度越大，其估价函数值就越小。被选为扩展的节点，是估价函数最小的节点。给定一个问题后，根据问题的特性和解的特性，可以有多种方法定义估价函数，用不同的估价函数指导搜索，其效果可以相差很远。如果选得不好，那么有序搜索就可能失去一个最好的解，甚至全部的解。对于八数码难题，我们采用了简单的估价函数f(n)=d(n)+w(n)其中：d(n)是搜索树中节点n的深度w(n)用来计算对应于节点n的数据库中错放的棋子个数。也就是说，该估价函数考虑了两个因数。第一个因数考虑希望节点距根节点（起始节点）越近越好，第二个因数考虑希望节点距目标节点看上去越近越好。考虑八数码难题，其搜索过程见图。5第五章高级求解技术上一章我们介绍了几个基本的（早期的）搜索技术，如宽度优先、深度优先（盲目搜索）、有序搜索（启发式搜索、最好优先）。对于许多比较复杂的系统和问题，用这些方法就很难甚至无法使问题获得解决。这时，就需要应用一些更先进的推理求解技术。本章讨论规则演绎系统、不确定性推理。5.1规则演绎系统我们通常习惯用ifthen规则形式表示知识求解问题。基于规则的问题求解系统运用下述规则来建立，IF-THEN,即：IFIF1IF2THENTHEN1THEN2其中：IF部分可能由几个IF组成，而THEN部分可能由一个或一个以上的THEN组成。通常称每个IF部分为前项（条件、断言），THEN部分为后项（新断言）。这种基于规则的系统叫做规则演绎系统。有时，THEN部分用于规定动作，这时称这种基于规则的系统为反应式系统或产生式系统。5.1.1规则正向演绎系统(事实、规则、目标)在基于规则的系统中，无论是规则演绎系统或规则产生式系统，均有两种推理方式，即正向推理和逆向推理。从IF部分向THEN部分推理的过程，叫做正向推理。也就是说，正向推理是从事实或状况向目标或动作进行操作的。反之，对于从THEN部分向IF部分推理的过程，叫做逆向推理。逆向推理是从目标或动作向事实或状况进行操作的。1.事实表达式的与或形变换通常用谓词演算公式来表示事实（用作事实表达式）。如事实表达式：(U)(V){Q(V,U)∧[(R(V)∨P(V))∧S(U,V)]}通常还存在蕴含关系。在基于规则的正向演绎系统中，所要做的第一步是将其变换（或叫化成）非蕴含形式的与或形。要把一个公式化成与或形，可利用以下恒等式或方法：(1)W1=>W2=W1∨W2（利用恒等式，去蕴含符号），在事实表达式中，很少有=>符号出现(2)用德.摩根公式（定律）把否定符号移进括号内，直到每个否定符号都只含一个谓词为止。(3)对所得表达式进行skelem化，消除存在性量词。XYmother(Y,X)Xmother(f(X),X)(4)删去全称量词，而余下的变量都被认为具有全称量化作用。Q(V,f(V))∧{[(R(V)∧P(V))]∨S(f(V),V)}2.事实表达式的与或图表示根节点Q(V,f(V))∧{[(R(V)∧P(V))]∨S(f(V),V)}与、合取Q(V,f(V))[(R(V)∧P(V))]∨S(f(V),V)或、析取R(V)∧P(V)S(f(V),V)叶节点文字R(V)P(V)通常，把事实表达式的与或图表示倒过来画，即把根节点画在最下面，而把其后继节点往上画。3.与或图的F规则变换我们把允许用作规则的公式类型限制为下列形式：L=>W式中，L是单文字；W是与或形表达式例如：事实表达式：P∨[S∧(T∨U)]规则：S=>(X∧Y)∨ZP∨[S∧(T∨U)]P析取S∧(T∨U)S合取T∨USTUZX∧Y应用一条F规则L=>WXY得到的与或图4.作为终止条件的目标公式应用F规则的目的在于从某个事实公式和某个规则集出发来证明某个目标公式。在正向推理系统中，这种目标表达式只限于可证明的表达式，尤其是可证明的文字析取形的目标公式表达式。结论是：当正向演绎系统产生一个含有目标节点作为终止的解图时，此系统就成功地终止。(目标可由叶节点析取得到)对上图，若目标为：P∨Z∨X或P∨Z∨Y时，就算证出。例：事实A∨B规则A=>C∧D，B=>E∧G目标C∨G（C∨E，D∨G，D∨E）A∨B消解否证法ABA∨CCGB∨GABA∨BABCDEGBCG空把规则化为子句形式：A∨C，A∨D，B∨E，B∨G目标否定：C∨G，其子句形式为C，G5.1.2规则逆向演绎系统基于规则的逆向演绎系统，其操作过程与正向演绎系统相反，即为从目标到事实的操作过程，从then到if的推理过程。1.目标表达式的与或形式逆向演绎系统能够处理任意形式的目标表达式。首先，采用与变换事实表达式同样的过程，把目标表达式化成与或形、即消去蕴含符号，把否定符号移进括号内，消去存在性量词（skelem化）等。例：目标表达式YX{P(X)=>[Q(X,Y)∧[R(X)∧S(Y)]]}化成与或形P(f(Y))∨{Q(f(Y),Y)∧[R(f(Y))∨S(Y)]}与事实表达式的与或图不同的是，对于目标表达式，与或图中的连接符用来区分合取关系的子表达式。P(f(Y))∨{Q(f(Y),Y)∧[R(f(Y))∨S(Y)]}或、析取P(f(Y))Q(f(Y),Y)∧[R(f(Y))∨S(Y)]与、合取Q(f(Y),Y)R(f(Y))∨S(Y)R(f(Y))S(Y)该目标公式的子句集为：P(f(Y))，Q(f(Y),Y)∧R(f(Y))，Q(f(Y),Y)∧S(Y)可从终止在叶节点上的解图集读出。目标子句是文字的合取，目标表达式就是这些子句的析取。2.与或图的B规则变换现在把这些B规则限制为：W=>LW为任一与或形表达式，L为文字。W=>(L1∧L2)可以化为两个规则：W=>L1和(∧)W=>L23.作为终止条件的事实节点的一致解图逆向系统中的事实表达式均限制为文字合取形。逆向系统成功的终止条件是与或图包含有某个终止在事实节点上的一致解图。下面讨论一个简单的例子，看看基于规则的逆向演绎系统是怎样工作的。例：事实F1：狗（FD）；F2：叫（FD）；F3：摇尾（FD）；F4：猫（MT）规则：R1：摇尾（X）∧狗（X）=>温顺（X）R2:温顺（X）∧叫（X）=>可怕（X）问题：是否存在这样的一只猫和一只狗，使得这只猫不怕这条狗。用目标表达式表示为：XY[猫（Y）∧狗（X）∧可怕(Y，X)]猫（Y）∧狗（X）∧害怕(Y，X)猫（Y）狗（X）可怕(Y，X){MT/Y}{FD/X}猫（MT）狗（FD）可怕(Y，X)R2叫（X）温顺(X){FD/X}叫（FD）温顺(X)逆向系统的一致解图R1红色节点为事实节点摇尾(X)狗（X）{FD/X}{FD/X}摇尾(FD)狗（FD）终止在事实节点前的置换为{MT/Y}，{FD/X}。把它应用到目标表达式，就得到了该问题的解答。5.1.3规则双向演绎系统在上两节中，我们所讨论的基于规则的正向演绎系统和逆向演绎系统都具有局限性（正向L=>W，逆向W=>L）。我们希望能够构成一个组合的系统，使它具有正向和逆向两系统的优点，以克服各自的缺点（局限性）。这个系统就是本节所要研究的规则双向演绎系统。不断用F规则和B规则对与或图进行扩展，进行适当的置换与合一。一个简单的终止条件是某个判定与或图根节点是否为可解过程的直接归纳。这个终止条件是建立在事实节点和目标节点的一种叫做CANCEL的对称关系的基础上的。5.1.3规则双向演绎系统在上两节中，我们所讨论的基于规则的正向演绎系统和逆向演绎系统都具有局限性（正向L=>W，逆向W=>L）。我们希望能够构成一个组合的系统，使它具有正向和逆向两系统的优点，以克服各自的缺点（局限性）。这个系统就是本节所要研究的规则双向演绎系统。不断用F规则和B规则对与或图进行扩展，进行适当的置换与合一。一个简单的终止条件是某个判定与或图根节点是否为可解过程的直接归纳。这个终止条件是建立在事实节点和目标节点的一种叫做CANCEL的对称关系的基础上的。5.2不确定性推理对于许多比较复杂的人工智能系统，往往含有复杂性、不完全性、模糊性和不确定性。当采用产生式系统或专家系统的结构时，要求设计者建立某种不确定性的计算和推理过程。有两种不确定性，即关于证据的不确定性和关于规则的不确定性。5.2.1关于证据的不确定性观察事物时，所看到的事实经常具有某种不确定性。例如，当你观察某种动物的颜色时，你可能说这种动物的颜色看起来是白色的，但也可能是灰色的。这就是说，你的观察带有某种程度的不确定性，导致证据的不确定性。一般，通过对事实赋于一个介于0和1之间的系数来表示事实的不确定性。1代表完全确定，0代表完全不确定。这个系数被称为可信度。当规则具有一个以上的条件时，就需要根据各条件的可信度求得总条件部分的可信度。已有的方法有两类：1.以模糊集理论为基础的方法按这种方法，把所有条件中最小的可信度作为总条件的可信度，看起来好像是符合模糊集理论的。CT=minCTi0.90.70.71.0有时把这种处理可信度的方法，称之为以模糊集理论为基础的方法。在MYCIN系统中主要采用这种方法。这种方法类似于当把几根绳子连接起来使用时，总的绳子强度与强度最差的绳子的强度相同。2.以概率为基础的方法总的证据可信度为各证据可信度的乘积。CT=CT1*…*CTn0.90.70.631.0探矿专家系统PROSPECTOR就采用这种方法。5.2.2关于规则和结论的不确定性规则的不确定性，它表示当规则的条件被完全满足时，产生某种结论的不确定程度。它也是以赋予规则在0和1之间的系数的方法来表示的。例如：规则：如果启动器发出刺耳的噪声那么这个启动器坏的可能性是0.8该规则表示，如果事实完全肯定（1.0），那么结论的可信度为0.8。如果规则的条件部分不完全确定，即条件可信度不为1，此时求结论的可信度简单方法：结论的可信度为条件可信度与规则可信度的乘积CJ=CG*CTCin0.50.80.4Cout规则不确定性5.2.3多个规则支持同一结论的不确定性当多个规则支持同一结论时，如何根据这些规则结论的可信度求得该结论的可信度呢，同样有两种方法。规则：如果该动物有毛发那么它是哺乳动物规则：如果该动物能产乳那么它是哺乳动物1.基于模糊集理论的方法取支持该结论的各规则的结论可信度的最大值作为结论的可信度。（规则1的结论可信度CJ1为0.25，规则2的结论可信度CJ2为0.9，则总的结论可信度CJ为0.9）CJ=maxCJii2.基于概率论的方法定义：规则i的结论可信度为CJi，可信性比例为RJi。一组规则支持结论的可信度，可用以下方法求得：（1）首先把各规则结论的可信度CJi转换成可信性比例RJi。可信性比例RJi和可信度CJi之间的关系为：RJi=CJi/(1-CJi)，CJi=RJi/(1+RJi)（2）把各规则结论的可信性比例RJi相乘以求得这些规则所支持结论的可信性比例。RJ=RJ1*RJ2*…*RJn（3）按公式求结论的可信度CJ:CJ=RJ/(1+RJ)当条件不确定性、规则不确定性、多个规则支持同一结论时，可按顺序依次解决。MYCIN医疗专家系统采用反向推理和深度优先搜索的方法，用到不确定性推理方法，它用于诊断和治疗感染性疾病。步骤4个：1.确定患者有无需要治疗的细菌性感染。2.确定可能引起感染的有机体。3.确定对引起感染的有机体有抑制作用的药物。4.选择一种或几种对治疗患者的感染是最合适的药物。前两步诊断，后两步治疗。有咨询模块、动态数据库（推理记录）、解释模块、知识库等。演讲完毕，谢谢观看！