课程学习人工智能第三章

人工智能原理

ArtificialIntelligencePrinciple

信息工程学院张永梅3.1图搜索策略

3.2盲目搜索3.3启发式搜索第三章搜索推理技术3.4产生式系统

3.5不确定推理3.6非单调推理

第三章搜索推理技术作业：

3-8，3-9，3-15第三章搜索推理技术实验：

实验2：产生式系统实验。熟悉和掌握产生式系统的运行机制，掌握基于规则推理的基本方法。实验1：启发式搜索算法。熟悉和掌握启发式搜索的定义、估价函数和算法过程，并求解博弈问题，理解求解流程和搜索顺序。3.1图搜索策略对于给定的问题，智能系统的行为一般是找到能够达到所希望目标的动作序列，并使其所付出的代价最小、性能最好。基于给定的问题，问题求解的第一步是目标的表示。搜索就是找到智能系统的动作序列的过程。搜索是人工智能中的一个基本问题，并与推理密切相关，搜索策略的优劣，将直接影响到智能系统的性能与推理效率。3.1图搜索策略搜索算法的输入是给定的问题，输出时表示为动作序列的方案。一旦有了方案，就可以执行该方案所给出的动作了。（执行阶段）求解问题包括：目标表示搜索执行

3.1图搜索策略

给定问题就是确定该问题的基本信息:其中，初始状态集合和操作符集合定义了问题的搜索空间。初始状态集合：定义了问题的初始状态。操作符集合：把一个问题从一个状态变换为另一个状态的动作集合。目标检测函数：用来确定一个状态是不是目标。路径费用函数：对每条路径赋予一定费用的函数。搜索问题包括：搜索什么(目标)在哪里搜索(搜索空间)搜索分成：状态空间的生成阶段在该状态空间中对所求问题状态的搜索搜索可以根据是否使用启发式信息分为:盲目搜索启发式搜索3.1图搜索策略盲目搜索只是可以区分出哪个是目标状态。一般是按预定的搜索策略进行搜索。没有考虑到问题本身的特性，这种搜索具有很大的盲目性，效率不高，不便于复杂问题的求解。启发式搜索是在搜索过程中加入了与问题有关的启发式信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解。根据问题的表示方式分为状态空间搜索与/或树搜索状态空间搜索是用状态空间法来求解问题所进行的搜索与/或树搜索是指用问题规约方法来求解问题时所进行的搜索。树

树是一类重要的非线性数据结构，是以分支关系定义的层次结构。树的定义定义：树(tree)是n(n>0)个结点的有限集T，其中：有且仅有一个特定的结点，称为树的根(root)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)特点：树中至少有一个结点——根树中各子树是互不相交的集合A只有根结点的树ABCDEFGHIJKLM有子树的树根子树基本术语结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)——结点拥有的子树数叶子(leaf)——度为0的结点孩子(child)——结点子树的根称为该结点的孩子双亲(parents)——孩子结点的上层结点叫该结点的~兄弟(sibling)——同一双亲的孩子树的度——一棵树中最大的结点度数结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层……深度(depth)——树中结点的最大层次数森林(forest)——m(m0)棵互不相交的树的集合ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点A是结点F，G的祖先搜索策略评价标准:完备性：如果存在一个解答，该策略是否保证能够找到？时间复杂性：需要多长时间可以找到解答？空间复杂性：执行搜索需要多少存储空间？最优性：如果存在不同的几个解答，该策略是否可以发现最高质量的解答？

考虑一个问题的状态空间为一棵树的形式。如果根节点首先扩展，然后是扩展根节点生成的所有节点，然后是这些节点的后继，如此反复下去。在树的最深一层的节点中扩展一个节点。只有当搜索遇到一个死亡节点（非目标节点，并且是无法扩展的节点）的时候，才返回上一层选择其他的节点搜索。宽度优先搜索深度优先搜索图图的定义和术语图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中：V(G)是顶点的非空有限集

E(G)是边的有限集合，边是顶点的无序对或有序对有向图——有向图G是由两个集合V(G)和E(G)组成的

其中：V(G)是顶点的非空有限集

E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为<v,w>，v,w是顶点，v为弧尾，w为弧头无向图——无向图G是由两个集合V(G)和E(G)组成的

其中：V(G)是顶点的非空有限集

E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v) 权——与图的边或弧相关的数叫~网——带权的图叫~子图——如果图G(V,E)和图G‘(V’,E‘),满足：V’VE’E

则称G‘为G的子图顶点的度无向图中，顶点的度为与每个顶点相连的边数有向图中，顶点的度分成入度与出度入度：以该顶点为头的弧的数目出度：以该顶点为尾的弧的数目路径——路径是顶点的序列V={Vi0,Vi1,……Vin}，满足(Vij-1,Vij)E或<Vij-1,Vij>E,(1<jn)路径长度——沿路径边的数目或沿路径各边权值之和回路——第一个顶点和最后一个顶点相同的路径叫~简单路径——序列中顶点不重复出现的路径叫~简单回路——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫~连通——从顶点V到顶点W有一条路径，则说V和W是连通的连通图——图中任意两个顶点都是连通的叫~连通分量——非连通图的每一个连通部分叫~强连通图——有向图中，如果对每一对Vi,VjV,ViVj,从Vi到Vj和从Vj到Vi都存在路径，则称G是~连通图例245136强连通图356例非连通图连通分量例245136图的遍历与连通性从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历(GraphTraversal)。图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组visited[]。辅助数组visited[]的初始状态为0,在图的遍历过程中,一旦某一个顶点i

被访问,就立即使visited[i]

为1,防止它被多次访问。图的遍历的分类:深度优先搜索

DFS(DepthFirstSearch)广度优先搜索

BFS(BreadthFirstSearch)DFS在访问图中某一起始顶点v

后,由

v

出发,访问它的任一邻接顶点

w1;再从w1出发,访问与w1邻

接但还没有访问过的顶点w2;然后再从w2出发,进行类似的访问,…,如此进行下去,直至到达所有的邻接顶点都被访问过的顶点u为止。接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。V1V2V4V5V3V7V6V8例深度遍历：V1V2V4V8V5V6V3V7BFS在访问了起始顶点

v之后,由

v出发,依次访问

v

的各个未被访问过的邻接顶点w1,w2,…,wt,然后再顺序访问w1,w2,…,wt的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，…，如此做下去，直到图中所有顶点都被访问到为止。V1V2V4V5V3V7V6V8例广度遍历：V1V2V3V4V5V6V7V8连通分量(Connectedcomponent)当无向图为非连通图时,从图中某一顶点出发,利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点,只能访问到该顶点所在的最大连通子图(连通分量)的所有顶点。若从无向图的每一个连通分量中的一个顶点出发进行遍历,可求得无向图的所有连通分量。在算法中,

需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。无论是宽度优先搜索还是深度优先搜索，遍历节点的顺序一般都是固定的，即一旦搜索空间给定，节点遍历的顺序就固定了。这种类型的遍历称为“确定性”的，也就是盲目搜索。3.1图搜索策略3.2盲目搜索

3.3启发式搜索第三章搜索推理技术3.4产生式系统

3.5不确定推理3.6非单调推理

3.2盲目搜索方法

ProcedureGenerate&Test（生成与测试）Begin Repeat

生成一个新的状态，称为当前状态；

Until当前状态=目标；End.上述算法在每次Repeat-Until循环中都生成一个新的状态，并且只有当新的状态等于目标状态的时候才退出。在该算法中最重要的部分是新状态的生成。盲目搜索（Blindsearch)不考虑问题本身的特性，按预定的路线进行搜索。效率不高，不便于复杂问题的求解。两种典型的用于搜索的状态生成方法：宽度优先深度优先3.2.1宽度优先搜索

沿着树的宽度遍历树的节点，它从深度为1的层开始，直到最深的层次。它可以很容易地用队列实现。ProcedureBreadth-first-searchBegin

把初始节点放入队列；

Repeat

取得队列最前面的元素为current; Ifcurrent=goal

成功返回并结束；

Elsedo Begin

如果current有子女，则current的子女 以任意次序添加到队列的尾部；

EndUntil队列为空

End采用队列结构，宽度优先算法可以表示如下：队列(Queue)的定义队列是限定仅在表的一端进行插入，在另一端进行删除操作的线性表。允许插入的一端称为队尾(rear)，允许删除的一端称为队首(front)。

队列的插入操作，称为入队；队列的删除操作，称为出队。当队列中没有元素时称为空队列。设队列q=(a0，a1，a2，…，an-1)，则a0称为队头元素，an-1称为队尾元素。元素按a0，a1，a2，…，an-1的次序入队，出队也只能按照这个次序。

队列和栈相反，队列的操作是按先进先出（FirstInFirstOut）的原则进行的，又称为先进先出的线性表（简称FIFO表）。如果当前的节点不是目标节点，则把当点节点的子孙以任意顺序增加到队列的后面，并把队列的前端元素定义为current。如果目标发现，则算法终止。

宽度优先搜索算法原理：宽度优先搜索是一种盲目搜索，时间和空间复杂度都比较高，当目标节点距离初始节点较远时会产生许多无用的节点，搜索效率低。宽度优先搜索优点：目标节点如果存在，用宽度优先搜索算法总可以找到该目标节点，而且是最小（即最短路径）的节点。宽度优先搜索中，时间需求是一个很大的问题，特别是当搜索的深度比较大时，尤为严重。3.2.2深度优先搜索

深度优先搜索生成节点并与目标节点进行比较是沿着树的最大深度方向进行的，只有当上次访问的节点不是目标节点，而且没有其他节点可以生成的时候，才转到上次访问节点的父节点。转移到父节点后，该算法会搜索父节点的其他的子节点。深度优先搜索也称为回溯搜索，它总是首先扩展树的最深层次上的某个节点，只是当搜索遇到一个死亡节点（非目标节点而且不可扩展），搜索方法才会返回并扩展浅层次的节点。上述原理对树中的每一节点是递归实现的(实现该递归用栈)。

ProcedureDepthFirstSearch Begin

把初始节点压入栈，并设置栈顶指针；

While栈不空do Begin

弹出栈顶元素；

If栈顶元素=goal，成功返回并结束；

Else以任意次序把栈顶元素的子女压入栈中；

EndWhile End基于栈实现的深度优先搜索算法：

初始节点放到栈中，栈指针指向栈的最上边的元素。为了对该节点进行检测，需要从栈中弹出该节点，如果是目标，该算法结束，否则把其子节点以任何顺序压入栈中。该过程直到栈变成为空。堆栈(Stack)：栈是允许在一端进行插入和删除操作的特殊线性表。

a1a2……an栈底栈顶MAXSIZETOP

允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。栈结构也称为后进先出表（LIFO）。

3.2.3迭代加深搜索

有界深度优先搜索过程总体上按深度优先算法方法进行，但对搜索深度需要给出一个深度限制dm，当深度达到了dm的时候，如果还没有找到解答，就停止对该分支的搜索，换到另外一个分支进行搜索。策略说明:（1）深度限制dm很重要。当问题有解，且解的路径长度小于或等于dm时，则搜索过程一定能够找到解，但是和深度优先搜索一样，这并不能保证最先找到的是最优解。但是当dm取得太小，解的路径长度大于dm时，则搜索过程中就找不到解，即这时搜索过程甚至是不完备的。完备性：如果存在一个解答，该策略是否保证能够找到？（2）深度限制dm不能太大。当dm太大时，搜索过程会产生过多的无用节点，既浪费了计算机资源，又降低了搜索效率。（3）有界深度搜索的主要问题是深度限制值dm的选取。

改进方法：

（迭代加深搜索）先任意给定一个较小的数作为dm，然后按有界深度算法搜索，若在此深度限制内找到了解，则算法结束；如在此限制内没有找到问题的解，则增大深度限制dm，继续搜索。迭代加深搜索，试图尝试所有可能的深度限制：首先深度为0，然后深度为1，然后为2，等等。如果初始深度为0，则该算法只生成根节点，并检测它。如果根节点不是目标，则深度加1，通过典型的深度优先算法，生成深度为1的树。当深度限制为m时，树的深度为m。

3.1图搜索策略3.2盲目搜索3.3启发式搜索第三章搜索推理技术3.4产生式系统

3.5不确定推理3.6非单调推理

3.3启发式搜索

如果能够利用问题自身的一些特征信息来指导搜索过程，则可以缩小搜索范围，提高搜索效率。像这样利用问题自身特征信息来引导搜索过程的方法称为启发式方法。盲目搜索可能带来组合爆炸启发式信息

用来加速搜索过程的有关问题领域的特征信息。人们解决问题的基本方法是方案--试验法，对各种可能的方案进行试验，直至找到正确的方案。搜索策略有盲目搜索、启发式搜索之分。盲目搜索是对可能方案进行顺序的试验；启发式搜索是依照经验或某种启发式信息，摒弃希望不大的搜索方向。启发式搜索大大加快搜索过程，使得人们处理问题效率得到提高。

启发式搜索用于两种不同类型的问题：前向推理反向推理关键问题：如何利用知识，尽可能有效地找到问题的解（最佳解）。前向推理一般用于状态空间的搜索。在前向推理中，推理是从预先定义的初始状态出发向目标状态方向执行。反向推理一般用于问题规约中。在反向推理中，推理是从给定的目标状态向初始状态执行。状态空间表示概念详释OriginalStateMiddleStateGoalState2.2状态空间法特点：选择最有希望的节点加以扩展种类：有序搜索、A*算法等启发性信息的概念

启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。

3.3.1启发式搜索策略和估价函数启发性信息启发性信息的种类

①有效地帮助确定扩展节点的信息；②有效地帮助决定哪些后继节点应被生成的信息；③能决定在扩展一个节点时哪些节点应从搜索树上删除的信息。启发性信息的作用

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

估价函数用来估计节点重要性的函数。估价函数f(n)被定义为从初始节点S0出发，约束经过节点n到达目标节点Sg的所有路径中最小路径代价的估计值。它的一般形式为：

f(n)=g(n)+h(n)

其中，g(n)是从初始节点S0到节点n的实际代价；h(n)是从节点n到目标节点Sg的最优路径的估计代价。

估价函数3.3.1启发式搜索策略和估价函数

为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。

f(n)——表示节点n的估价函数值。评价函数的格式：

f(n)=g(n)+h(n)

f(n)：评价函数

h(n)：启发函数3.3.1启发式搜索策略和估价函数

需要某些估算节点“希望”的量度，这种量度叫做评价函数(evalutionfunction)。启发式搜索算法在状态图一般搜索算法基础上，增加启发函数值的计算与传播过程。由启发函数值来确定节点的扩展顺序。3.3.1启发式搜索策略和估价函数算法的数据结构和符号约定

Open表：用于存放刚生成的节点。

Closed表：用于存放将要扩展的节点。

S：表示问题的初始状态。

G：表示搜索过程所得到的搜索图。

M：表示当前扩展节点新生成的且不为自己先辈的子节点集。3.3.2有序搜索实质

选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。对策树博弈概述:

博弈一向被认为是富有智能行为的游戏,因而很早就受到人工智能界的重视,早在60年代就已经出现若干博奕程序,并达到一定水平。博奕问题的研究还不断提出一些新的研究课题,从而推动了人工智能研究的发展。

博弈是研究使自己取胜、战胜对手的策略。在决策过程中要对形势做出恰当的估计，搜寻各种可能的策略组合，通过对比分析确定对自己最有利的策略。对策树博弈概述:

诸如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很多种，我们讨论最简单的“二人零和、全信息、非偶然”博弈，其特征如下：

(1)对垒的MAX、MIN双方轮流采取行动，博弈的结果只有三种情况：MAX方胜，MIN方败；MIN方胜，MAX方败；和局。

(2)在对垒过程中，任何一方都了解当前的格局及过去的历史。

(3)任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取对自已为最有利而对对方最为不利的对策，不存在掷骰子之类的“碰运气”因素。即双方都是很理智地决定自己的行动。

在博弈过程中，任何一方都希望自己取得胜利。因此，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动方案。此时，如果我们站在MAX方的立场上，则可供MAX方选择的若干行动方案之间是“或”关系，因为主动权掌握在MAX方手里，他或者选择这个行动方案，或者选择另一个行动方案，完全由MAX方自已决定。当MAX方选取任一方案走了一步后，MIN方也有若干个可供选择的行动方案，此时这些行动方案对MAX方来说它们之间则是“与”关系，因为这时主动权掌握在MIN方手里，这些可供选择的行动方案中的任何一个都可能被MIN方选中，MAX方必须应付每一种情况的发生。

这样，如果站在某一方(如MAX方，即MAX要取胜)，把上述博弈过程用图表示出来，则得到的是一棵“与/或树”。描述博弈过程的与/或树称为博弈树，它有如下特点：

(1)博弈的初始格局是初始节点。

(2)在博弈树中，“或”节点和“与”节点是逐层交替出现的。自己一方扩展的节点之间是“或”关系，对方扩展的节点之间是“与”关系。双方轮流地扩展节点。

(3)所有自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都认为是不可解节点。

我们假定MAX先走，处于奇数深度级的节点都对应下一步由MAX走，这些节点称为MAX节点，相应的偶数级为MIN节点。对策树估价函数E(X)E(X)以数值形式表示弈者在棋局X下获胜机会的大小。对于对策树结点比较少的的搏弈游戏，E(X)为：E(X)={1,-1|若X为胜局，E(X)=1，若X为负局，E(X)=-1}我们希望利用刚才所定义的这个估价函数来确定弈者A在棋局a下应走哪一着棋，即，将比赛导向b、c、d三种棋赛的哪一种棋局。设V（X）是棋局X的价值值，那末，所作的选择就应使其价值值为max{V（b），V（c），V（d）}。对于叶结点X，

V（X）取成E（X）。对于其余的结点，设d≥1是X的度，C1，C2，…，Cd是X的儿子们所表示的棋局，那末V（X）可表示为一般情况：V(X)=max{V(ci)} 若X是方形结点，1≤i≤d

min{V(ci)} 若X是圆形结点，1≤i≤d

估价函数的定义：

对节点n定义f*(n)=g*(n)+h*(n),表示从S开始约束通过节点n的一条最佳路径的代价。

希望估价函数f定义为：f(n)=g(n)+h(n)

——g是g*的估计，h是h*的估计3.3.3A*算法A*算法的定义：

定义1

在图搜索过程中，如果重排OPEN表是依据f(x)=g(x)+h(x)进行的，则称该过程为A算法。

定义2

在A算法中，如果对所有的x存在h(x)≤h*(x),则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。

定义3

采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。当h=0时，A*算法就变为有序搜索算法。

A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。

3.1图搜索策略3.2盲目搜索3.3启发式搜索第三章搜索推理技术3.4产生式系统

3.5不确定推理3.6非单调推理

定义：用来描述若干个不同的以一个基本概念为基础的系统。这个基本概念就是产生式规则或产生式条件和操作对的概念。3.4产生式系统实质：在产生式系统中，论域的知识分为两部分：用事实表示静态知识，如事物、事件和它们之间的关系；用产生式规则表示推理过程和行为。由于这类系统的知识库主要用于存储规则，因此又把此类系统称为基于规则的系统。2.4产生式表示法（ProductionSystem）2.4.1产生式的基本形式

产生式通常用于表示具有因果关系的知识，其基本形式是:P→Q或IFPTHENQ

其中，P是产生式的前提或条件，用于指出该产生式是否是可用的条件；Q是一组结论或动作，用于指出该产生式的前提条件P被满足时，应该得出的结论或应该执行的操作。P和Q都可以是一个或一组数学表达式或自然语言。2.4产生式表示法（ProductionSystem）2.4.2产生式表示知识方法确定性和不确定性规则知识的产生式表示。

确定性规则知识可用前面介绍的产生式的基本形式表示即可。不确定性规则知识用如下形式表示

P→Q

（可信度）或者IFPTHENQ

（可信度）其中，P是产生式的前提或条件，用于指出该产生式是否是可用的条件；Q是一组结论或动作，用于指出该产生式的前提条件P被满足时，应该得出的结论或应该执行的操作。2.4产生式表示法（ProductionSystem）2.4.2产生式表示知识方法产生式规则的例子

r6:IF动物有犬齿AND有爪AND眼盯前方

THEN该动物是食肉动物

其中，r6是该产生式的编号；“动物有犬齿AND有爪AND眼盯前方”是产生式的前提P；“该动物是食肉动物”是产生式的结论Q。

2.4.3产生式系统的组成产生式系统用于描述某领域内知识的产生式集合，是某领域知识（规则）的存储器。用来存放输入事实、外部数据库输入的事实以及中间结果和最后结果。由一组程序组成，用来控制协调规则库与数据库的运行，包含了推理方式和控制策略。规则库数据库推理机产生式系统：知识库＋推理机知识库：数据库＋规则库把一组产生式放在一起，让它们相互配合、协同作用。产生式系统一个产生式生成的结论就可以供另一个产生式作为前提使用。以这种方式问题求解的系统。

规则库：R1: IF有毛发OR产乳

THEN哺乳动物R2：IF哺乳动物AND有蹄

THEN偶蹄R3：IF偶蹄AND白色AND黑条纹

THEN斑马R4: IF哺乳动物AND食肉

THEN食肉动物R5：IF利爪AND利齿AND眼睛前视

THEN食肉动物R6：IF黑条纹AND食肉动物AND黄褐色

THEN老虎控制策略图产生式系统的主要组成总数据库产生式规则3.6.1产生式系统的组成选择规则到执行操作的步骤

1匹配

把当前数据库与规则的条件部分相匹配。

2冲突

当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决。3操作

操作就是执行规则的操作部分。推理过程

从规则库中取一条规则，将前件与当前动态数据库中的事实/数据进行模式匹配将规则后件放入当前动态数据库，或执行规则后件的动作匹配成功？NY正向推理：从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立。3.6.2产生式系统的推理逆向推理：从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后逐一验证这些假设。双向推理：双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。冲突消解策略

在推理过程中，匹配会出现三种情况已知事实可与知识库中的多个知识匹配成功；或者有多个（组）已知事实都可与知识库中某一知识匹配成功；或者有多个（组）已知事实可与知识库中的多个知识匹配成功已知事实恰好只与知识库中的一个知识匹配成功已知事实不能与知识库中的任何知识匹配成功出现冲突的情况逆向推理:

如果有多条产生式的后件都和同一假设匹配成功，或者有多条产生式后件可与多个假设匹配成功。正向推理:

如果有多条产生式规则的前件都和已知的事实匹配成功；或者有多组不同的已知事实都与同一条产生式规则的前件匹配成功；或者两种情况同时出现。1.按就近原则排序该策略把最近被使用过的规则赋予较高的优先级2.按已知事实的新鲜性排序后生成的事实比先生成的事实具有较大的优先性3.按匹配度排序根据匹配程度来决定哪一个产生式规则优先被应用冲突消解策略

4.按领域问题特点排序按照求解问题领域的特点将知识排成固定的次序5.按上下文限制排序根据当前数据库的已知事实与上下文的匹配情况确定6.按条件个数排序将条件少的规则赋予较高的优先级，优先被启用7.按规则的次序排序

以知识库中预先存入规则的排列顺序作为知识排序的依据冲突消解策略

例子初始事实：f1：某动物有毛发f2：食肉f3：黄褐色f4：有黑条纹f5：无蹄问题求解：该动物是什么？

规则库：R1: IF有毛发OR产乳

THEN哺乳动物R2： IF哺乳动物AND有蹄

THEN偶蹄R3： IF偶蹄AND白色AND黑条纹

THEN斑马R4: IF哺乳动物AND食肉

THEN食肉动物R5： IF利爪AND利齿AND眼睛前视

THEN食肉动物R6： IF黑条纹AND食肉动物AND黄褐色

THEN老虎解：数据库：{有毛发，食肉、黄褐色、黑条纹，无蹄}规则库：{R1,R2,R3,R4,R5,R6}待测试规则库：{}R1匹配成功，R2,R3匹配失败,R4,R5,R6无匹配冲突集：{R1}；待测试规则库：{R4,R5,R6}冲突消解，执行后件：将“哺乳动物”置入数据库：{有毛发，食肉、黄褐色、黑条纹，无蹄，哺乳动物}推理1：R4匹配成功，R5,R6无匹配冲突集：{R4}；待测试规则库：{R5,R6}冲突消解，执行后件：将“食肉动物”放入数据库：{有毛发，食肉、黄褐色、黑条纹，无蹄，哺乳动物,食肉动物}R5无匹配，R6匹配成功冲突集：{R5}；待测试规则库：{R6}冲突消解，执行后件：将后件“老虎”放入数据库：{有毛发，食肉、黄褐色、黑条纹，无蹄，哺乳动物,食肉动物,老虎}推理结束，“老虎”为问题求解推理2：推理3：3.1图搜索策略3.2盲目搜索3.3启发式搜索第三章搜索推理技术3.4产生式系统

3.5不确定推理

3.6非单调推理

3.5不确定性推理

什么是不确定推理

智能主要反映在求解不确定性问题的能力上。推理是人类的思维过程，它是从已知事实出发，通过运用相关的知识逐步推出某个结论的过程。其中已知事实和知识是构成推理的两个基本要素。已知事实（证据），用以指出推理的出发点及推理时应使用的知识；知识是推理得以向前推进，并逐步达到最终目标的依据。什么是不确定性推理?不确定性推理是建立在非经典逻辑上的一种推理,是对不确定性知识的运用与处理。是从不确定性的初始证据出发,通过运用不确定性的知识,最终推出具有一定程度的不确定性但却合理或者近乎合理的结论的思维过程。为什么要研究不确定性推理?日常生活中含有大量的不确定的信息。ES系统中大量的领域知识和专家经验，不可避免的包含各种不确定性。以模糊集理论为基础的方法以概率为基础的方法3.5.1关于证据的不确定性

不确定性推理是研究复杂系统不完全性和不确定性的有力工具。有两种不确定性，即关于证据的不确定性和关于结论的不确定性。3.5不确定性推理关于结论的不确定性也叫做规则的不确定性，它表示当规则的条件被完全满足时，产生某种结论的不确定程度。3.5.3多个规则支持同一事实时的不确定性

基于模糊集理论的方法基于概率论的方法3.5.2关于结论的不确定性纯概率方法虽然有严格的理论依据，但通常要求给出事件的先验概率和条件概率，而这些数据又不易获得，因此使其应用受到限制。为了解决这个问题，人们在概率论的基础上发展起来了一些新的方法和理论，主要有：可信度方法证据理论主观概率论(又称主观Bayes方法)等

(1)主观Bayes方法

(2)可信度方法

(3)证据理论PROSPECTOR专家系统中使用的不确定推理模型，是对Bayes公式修正后形成的一种不确定推理方法，为概率论在不确定推理中的应用提供了一条途径。它是MYCIN专家系统中使用的不确定推理模型，它以确定性理论为基础，方法简单、易用。它通过定义信任函数、似然函数，把知道和不知道区别开来。这些函数满足比概率函数的公理要弱的公理，因此，概率函数是信任函数的一个子集。所谓的专家系统实质上是某一专门知识，例如某种疾病的诊断、处方，某些矿物的资源勘探数据分析等的计算机咨询系统(软件)。专家系统的基础是专家知识。专家知识可以分成两大类，一类是已经总结在书本上的定律、定理和公式等，另一类是专家们在实际工作中长期积累的经验、教训。这后一类知识往往难以总结成书面的规律或条文，但这类知识却是十分宝贵的，它们在专家做出决策、指导工作和解决疑难问题等方面起着重要作用。

什么是专家系统：“专家系统”(ExpertSystem)是指具有相当于专家的知识和经验水平，以及解决专门问题能力的计算机系统，通常指计算机软件。主观Bayes方法1976年提出，应用于地矿勘探专家系统Prospector中不确定推理系统包括：不确定性的表示：规则/知识事实/证据不确定性的计算组合证据的不确定算法不确定性的传递算法结论的不确定算法规则不确定的表示

ifEthen(LS，LN)H(P(H))(1)E是规则的前提条件，H是结论，P(H)是H的先验概率，是指在没有任何证据的情况下结论H为真的概率。(2)LS是充分性度量：表示E对H的支持程度，取值范围[0,+),其定义为：

P(E/H)LS=------------------P(E/~H)规则不确定的表示(3)LN是必要性度量：表示~E对H的支持程度，取值范围[0,+),其定义为：

P(~E/H)1-P(E/H)LN=----------------=-------------------P(~E/~H)1-P(E/~H)不确定性的传递算法

主观Bayes方法推理的任务就是根据证据E的概率P(E)和LS，LN的值，把H的先验概率P(H)更新为P(H/E)或P(H/~E)。分下面三种情况：证据肯定存在证据肯定不存在证据不确定

MYCIN系统研制发起人E．H．Shortiffe(爱德华持·肖持利夫)是哈佛大学数学系毕业生，他获得了斯坦福大学面向医学的计算机应用方面的奖学金，到斯坦福大学当研究生。他在计算机科学和医学之间的边缘领域一一医疗诊断的研究中，进行了开创性的工作。当他在一九七一年完成MYCIN系统时，他只是一名研究生，到了一九七九年成为斯坦福大学的内科副教授。一九八零年召开第二届医疗中的人工智能(AIM)学术会议时，他成为大会的组织委员会主席。

MYCIN是有关传染病诊断和治疗的咨询系统。它能教会不擅长诊治传染病的医生，怎样从患者症状出发，确定病的种类及相应的治疗方法。我们知道，传染病种类繁多，与其相应的抗生素种类也不少。要在限定的时间内确定病症，选择出恰当的治疗方法，决非易事。这似乎就是开发MYCIN系统的着眼点。

MYCIN系统存放有大量传染病专家长期积累的知识，它们是肖特利夫与许多著名的传染病专家交谈，推理和总结得到的。他把这些知识归纳成200多条规则(后扩充至500多条)存放在计算机中，这些规则具有“如果…那么…”这种形式，称为产生式规则。这是目前专家系统使用得最广泛的推理方式之一。当使用MYCIN进行医疗诊断时，医生通过计算机的人机交互接口，将病人数据送入计算机，MYCIN系统将外来数据不断与内部知识进行匹配，直到获得最终结果。

产生式规则：

IfEThenH(CF(H,E))CF(H,E)是该条知识的可信度，称为可信度因子或规则强度，表示当前提条件E所对应的证据为真时，它对结论H为真的支持程度。CF是根据经验对一个事物或现象为真的可信程度的度量CF(H,E)取值为：[-1,1]可信度方法模型知识的不确定性表示CF定义：

CF(H,E)=MB(H,E)-MD(H,E)MB:信任增长度，它表示因与前提条件E匹配的证据的出现，使结论H为真的信任增长度MD：不信任增长度，它表示因与前提条件E匹配的证据的出现，对结论H的不信任增长度知识的不确定性表示MB的定义：由条件概率和先验概率定义

1若P（H）=1MB(H,E)=max{P(H|E),P(H)}–P(H)-----------------------------------否则1-P(H)MD的定义：1若P（H）=0MD(H,E)=min{P(H|E),P(H)}–P(H)-----------------------------------否则-P(H)知识的不确定性表示MB(H,E)和MD(H,E)是互斥的：即一个证据不能既增加对H的信任度，又不能同时增加对H的不信任度当MB(H,E)>0,MD(H,E)=0

当MD(H,E)>0,MB(H,E)=0知识的不确定性表示CF(H,E)的直观意义：(1)CF(H,E)>0,则P(H|E)>P(H):E的出现增加了H为真的概率，增加了H为真的可信度(2)CF(H,E)<0,则P(H|E)<P(H):E的出现减少了H为真的概率，增加了H为假的可信度(3)CF(H,E)=0,则P(H|E)=P(H):表示H与E独立，即E的出现对H没有影响知识的不确定性表示CF(H,E)几个特殊的值：(1)前提真，则结论必真，即P(H|E)=1,有CF(H,E)=1(2)前提真，而结论必假，即P(H|E)=0,有CF(H,E)=-1(3)前提与结论无关，即P(H|E)=P(H),有CF(H,E)=0证据的不确定性表示证据的不确定性也用CF来表示CF值的来源分两种情况：初始证据：由提供证据的用户给出以前的结论作为新证据：由传递算法推出证据的CF取值范围：[-1，1]E肯定为真时：CF(E)=1E肯定为假时：CF(E)=-1对E一无所知时：CF(E)=0CF(E)>0表示E以CF(E)为真CF(E)<0表示E以CF(E)为假组合证据不确定性算法(1)E=E1

E2

…En

如果已知CF(E1),…,CF(En),则：

CF(E)=min{CF(E1),…,CF(En)}(2)E=E1

E2

…

En

如果已知CF(E1),…,CF(En),则：

CF(E)=max{CF(E1),…,CF(En)}不确定性的传递算法已知：CF(E)EHCF(H,E)

则规定：CF(H)=CF(H,E)max{0,CF(E)}规定：CF(~E)=-CF(E)当证据为假时：CF(H)=0，即该模型没有考虑证据为假时对H所产生的影响当证据为真时，CF(H,E)实际上就是结论H的可信度CF(H)结论不确定性合成算法r1:ifE1thenH(CF(H,E1))r2:ifE2thenH(CF(H,E2))求合成的CF(H)(1)首先对每条知识求出CF(H)，即：

CF1(H)=CF(H,E1)max{0,CF(E1)}CF2(H)=CF(H,E2)max{0,CF(E2)}(2)规定：

CF1(H)+CF2(H)-CF1(H)CF2(H)CF1(H)>=0,CF2(H)>=0CF(H)=CF1(H)+CF2(H)+CF1(H)CF2(H)CF1(H)<0,CF2(H)<0CF1(H)+CF2(H)其他证据理论主要内容：概率分配函数信任函数似然函数证据的不确定性度量规则的不确定性度量推理计算基于概率的方法没有把事物自身所具有的模糊性反映出来。Zadeh提出模糊集理论。概率论处理的是由随机性引起的不确定性，可能性理论处理的是由模糊性引起的不确定性。信号可以分为确知信号和随机信号两大类。每次观测所得结果都相同，都是时间t的一个确定的函数，具有确定的变化规律。每次观测所得结果都不同，都是时间t的不同函数，观测前又不能预知观测结果，没有确定的变化规律。在一定条件下必然发生的现象称为确定性现象。

“太阳不会从西边升起”。确定性现象

“同性电荷必然互斥”。“水从高处流向低处”。实例自然界所观察到的现象:确定性现象随机现象在一定条件下可能出现也可能不出现的现象称为随机现象。实例1

“在相同条件下掷一枚均匀的硬币，观察正反两面出现的情况”。随机现象“函数在间断点处不存在导数”等。结果有可能出现正面也可能出现反面。确定性现象的特征

条件完全决定结果结果有可能为:“1”,“2”,“3”,“4”,“5”或“6”.

实例3

“抛掷一枚骰子，观察出现的点数”.

实例2

“用同一门炮向同一目标发射同一种炮弹多发,观察弹落点的情况”。结果:“弹落点会各不相同”。实例4

“从一批含有正品和次品的产品中任意抽取一个产品”。其结果可能为:

正品

、次品。实例5

“过马路交叉口时,可能遇上各种颜色的交通指挥灯”。实例6“一只灯泡的寿命”可长可短。随机现象的分类个别随机现象：原则上不能在相同条件下重复出现。大量性随机现象：在相同条件下可以重复出现。随机现象的特征条件不能完全决定结果2.随机现象在一次观察中出现什么结果具有偶然性,但在大量重复试验或观察中,这种结果的出现具有一定的统计规律性。随机现象是通过随机试验来研究的。问题什么是随机试验?如何来研究随机现象?说明1.随机现象揭示了条件和结果之间的非确定性联系

,其数量关系无法用函数加以描述。概率论的基本术语

随机试验

满足下列三个条件的试验称为随机试验：

(1)在相同条件下可重复进行；

(2)试验的结果不止一个，所有可能的结果能事先明确；

(3)每次试验前不能确定会出现哪一个结果。例：投掷硬币

随机事件

在随机试验中，对试验中可能出现也可能不出现、而在大量重复试验中却具有某种规律性的事情，称为随机事件，简称为事件，如投掷硬币出现正面就是一个随机事件。

概率论的基本术语

样本空间Ω——随机试验所有可能的结果组成的集合。样本点

——Ω中的元素。随机事件——样本空间Ω的子集合，称为事件。基本事件——Ω中每个样本点所构成的单点集。必然事件——Ω本身。不可能事件——不包含任何元素的空集合Φ。

基本事件

随机试验中最简单的随机事件称为基本事件，如投掷骰子出现1、2、.....、6点是基本事件，出现偶数点是随机事件，但不是基本事件。样本空间

随机试验的所有基本事件组成的集合称为样本空间，如投掷骰子的样本空间为{1,2,3,4,5,6}。频数和频率

在相同条件下的n次重复试验中，事件A发生的次数nA称为事件A的频数，比值称为事件A发生的频率。频率反映了事件A发生的频繁程度，若事件A发生的可能性大，那么相应的频率也大，反之则较小。概率随