AI第3章-确定性推理

ArtificialIntelligence(AI)

人工智能第3章确定性推理1、推理的基本概念2、搜索策略3、自然演绎推理4、归结演绎推理5、基于规则的演绎推理内容提要表示问题是为了进一步解决问题。有了知识的表示方法之后,就需要有解决问题的方法。从问题表示到问题解决，有个求解过程---搜索过程。这一过程中，需要采用适当的搜索技术，包括各种规则、过程和算法等推理技术，力求找到问题的解答。

搜索---寻找一条从初始问题到问题解的路径。

关键是如何利用知识，尽可能有效地找到问题的解(最佳解)。即，通过推理方法进行“解”的搜索。一、推理的基本概念

什么是推理

推理方法及其分类

推理的控制策略及其分类1、什么是推理所谓推理，就是按照某种策略，由已知判断，推出另一个判断的思维过程。人工智能中，推理是由程序实现的，称之为推理机。智能系统的推理过程实际上就是一种思维过程。按照推理过程所用知识的确定与否，推理可分为：

确定性推理（第3章）

不确定性推理（第4章）⑴、推理的方法演绎、归纳、类比、确定、不确定、单调、非单调、启发式、非启发式。⑵、推理的控制策略如何使用领域知识，使推理过程尽快达到目标的策略。推理的控制策略又可分为：搜索策略、推理策略。2、推理的两个基本问题⑴、按推理的逻辑基础分类

演绎推理从已知的一般性知识出发，推出蕴含在已知知识中，适合于某种个别情况的结论。是一种由一般到个别的推理方法,其核心是三段论。

归纳推理一种由个别到一般的推理方法。

类比归纳推理在两个或两类事物有许多属性都相同或相似的基础上，推出它们在其他属性上也相同或相似的一种归纳推理。3、推理方法的分类假言三段论：A→B，B→C⇒A→C三段论通常由一个大前提、一个小前提和一个结论三部分组成。

大前提是已知的一般性知识，或推理过程得到的判断。

小前提是关于某种具体情况，或某个具体实例的判断。

结论是由大前提推出的，并且适合于小前提的判断。①演绎推理例，有如下三个判断：

a、计算机系的学生都会编程序；（一般性知识）

b、程强是计算机系的一位学生；（具体情况）

c、程强会编程序。（结论）三段论推理：其中，a是大前提；b是小前提；c是经演绎推出的结论。可见：结论是蕴含在大前提中的。---按照所选事例的广泛性：（完全、不完全）

完全归纳推理在进行归纳时，考察相应事物的全部对象，根据这些对象是否都具有某种属性，推出该类事物是否具有此属性。

不完全归纳推理在进行归纳时，仅考察相应事物的部分对象，即得出关于该事物的结论。②归纳推理---按照推理所使用的方法：（枚举\类比\统计\差异归纳）

枚举归纳推理在进行归纳时，若已知某类事物的有限可数个具体事物都具有某种属性，则可推出该类事物都具有此种属性。

例，设有如下事例：王强是计算机系学生，会编程序；高华是计算机系学生，会编程序；

……。当这些具体事例足够多时，即可归纳出一个一般性的知识：凡是计算机系的学生，就一定会编程序。

若两个(或两类)事物有许多属性相同或相似，推出其在其他属性上也相同或相似。例如，设A、B分别是两类事物的集合：A={a1,a2,…}，B={b1,b2,…}设ai与bi总是成对出现，且当ai有属性P时，bi就有属性Q与之对应，即：P(ai)→Q(bi)（i=1,2,…..）。当A与B中有一新的元素对出现时，若已知a’有属性P，b’有属性Q，则类比归纳出结论：P(a')→Q(b')

类比归纳推理的基础是相似原理，其可靠程度取决于两个或两类事物的相似程度,及这两个或两类事物的相同属性与推出的那个属性之间的相关程度。③类比归纳推理演绎推理是在已知领域内一般性知识的前提下，通过演绎，求解一个具体问题或者证明一个结论的正确性。其所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理不过是将已有事实揭露出来，因而不能增值新知识。归纳推理所推出的结论并未包含在前提内容中。这种由个别事物或现象推出一般性知识的过程，是增值新知识的过程。演绎推理与归纳推理的区别：⑵、按推理过程所用知识的确定性分类

确定性推理

不确定性推理⑶、按推理过程推出的结论是否单调增加分类

单调推理

非单调推理⑷、按推理过程是否利用问题的启发性知识分类

启发式推理

非启发式推理⑴、按推理的逻辑基础分类推理过程不仅依赖于所用的推理方法，同时也依赖于推理的控制策略。

推理的控制策略是指如何使用领域知识，使推理过程尽快达到目标的策略。推理的控制策略可分为：搜索策略、推理策略。4、推理的控制策略及其分类

在知识库中寻找可利用的知识，构造一条代价较小的推理路线，主要解决推理线路、推理效果、推理效率等问题。①按是否使用启发式信息可分为：

盲目搜索

启发式搜索②按问题的表示方式可分为：

状态空间搜索

与或树搜索⑴、搜索策略包括推理方向控制、求解、限制、冲突消解等策略。推理方向控制策略：用于确定推理的控制方向,可分为正向推理、

逆向推理、混合推理。求解策略：指仅求一个解，还是求所有解或最优解等。限制策略：指对推理的深度、宽度、时间、空间等进行的限制。冲突消解策略：当推理过程有多条知识可用时，如何从多条可用知识中选出一条最佳知识用于推理的策略。⑵、推理策略

正向推理从已知事实出发，正向使用推理规则。(数据驱动推理\前向链推理)从用户提供的初始已知事实出发，在知识库中找出当前可适用的知识，构成可适用的知识集KS；然后按某种冲突消解策略，从KS中选出一条知识进行推理，并将推出的新事实加入到数据库DB中，作为下一步推理的已知事实（中间事实）。在此之后，再从知识库中选取可适用的知识进行推理。重复进行这一过程，直到求得所要求的解。①推理方向控制策略●如何根据已知事实，到知识库中选取可用知识？●当知识库中有多条知识可用时，应该先使用那一条知识？这些问题涉及到了知识的匹配方法和冲突消解策略。优点：比较直观，允许用户主动提供有用的事实信息，适合于诊断、设计、预测、监控等领域的问题求解。缺点：推理无明确目标，求解问题时可能会执行许多与解无关的操作，导致推理效率较低。

逆向推理从某个假设目标出发，逆向使用推理规则。(目标驱动\逆向链)

首先选定一个假设目标，然后寻找支持该假设的证据。若所需的证据都能找到，说明原假设成立；若找不到所需证据,则说明原假设不成立，需要另作新的假设。优点：无需寻找和使用那些与假设目标无关的信息和知识，推理过程的目标明确，有利于向用户提供解释。（在诊断性专家系统中较为有效）缺点：当用户对解的情况认识不请时，由系统自主选择假设目标的盲目性比较大，若选择不好，可能需要多次提出假设，会影响系统效率。

混合推理将正向推理与逆向推理结合起来所进行的推理，是一种解决较复杂问题的方法。三种类型：先正向后逆向：先进行正向推理，从已知事实出发推出部分结果，然后再用逆向推理对这些结果进行证实或提高其可信度。先逆向后正向：先进行逆向推理，从假设目标出发推出一些中间假设，然后再用正向推理对这些中间假设进行证实。双向混合：正向推理和逆向推理同时进行，使推理过程在中间的某一步结合起来。内容提要1、推理的基本概念2、搜索策略3、自然演绎推理4、归结演绎推理5、基于规则的演绎推理二、搜索策略

搜索的基本概念

状态空间的搜索策略

与/或树的搜索策略

搜索的完备性与效率⑴、什么是搜索搜索是人工智能中的一个基本问题，与推理密切相关。搜索策略的优劣,将直接影响智能系统的性能与推理效率。搜索的定义：根据经验，利用已有知识，按照问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程。搜索的适用情况：不良结构或非结构化问题；难以获得求解所需的全部信息；没有现成的算法可供求解使用。1、搜索的基本概念①按是否使用启发式信息

盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间

信息并不改变控制策略。

启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导

搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。②按问题的表示方式

状态空间搜索：用状态空间法求解问题进行的搜索。

与或树搜索：用问题归约法求解问题进行的搜索。⑵、搜索的类型

状态空间搜索的基本思想

图搜索的一般过程

状态空间的盲目搜索广度优先搜索、

深度优先搜索、代价树搜索。

状态空间的启发式搜索启发性信息和估价函数、A算法和A*算法。2、状态空间的搜索策略①先将问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点。②然后检查问题的目标状态是否出现在这些子节点中。

若出现，则搜索成功，找到了问题的解；

若未出现，则再从已生成的子节点中选择一个节点作为当前扩展节点。③重复上述过程，直到目标状态出现在子节点中，或者没有可供操作的节点为止。对一个节点进行“扩展”---指对该节点用某个可用操作进行作用，生成该节点的一组子节点。⑴、状态空间搜索的基本思想OPEN表：未扩展节点表，用于存放刚(新)生成节点。CLOSED表：已扩展节点表，用于存放已经扩展或将要扩展节点。S：表示问题的初始状态。（起始节点）G：表示搜索过程所得到的搜索图。M：表示当前扩展节点新生成的、且不是自己先辈的子节点集。状态空间搜索算法的数据结构和符号约定3.1图搜索策略（GraphSearch）

图搜索控制可看成是一种在图中寻找路径的方法。

初始节点和目标节点分别代表初始数据库和满足终止条件的目标数据库。求得将一个数据库变换为另一数据库的规则序列问题,等价于求得图中的一条路径问题。⑴将初始节点S放入未扩展节点表OPEN表，并建立当前仅包含S的图G；⑵检查OPEN表是否为空，若为空，则问题无解，失败退出；⑶将OPEN表的第一个节点取出放入已扩展节点表CLOSED表，并记该节点为节点n；⑷考察节点n是否为目标节点。若是，则得到问题的解，成功退出。此时的解为追踪图G中沿着指针（步骤6中设置的指针）从n到初始节点S的路径。(5)扩展节点n，生成一组子节点。把这些子节点中不是节点n先辈的那部分子节点记入集合M，并把这些子节点作为节点n的子节点加入G中。1、图搜索的一般过程(6)针对M中子节点的不同情况，分别作如下处理：①对那些没有在G中出现过的M成员，设置一个指向其父节点(即节点n)的指针，并把它放入OPEN表。（新生成的）②对那些原来已在G中出现过，但还没有被扩展的M成员，确定是否需要修改它指向父节点(n)的指针。(已生成但未扩展的)③对那些先前已在G中出现过，并已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针。(已生成也扩展过的)(7)按某种策略,对OPEN表中的节点进行排序。(8)转第(2)步。⑴上述过程是状态空间的一般图搜索算法，具有通用性，后面所要讨论的各种状态空间搜索策略都是上述过程的一个特例。⑵各种搜索策略的主要区别在于“对OPEN表中节点的排列顺序不同”。

例如，广度优先搜索把先生成的子节点排在前面，而深

度优先搜索则把后生成的子节点排在前面。2、图搜索一般过程的几点说明⑶在第(6)步针对M中子节点的不同情况进行处理时，若发生第②种情况，那么，这个M中的节点究竟应该作为哪一个节点的后继节点呢？一般是由原始节点到该节点路径上所付出的代价来决定,哪一条路径付出的代价小，相应的节点就作为它的父节点。所谓由原始节点到该节点路径上的代价，是指这条路径上的所有“有向边”的代价之和。②对那些原来已在G中出现过，但还没有被扩展的M成员，确定是否需要修改它指向父节点(n)的指针。(已生成但未扩展的)⑷若发生第③种情况，除了需要确定该子节点指向父节点的指针外，还需要确定其后继节点指向父节点的指针。其依据也是由原始节点到该节点的路径上的代价。⑸在搜索图中，除初始节点外，任意一个节点都含有且只含有一个指向其父节点的指针。因此，由所有节点及其指向父节点的指针所构成的集合是一棵树，称为搜索树。③对那些先前已在G中出现过，并已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针。(已生成也扩展过的)⑹在搜索过程的第(4)步，一旦某个被考察的节点是目标节点，则搜索过程成功结束。此时，由初始节点到目标节点路径上的所有操作就构成了该问题的解，而路径由过程第(6)步所形成的指向父节点的指针来确定。⑺如果搜索过程终止在第(2)步，即没有达到目标，且OPEN表中已无可供扩展的节点，则失败结束。3.2盲目搜索

不需要重新安排OPEN表的搜索叫做“无信息搜索”或“盲目搜索”。（实际上是对解空间的遍历）包括：宽(广)度优先搜索深度优先搜索等代价搜索盲目搜索只适用于求解比较简单的问题。定义：以接近起始节点的程度逐层扩展节点的搜索方法。特点：一种高代价搜索，但若有解存在，则必能找到。3.2.1宽度优先搜索（Breadth-firstsearch）搜索是逐层进行的，在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。(解空间的横向遍历)从初始节点S开始逐层向下扩展，在第n层节点还未全部搜索完之前，不进入第n+1层节点的搜索。

未扩展节点表（OPEN表）中的节点，总是按进入的先后排序，先进入的节点排在前面，后进入的节点排在后面。1、宽度优先搜索的基本思想⑴将初始节点S放入OPEN表中；⑵如果OPEN表为空，则问题无解，失败退出；⑶将OPEN表的第一个节点取出放入CLOSED表，并记该节点为n；⑷考察节点n是否为目标节点。若是，则得到问题的解，成功退出；⑸若节点n不可扩展，则转第(2)步；⑹扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。2、宽度优先搜索算法流程思考：与原始算法比较异同，宽度优先的体现？优点：能够保证在搜索树中，找到一条通向目标节点的最短路径。宽度优先搜索算法流程-动态：八数码难题：

在3×3的方格棋盘上，分别放置了标有数字1、2、3、4、5、6、7、8的八张牌，初始状态S0，目标状态Sg，如下图所示。要求用宽度优先搜索策略，寻找从初始状态到目标状态的解路径。56741382S056748321Sg3、宽度优先搜索的例子八数码难题的宽度优先搜索树：八数码难题的宽度优先搜索树-动态：⑴对任意一个可扩展的节点，总是按照固定的操作符顺序对其进行扩展（空格左移、上移、右移、下移）。⑵在对任一节点进行扩展的时候，如果所得的某个子节点（状态）前面已经出现过，则立即将其放弃，不再重复画出（不送入OPEN表）。因此，宽度优先搜索的本质是：

以初始节点为根节点，在状态空间图中按照宽度优先的原则，生成一棵搜索树。（横向搜索）4、上述宽度优先算法中需注意的两个问题：优点：只要问题有解，用宽度优先搜索总可以得到解，而且得到的是路径最短的解。缺点：盲目性较大，当目标节点距初始节点较远时，将会产生许多无用节点，搜索效率低。5、宽度优先搜索的特点3.2.2深度优先搜索（Depth-firstsearch）首先扩展最新产生的（即最深的）节点，深度相等的节点可以任意排列。定义节点的深度如下：

起始节点（即根节点）的深度为0。

任何其他节点的深度，等于其父辈节点深度加1。特点：为防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度---深度界限。扩展最深(新)节点的结果,使得搜索沿着状态空间某条单一的路径，从起始节点向下进行。只有当搜索到达一个没有后裔的状态时，才考虑另一条替代的路径。(解空间纵向遍历)

⑴从初始节点S开始，在其子节点中选择一个最新生成的节点进行考察；⑵若该子节点不是目标节点且可以扩展，则扩展该子节点,然后再在此子节点的子节点中选择一个最新生成的节点进行考察；⑶依此向下搜索，直到某个子节点既不是目标节点，又不能继续扩展时，才选择其兄弟节点进行考察。1、深度优先搜索的基本思想

2、深度优先搜索算法流程⑴将初始节点S放入OPEN表中；⑵如果OPEN表为空，则问题无解，失败退出；⑶将OPEN表的第一个节点取出放入CLOSED表，并记该节点为n；⑷考察节点n是否为目标节点。若是，则得到问题的解，成功退出；⑸若节点n不可扩展，则转第(2)步；⑹扩展节点n，将其子节点放入OPEN表的首部，并为每一个子节点设置指向父节点的指针，然后转第⑵步。3、深度优先搜索的例子八数码问题深度优先搜索树？12384567目标状态

Sg12384567初始状态S0首先扩展最新产生的(最深的)节点，若目标节点不在当前搜索的分支上？

宽度优先搜索是将节点n的子节点放入到OPEN表的尾部，而深度优先搜索是把节点n的子节点放入到OPEN表的首部。在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上，则可较快地得到解。但是，如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。所以深度优先搜索是不完备的，即使问题有解，也不一定能求得解。深度优先搜索本质：以初始节点为根节点，在状态空间图中按照深度优先的原则，生成一棵搜索树。深度优先搜索与宽度优先搜索的唯一区别：4、有界深度优先搜索动机：为了防止搜索过程沿着无益的路径扩展下去，往往给出一个节

点扩展的最大深度，即深度界限。思想：对状态空间的深度优先搜索引入搜索深度界限，设为dm，当搜索深度达到了深度界限而仍未出现目标节点时，就换一个分支进行搜索。

即，沿着一条路径进行下去，直到深度界限为止，然后再考虑

只有最后一步有差别的相同深度或较浅深度可供选择的路径，接着再考虑最后两步有差别的那些路径。八数码难题：dm=55、注意问题如果问题有解，且其路径长度≤dm

，则上述搜索过程一定能求得解。但若解的路径长度>dm，则上述搜索过程就得不到解。这说明在有界深度优先搜索中，深度界限的选择是很重要的。要恰当地给出dm的值是比较困难的。否则即使能求出解，其也不一定是最优解。3.2.3等代价搜索有些问题并不要求应用算符序列为最少的解，而是要求具有某些特性的解。定义：是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。搜索树中每条连接弧

线上标识有代价,时间、距离等花费。算法应用的条件：该算法是针对代价树的算法。为了采用该算法对图进行搜索，必须先将图转换为代价树。代价树：边（连接弧线）上标有代价(或费用)的搜索树。在代价树中，若用g(x)表示从初始节点S到节点x的代价，用c(x1,x2)表示从父节点x1到子节点x2的代价，则有：g(x2)=g(x1)+c(x1,x2)代价树搜索：考虑边的代价的搜索方法，目的是为了找到一条代价最小的解路径。代价树搜索方法包括：代价树的广度优先搜索

代价树的深度优先搜索⑴、基本思想每次从OPEN表中选择节点往CLOSED表传送时，总是选择其中代价最小的节点。也就是说，OPEN表中的节点在任一时刻都是按其代价从小到大排序的。代价小的节点排在前面，代价大的节点排在后面，而不管节点在代价树中处于什么位置上。如果问题有解，代价树的宽度优先搜索一定可以求得解，并且求出的是最优解。1、代价树的宽度优先搜索⑵、代价树的宽度优先搜索算法流程①把初始节点S放入OPEN表中，置S的代价g(S)=0；②如果OPEN表为空，则问题无解，失败退出；③把OPEN表的第一个节点取出放入CLOSED表，并记该节点为n；④考察节点n是否为目标。若是，则找到了问题的解，成功退出；⑤若节点n不可扩展，则转第(2)步；否则转第(6)步；⑥扩展节点n，为每一个子节点都配置指向父节点的指针，计算各子节点的代价，并将各子节点放入OPEN表中。根据各子结点的代

价对OPEN表中的全部结点按由小到大的顺序排序。然后转第⑵步。设有5个城市，它们之间的交通线路如图所示，图中的数字表示两个城市之间的交通费用，即代价。用代价树的宽度优先搜索，求从A市出发到E市，费用最小的交通路线。ABCDE434523例子：城市交通问题解：首先将交通图转化为代价树。具体转化方法如下：①从起始节点A开始，把与它直接相邻的节点作为它的子节点。②对其他节点也做相同的处理。③若一个节点已经为某节点的直系

先辈节点时，就不能作为这个节点的子节点。④图中除了起始节点A之外，其它节点都可能要在代价树中出现多

次，为了区分它们的多次出现，分别用下标1,2，……标出。交通图的代价树245AC1B1D1D2E1E2B2C2E3E43434235245AC1B1D1D2E1E2B2C2E3E43434235对此代价树进行宽度优先搜索，可得到最优解，如图红线部分为最优解，其代价为8。ABCDE434523沿代价最小的路径搜索，即每次展开未展开节点中距离A点最近的那个节点。⑴、基本思想

与代价树的宽度优先搜索不同，深度优先搜索是从刚扩展出的子节点中选择一个代价最小的节点送入CLOSED表进行考察，而不是在整个OPEN表中选择代价最小的。2、代价树的深度优先搜索⑵、代价树的深度优先搜索算法流程①把初始节点S放入OPEN表中，置S的代价g(S)=0；②如果OPEN表为空，则问题无解，失败退出；③把OPEN表的第一个节点取出放入CLOSED表，并记该节点为n；④

考察节点n是否为目标节点。若是，则找到问题的解，成功退出；⑤若节点n不可扩展，则转第(2)步；⑥扩展节点n，生成其子节点，将这些子节点按边代价由小到大放入Open表的首部，并为每一个子节点设置指向父节点的指针。然后转第②步。上述几种搜索方法的本质是：以初始节点为根节点，按照既定的策略对状态空间图进行遍历，并希望能够尽早发现目标节点。由于对状态空间图遍历的策略是既定的，因此这些方法统称为盲目搜索方法。盲目搜索具有较大的盲目性，产生的无用节点较多，效率不高。状态空间的盲目搜索小结：盲目搜索的效率低，耗费过多的计算时间和空间，容易产生组合爆炸。若能找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，则搜索效率将会大为提高。(许多情况下，可通过检测来确定合理的顺序)下面介绍的搜索方法就是优先考虑这类检测，称这类搜索为启发式搜索(heuristicsearch)或有信息搜索(informedsearch)。3.3启发式搜索在盲目搜索中找到一个解，所需要扩展的节点数目可能是很大的，因为这些节点的扩展次序是随意的，而且没有利用已解决问题的任何特性。因此，除了那些最简单的问题之外，一般都需要占用很多时间或空间（或两者均有），这种结果是组合爆炸的一种表现形式。3.3.1启发式搜索策略和估价函数具体问题领域的信息常常可以用来简化搜索。假设初始状态、算符和目标状态的定义都是完全确定的，然后决定一个搜索空间。因此，问题就在于如何有效搜索这个给定空间。进行这种搜索的技术一般需要某些有关具体问题领域特性的信息，把这类特性信息称为启发信息，并把利用启发信息的搜索方法叫做“启发式搜索方法”。启发式搜索：采用问题自身的特性信息，以指导搜索朝着最有希望的方向前进。启发性信息：与具体问题求解过程有关，可指导搜索过程朝着最有希望方向前进的控制信息。(减少搜索范围，降低问题复杂度)

启发信息的启发能力越强，扩展的无用结点就越少。

强：降低搜索工作量，但可能导致找不到最优解。

弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能找到最优解。①帮助确定扩展节点的信息用于决定要扩展的下一个节点（最有希望的节点），以免像在宽度优先或深度优先搜索中那样盲目地扩展。(扩展谁)②帮助决定哪些后继节点应被生成的信息在扩展一个节点的过程中，用于决定要生成哪些后继节点，以免盲目生成所有节点。(生成谁)③决定在扩展一个节点时哪些节点应从搜索树上删除的信息利用第一种启发信息的状态空间搜索算法，即选择“最有希望”的节点作为下一个被扩展的节点。称为有序搜索(orderedsearch)。

估算节点希望程度的方法为估价函数。(重排每步open表节点顺序)启发性信息分类（按用途）:估价函数：用于评估节点重要性（希望程度）的函数。一般形式为：

f(x)=g(x)+h(x)其中，g(x)---从初始节点S0到节点x的代价；h(x)---启发函数。对从节点x到目标节点Sg的最优路径的代价的估计，体现了问题的启发性信息。设问题的初始状态S0和目标状态Sg如图所示。估价函数为：f(n)=d(n)+W(n)

d(n)：表示节点n在搜索树中的深度。

W(n)：表示节点n中“不在位”的数码个数。计算初始状态S0的估价函数值f(S0)。例子：八数码难题56741382S056748321Sg解：取g(n)=d(n)，h(n)=W(n)①说明是用从S0到n的路径上的单位

代价表示实际代价。②用结点n中“不在位”的数码个数作为启发信息。③一般来说，某节点中的“不在位”的数码个数越多，说明它离目标节点越远（代价的估计）。④对初始节点S0，d(S0)=0，W(S0)=3。因此，f(S0)=0+3=3

56741382S056748321Sg有序搜索又称为“最佳优先搜索”，它总是选择最有希望的节点作为下一个要扩展的节点。

实质：选择OPEN表中具有最小f值的节点作为下一个要扩展的节点。

尼尔逊（Nilsson）曾提出一个有序搜索的基本算法，估价函数f是这样确定的：一个节点的希望程度越大，其f值就越小。3.3.2有序搜索！被选为扩展的节点，是估价函数最小的节点。例子：八数码难题估价函数设置：f(n)=d(n)+W(n)

d(n):节点n的深度；W(n):错放的棋子数。12384567（目标状态）12384567（初始状态）由图可见，这里所求得的解答路径和用其它搜索方法找到的解答路径相同。不过，估价函数的应用显著地减少了被扩展的节点数。(若只用估价函数f(n)=d(n)，即得到宽度优先搜索过程)

正确选择估价函数，对确定搜索结果具有决定性作用。使用不能识别某些节点真实希望的估价函数，会形成非最小代价路径；而使用一个过多地估计了全部节点希望的估价函数(如宽度优先搜索方法得到的估价函数一样)又会扩展过多的节点。算法比较：八数码难题的深度优先搜索、宽度优先搜索和启发式搜索三种搜索方法的比较列于表中。136启发式搜索3418深度优先搜索4626宽度优先搜索生成节点数扩展节点数搜索算法有序搜索小结：f函数的重要性：

有序搜索的有效性直接取决于f,是提高搜索效率的关键；如果f不准确，可能失去最佳解，也可能失去全部解。f一般选择策略：

搜索时间与空间的折衷；保证有解或有最佳解。①最优解答状态空间中有多条不同代价的解答路径，求得最优解答，如A*算法。②搜索代价与解答质量的综合问题类似于①，但搜索过程可能超出时间与空间的界限。在适当的搜索中找到满意解答,并限制满意解答与最优解答的差异程度。如：TSP问题。③最小搜索代价不考虑解答的最优化（只有一个解答或多个解答间无差异），尽量使搜索代价最小。如：定理证明。f选择的三种典型情况⑴、A算法定义在图搜索算法中，如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对OPEN表中的节点排序，则该搜索算法为A算法。由于估价函数中带有问题自身的启发性信息。因此，A算法也被称为启发式搜索算法。⑵、A算法的类型可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为：

全局择优搜索算法：从OPEN表的所有节点中，选择估价函数值最小的一个节点进行扩展。

局部择优搜索算法：仅从刚生成的子节点中，选择估价函数值最小的一个子节点进行扩展。3.3.3A*算法A算法(1)把初始节点S0放入OPEN表，计算f(S0)。(2)如果OPEN表为空，则问题无解，退出。(3)把OPEN表的第一个节点（记为节点n）取出放入CLOSED表。(4)考察节点n是否为目标节点。若是，则求得了问题的解，退出。(5)若节点n不可扩展，则转第(2)步。(6)扩展节点n，用估价函数f(x)计算每个子节点的估价值，并为每一个子节点都配置指向父节点的指针。把这些子节点都送入OPEN表中，然后对OPEN表中的全部节点按估价值从小至大的顺序进行排序，然后转第(2)步。全局择优搜索算法流程：设问题的初始状态S0和目标状态Sg如图所示。估价函数为：f(n)=d(n)+w(n)d(n)：表示节点n在搜索树中的深度w(n)：表示节点n中“不在位”的数码个数用全局择优搜索解决该问题。全局择优搜索算法：八数码难题56741382S056748321Sg解：该问题的全局择优搜索树如右图所示。图中，每个节点旁边的数字是该节点的估价函数值。该问题的解为：

S0→S1→S2→S3→Sg局部择优搜索算法流程：(1)把初始节点S0放入OPEN表，计算f(S0)。(2)如果OPEN表为空，则问题无解，退出。(3)把OPEN表的第一个节点（记为节点n）取出放入CLOSED表。(4)考察节点n是否为目标节点。若是，则求得了问题的解，退出。(5)若节点n不可扩展，则转第(2)步。(6)扩展节点n，用估价函数f(x)计算每个子节点的估价值，并按估价值

从小到大的顺序放到OPEN表中的首部，并为每一个子节点都配置指向其父节点的指针，然后转第(2)步。A*算法是对A算法的估价函数f(n)=g(n)+h(n)加上某些限制后得到的一种启发式搜索算法。假设f*(n)是从初始节点S出发经过节点n达到目标节点的最小代价，估价函数f(n)是对f*(n)的估计值。且f*(n)=g*(n)+h*(n)

A*算法对A算法（全局择优的启发式搜索算法）中的g(n)和h(n)分别提出如下限制：第一，g(n)是对最小代价g*(n)的估计，且g(n)>0；第二，h(n)是最小代价h*(n)的下界,即对任意节点n均有h(n)≤h*(n)。即：满足上述两条限制的A算法称为A*算法。A*算法在A*算法中，g(n)比较容易得到，它实际上就是从初始节点S0到节点n的路径代价，恒有：g(n)≥g*(n)在算法执行过程中，随着更多搜索信息的获得，g(n)呈下降的趋势。如右图的例子：对S0扩展后g(n1)=3，g(n2)=7对n1扩展后g(n2)=6，g(n3)=5S0n137n2n332可纳性的含义：对任一状态空间图，当从初始节点到目标节点有路经存在时，如果搜索算法总能在有限步骤内找到一条从初始节点到目标节点的最佳路径，并在此路径上结束，则称该搜索算法是可纳的。

A*算法是可纳的，即它能在有限步内终止，并找到问题的最优解。A*算法的可纳性:第一步：对于有限图，A*算法一定会在有限步骤内终止。第二步：对于无限图，如果从初始节点S0到目标节点Sg有路径存在，则A*算法也必然会终止。第三步：A*算法一定终止在最优路径上。A*算法的可纳性证明：h(n)的确定依赖于具体问题领域的启发性信息，其中h(n)≤h*(n)的限制是十分重要的，它可以保证A*算法能找到问题的最优解。A*算法的搜索效率很大程度上取决于估价函数h(n)。一般来说，在满足h(n)≤h*(n)的前提下，h(n)的值越大越好。h(n)的值越大，说明它携带的启发性信息越多，A*算法搜索时扩展的节点就越少，搜索效率就越高。A*算法的最优性:在A*算法中，每当扩展一个节点n时，都需要检查其子节点是否已在OPEN表或CLOSED表中。对已在OPEN表中的子节点，需要决定是否调整指向其父节点的指针；对已在CLOSED表中的子节点，除需要决定是否调整其指向父节点的指针外，还需要决定是否调整其子节点的后继节点的父指针。如果能够保证，每当扩展一个节点时就已经找到了通往这个节点的最佳路径，则没有必要再作上述检查。h(n)的单调限制:为能够保证，每当扩展一个节点时就已经找到了通往这个节点的最佳路径，需要对启发函数h(n)增加单调性限制。如果启发函数满足以下两个条件:

h(Sg)=0;

对任意节点ni及其任一子节点nj，都有:0≤h(ni)-h(nj)≤c(ni,nj)其中c(ni,nj)是ni到其子节点nj的边代价，则称h(n)满足单调限制。证明：设A*正要扩展节点n，而节点序列S0=n0,n1,…,nk=n是由初始节点S0到节点n的最佳路径。其中，ni是这个序列中最后一个位于CLOSED表中的节点，则上述节点序列中的ni+1节点必定在OPEN表中，由h(n)的单调条件可知：g*(ni)+h(ni)≤g*(ni)+c(ni,ni+1)+h(ni+1)所以：g*(ni)+h(ni)≤g*(ni+1)+h(ni+1)依此类推可得：g*(ni+1)+h(ni+1)≤g*(nk)+h(nk)=g*(n)+h(n)由于节点ni+1在最佳路径上，故有f(ni+1)≤g*(n)+h(n)因为这时A*扩展节点n而不扩展节点ni+1，则有：

f(n)=g(n)+h(n)≤f(ni+1)≤g*(n)+h(n)即g(n)≤g*(n)，g*(n)是最小代价值。所以有g(n)=g*(n)如果h(n)满足单调条件，则当A*算法扩展节点n时，该节点就已经找到了通往它的最佳路径，即g(n)=g*(n)。证明：假设节点ni+1在节点ni之后立即扩展，由单调限制条件可知：

h(ni)-h(ni+1)≤c(ni,ni+1)即：(f(ni)-g(ni))-(f(ni+1)-g(ni+1))≤c(ni,ni+1)亦即：f(ni)-g(ni)-f(ni+1)+g(ni)+c(ni,ni+1)≤c(ni,ni+1)所以：f(ni)-f(ni+1)≤0即：f(ni)≤f(ni+1)

以上两个定理都是在h(n)满足单调性限制的前提下才成立的。如果h(n)不满足单调性限制，则它们不一定成立。如果h(n)满足单调限制，则A*算法扩展的节点序列的f值是非递减的，即f(ni)≤f(ni+1)。f(n)=g(n)+h(n)g(n)深度h(n)与目标的距离f*=g*+h*A*算法应用：八数码难题3.4消解原理第2章中，我们已介绍了谓词逻辑表示法（谓词演算、谓词公式、置换合一）的相关概念。谓词演算中，利用前面列出的等价式和永真蕴含式，可以从已知的一些公式推导出新的公式。导出的新公式叫做定理，推导过程中使用的推理规则序列即是该定理的一个证明。本节所要介绍的“消解原理(归结原理)”正是定理证明的基础，是应用于“子句”的一种公式类。消解是一种可用于子句公式的重要推理规则。子句由文字的“析取”组成的公式。（任何文字的“析取式”）

文字：一个原子公式和原子公式的否定。如：P∨Q、～(P∨Q)、～P(x,f(x),y)∨Q(y)等都是子句。什么是消解、子句？文字析取组成的公式原子公式、原子公式的否定P(x1,x2,...,xn)称为谓词演算的原子公式子句[P∨Q、～P(x,f(x),y)∨Q(x)∨R(f(x)]如：

E1∨E2

（前提）

～E2∨E3

（前提）

E1∨E3逻辑上成立（结论）消解过程应用于“母体子句对”，以产生一个“导出子句”。并称，“E1∧E3”为“E1∨E2”和“～E2∨E3”的消解式。母体子句对导出子句3.4.1子句集的求取（9步法）

说明消解过程之前，首先说明任一谓词演算公式均可以变换为一个子句集。将谓词公式变换为为子句集的步骤：①消去蕴涵符号②减少否定符号的管辖域③对变量标准化④消去存在量词⑤化为前束形⑥把母式化为合取范式⑦消去全称量词⑧消去连词符号∧⑨更换变量名例：将下列谓词演算公式化为一个子句集。(x){P(x){(y)[P(y)P(f(x,y))]∧～(y)[Q(x,y)P(y)]}}只应用∨和～符号，以～A∨B替换AB（或AB）。⑴、消去蕴涵符号(x){～P(x)∨{(y)[～P(y)∨P(f(x,y))]∧～(y)[～Q(x,y)∨P(y)]}}⑵、减少否定符号的管辖域(x){～P(x)∨{(y)[～P(y)∨P(f(x,y))]∧(y){～[～Q(x,y)∨P(y)]}}}①(x){～P(x)∨{(y)[～P(y)∨P(f(x,y))]∧～(y)[～Q(x,y)∨P(y)]}}每个否定符号“～”最多只用到一个谓词符号上，并反复应用摩根定律。以～A∨～B代替～(A∧B)以～A∧～B代替～(A∨B)以A代替～(～A)以(x){～A}代替～(x)A以(x){～A}代替～(x)A将～移到后面，“全称”改“存在”。(x){～P(x)∨{(y)[～P(y)∨P(f(x,y))]∧(y)[Q(x,y)∧～P(y)]}}任一量词辖域内，受该量词约束的变量为一哑元(虚构变量),它可以在该辖域内被另一个未出现过的变量代替,而不改变公式的真值。合式公式中变量的标准化意味着对哑元改名,以保证每个量词有其惟一的哑元。⑶、对变量标准化②(x){～P(x)∨{(y)[～P(y)∨P(f(x,y))]∧(y)[Q(x,y)∧～P(y)]}}(x){～P(x)∨{(y)[～P(y)∨P(f(x,y))]∧(w)[Q(x,w)∧～P(w)]}}{w/y}(x){P(x)∧(x)Q(x)}(x){P(x)∧(y)Q(y)}如：⑷、消去存在量词以Skolem函数代替存在量词内的约束变量，然后消去存在量词。规则：

对于一个受存在量词约束的变量，若不受全称量词约束,则该变量可用一个常量代替。(x)P(x)P(A)公式(y)[(x)P(x,y)]中，因存在量词处于全称量词的辖域内，则所存在的x可能依赖于y值。令这种依赖关系明显地由函数g(y)所定义,它把每个y值映射到存在的那个的x，即x=g(y)。---Skolem函数

若该变量受全称量词约束，则该变量用一个S函数代替,S函数的变量即全称量词的量化变量。(y){(x)P(x,y)}(y){P(g(y),y)}Skolem函数替代常量或函数必须是新的，是公式中没出现过的。③(x){～P(x)∨{(y)[～P(y)∨P(f(x,y))]∧(w)[Q(x,w)∧～P(w)]}}(x){～P(x)∨{(y)[～P(y)∨P(f(x,y))]∧[Q(x,g(x))∧～P(g(x))]}}w=g(x)为Skolem函数⑸、化为前束形(x)(y){～P(x)∨{[～P(y)∨P(f(x,y))]∧[Q(x,g(x))∧～P(g(x))]}}④(x){～P(x)∨{(y)[～P(y)∨P(f(x,y))]∧[Q(x,g(x))∧～P(g(x))]}}把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。前束形={前缀}{母式}

全称量词串无量词公式⑹、把母式化为合取范式A∨{B∧C}{A∨B}

∧{A∨C}(x)(y){[～P(x)∨～P(y)∨P(f(x,y))]∧[～P(x)∨[Q(x,g(x))∧～P(g(x)]]}⑤(x)(y){～P(x)∨{[～P(y)∨P(f(x,y))]∧[Q(x,g(x))∧～P(g(x))]}}任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。(反复应用分配律)ABCBCA(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))]}⑥(x)(y){[～P(x)∨～P(y)∨P(f(x,y))]∧[～P(x)∨Q(x,g(x))]∧[～P(x)∨～P(g(x))]}所有余下的量词均被全称量词量化了。消去前缀，即消去明显出现的全称量词。⑻、消去连词符号∧～P(x)∨～P(y)∨P(f(x,y))～P(x)∨Q(x,g(x))～P(x)∨～P(g(x))⑦{[～P(x)∨～P(y)∨P(f(x,y))]∧[～P(x)∨Q(x,g(x))]∧[～P(x)∨～P(g(x))]}用{A,B}代替(A∧B)，消去符号∧。最后得到一个有限集，其中每个公式都是文字的析取。××⑼、更换变量名称⑧～P(x)∨～P(y)∨P(f(x,y))

～P(x)∨Q(x,g(x))

～P(x)∨～P(g(x))⑨

～P(x1)∨～P(y)∨P[f(x1,y)]

～P(x2)∨Q[x2,g(x2)]

～P(x3)∨～P[g(x3)]更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。（用x1，x2，x3代替x）3.4.2消解推理规则消解式的定义：令L1，L2为两任意原子公式；

L1和L2具有相同的谓词符号，但一般具有不同的变量。已知两子句L1∨α和～L2∨β，如果L1和L2具有最一般合一者σ,那么通过消解可以从这两个父辈子句推导出一个新子句(α∨β)σ。这个新子句叫做消解式。消解式求法:取各子句的析取，然后消去互补对。命题逻辑的消解推理举例：假言推理：P～P∨Q(即P→Q)消解式：Q合并：P∨Q～P∨Q消解式：Q∨Q=Q重言式：P∨Q～P∨～Q消解式：Q∨～Q或P∨～P空子句(矛盾)：P～P消解式：NIL链式(三段论)：～P∨Q(即P→Q)～Q∨R(即Q→R)消解式：～P∨R(即P→R)3.4.3含有变量的消解式要把消解推理规则推广到含有变量的子句，必须找到一个作用于父辈子句的置换，使父辈子句含有互补文字。例：B(x)～B(x)∨C(x)C(x)P(x)∨Q(x)～Q[f(y)]P[f(y)]置换σ={f(y)/x}P[x,f(y)]∨Q(x)∨R[f(a),y]～P[f(f(a)),z]∨R(z,w)Q[f(f(a))]∨R(f(a),y)∨R(f(y),w)σ={f(f(a))/x,f(y)/z}！消解推理的常用规则，参见教材中“子句和消解式”对应表。3.4.4消解反演求解过程将要解决的问题作为一个要证明的命题，消解通过反演产生证明。

即,要证明某个命题，其目标公式被否定并化成子句形,然后添加到命题公式集中去,把消解反演系统应用于联合集,推出一个空子句(NIL),产生一个矛盾，从而使定理得到证明。消解反演的证明思想，与数学中反证法的思想十分相似。给出一个公式集{S}和目标公式L，通过反证或反演来求证目标公式L。步骤如下：⑴否定L，得～L；⑵把～L添加到S中去；⑶把新产生的集合｛～L，S｝化成子句集；⑷应用消解原理，推导出一个表示矛盾的空子句。1、消解反演讨论：

设公式L在逻辑上遵循公式集S按照定义，满足S的每个解释也满足L，绝不会有满足S的解释能够满足～L的。所以，不存在能够满足并集“S∪{～L}”的解释。

若一个公式集不能被任一解释所满足，则这个公式是不可满足的。

因此，如果L在逻辑上遵循S，那么S∪{～L}是不可满足的。

可证：若将消解反演，反复应用到不可满足的子句集，则最终会产生空子句NIL。因此，如果L在逻辑上遵循S，那么由并集S∪{～L}消解得到的子句,最后将产生空子句。

反之也可证：若从S∪{～L}的子句消解得到空子句，那么L在逻辑上遵循S。例：储蓄问题

前提：每个储蓄钱的人都获得利息。

结论：如果没有利息，那么就没有人去储蓄钱。⑴规定原子公式：

S(x,y)表示“x储蓄y”M(x)表示“x是钱”

I(x)表示“x是利息”

E(x,y)表示“x获得y”⑵用谓词公式表示前提和结论：前提：(x){[(y)(S(x,y)∧M(y)][(y)(I(y)∧E(x,y))]}结论：～(x)I(x)(x)(y)(M(y)

～S(x,y))⑶化为子句形把前提化为子句形：(x){[(y)(S(x,y)∧M(y)][(y)(I(y)∧E(x,y))]}(x)((～[(y)(S(x,y)∧M(y))]∨((y)(I(y)∧E(x,y))))(x)(((y)(～

S(x,y)∨～

M(y))∨((y)(I(y)∧E(x,y))))(x)(((y)(～

S(x,y)∨～

M(y))∨(I(f(x))∧E(x,f(x))))Y=f(x)为Skolem函数(x)(y)(((～S(x,y))∨～M(y)∨I(f(x)))∧(～S(x,y)∨～M(y)∨E(x,f(x)))))①～S(x,y)∨～M(y)∨I(f(x))②～S(x1,y1)∨～M(y1)∨E(x1,f(x1))结论：～(x)I(x)(x)(y)(M(y)

～S(x,y))把结论的否定化为子句形：结论的否定：

～(～(x)I(x)(x)(y)(M(y)

～S(x,y)))③～I(z)④S(a,b)⑤M(b)～((x)I(x)

∨(x)(y)(～

M(y)∨

～S(x,y)))(～((x)I(x))∧(～(x)(y)(～

M(y)∨～S(x,y)))((x)(～

I(x))∧((x)(y)(M(y)∧S(x,y)))((z)(～

I(z))∧((x)(y)(M(y)∧S(x,y)))(～

I(z))∧((M(b)∧S(a,b)))把前提化为子句形：①

～S(x,y)∨～M(y)∨I(f(x))②

～S(x1,y1)∨～M(y1)∨E(x1,f(x1))把结论的否定化为子句形：③～I(z)④S(a,b)⑤M(b)⑷

消解反演求NIL图：储蓄问题反演树～M(b)NIL子句（5）子句（7）子句（4）{a/x,b/y}子句（1）子句（3）f(x)/z～S(x,y)∨～M(y)子句（6）消解方法小结：

求子句集，进行归结，方法简单

通过修改证明树的方法，提取回答

方法通用

求解效率低，不宜引入启发信息

不宜理解推理过程3.5规则演绎系统以上介绍的经典求解方法，对于比较复杂的问题，很难甚至无法解决。因此，需要有更好的求解方法。包括：

规则演绎系统

产生式系统

系统组织技术

不确定性推理

非单调推理对于许多公式来说，子句形是一种低效率的表达式，因为一些重要信息可能在求取子句形过程中丢失。采用易于叙述的if-then(如果-那么)规则来求解问题更为直接。规则演绎系统概述其中，If部分可能由几个if组成，而Then部分可能由一个或一个以上的then组成。基于规则的问题求解系统，运用下述规则来建立:在所有基于规则的系统中，每个if可能与某断言集中的一个或多个断言匹配（断言集→工作内存），then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统(rulebaseddeductionsystem)。有时，then部分用于规定动作。这时，称这种基于规则的系统为反应式系统(reactionsystem)或产生式系统(production

system)。

规则演绎系统属于高级搜索推理技术；

其知识表示分为两类：规则和事实；

规则由形如：If…Then

的蕴涵式表示；

事实由谓词公式（不包括蕴涵式）表示；

if部分称为前项，then部分称为后项；

根据事实和规则，采用直接法而不是反演系统证明目标公式，强调

用规则进行演绎。

类型可分为：正向演绎、逆向演绎、双向演绎；（与或形变换(子句集)、与或图表示、叶节点文字的析取）3.6产生式系统（ProductionSystem）历史悠久且使用最多的知识表示系统，早在自动机理论、形式文法和程序语言中即得到广泛应用。主要用来描述若干个不同的，但以一个基本概念为基础的系统。这个基本概念就是产生式规则（或产生式条件）和操作对的概念。产生式系统中，论域的知识分为两部分：①用事实表示的静态知识（如事物、事件和它们之间的关系）②用产生式规则表示的推理过程和行为系统的知识库主要用于存储规则，因此又将此类系统称为基于规则的系统。3.6.1产生式系统的基本结构许多成功的专家系统都采用产生式系统的典型结构，用产生式规则来表达知识。通常，一个产生式系统包含事实库、规则集和规则解释（控制器）三部分。⑴、事实库存放当前已知的知识信息数据，包括推理过程中形成的中间结论知识。即用于存储有关问题的状态