搜索
第四章一般搜索原理知识表示的目的是为了便于计算机求解，是为了解决问题。从问题的描述（表示）到问题的解决，有个求解的过程，也就是搜索过程。在这一过程中采用适当的搜索技术，包括各种规则、过程和算法等推理技术，力求找到问题的解答。本章讨论一些早期的搜索技术或用于解决比较简单问题的搜索原理（启发式搜索、宽度优先、深度优先、有序搜索）。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）；F