,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,西安电子科技大学,西安电子科技大学,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,Artificial Intelligence(AI),人工智能,第三章：确定性推理,Artificial Intelligence(AI)人,内容提要,第三章：确定性推理,1.,推理的基本概念,2.,搜索策略,3.,自然演绎推理,4.,归结演绎推理,5.,基于规则的演绎推理,内容提要第三章：确定性推理1.推理的基本概念2.搜索策略3.,内容提要,第三章：确定性推理,1.,推理的基本概念,2.,搜索策略,3.,自然演绎推理,4.,归结演绎推理,5.,基于规则的演绎推理,内容提要第三章：确定性推理1.推理的基本概念2.搜索策略3.,推理的基本概念,推理的基本概念,1.,什么是推理,2.,推理方法及其分类,3.,推理的控制策略及其分类,推理的基本概念推理的基本概念,推理的基本概念,什么是推理,所谓推理就是按某种策略由已知判断推出另一个判断的思维过程。,在人工智能中，推理是由程序实现的，称为推理机。,推理的两个基本问题,推理的方法,推理的控制策略,推理的基本概念什么是推理,推理的基本概念,推理方法及其分类,1.,按推理的逻辑基础分：,演绎，归纳，类比归纳推理,演绎推理,:,从已知的一般性知识出发，推出蕴含在已知知识中的适合于某种个别情况的结论。是一种由一般到个别的推理方法，其,核心是三段论,。,假言三段论：,AB,，,BC AC,常用的三段论是由一个,大前提,、,一个小前提,和,一个结论,这三部分组成的。,大前提是已知的一般性知识或推理过程得到的判断；,小前提是关于某种具体情况或某个具体实例的判断；,结论是由大前提推出的，并且适合于小前提的判断。,其结论是蕴含在前提中的,推理的基本概念推理方法及其分类,推理的基本概念,推理方法及其分类,1.,按推理的逻辑基础分：,演绎，归纳，类比归纳推理,归纳推理：,按照所选事例的,广泛性,可分为,完全归纳推理,和,不完全归纳推理,。,完全归纳推理：,是指在进行归纳时需要考察相应事物的,全部对象,，并根据这些对象是否都具有某种属性，推出该类事物是否具有此属性。,不完全归纳推理：,是指在进行归纳时只考察了相应事物的,部分对象,，就得出了关于该事物的结论。,推理的基本概念推理方法及其分类,推理的基本概念,推理方法及其分类,1.,按推理的逻辑基础分：,演绎，归纳，类比归纳推理,类比归纳推理：,若在两个或两类事物有许多属性相同或相似，则推出它们在其他属性上也相同或相似。,类比归纳推理的基础是,相似原理,，其可靠程度取决于两个或两类事物的相似程度以及这两个或两类事物的相同属性与推出的那个属性之间的相关程度。,推理的基本概念推理方法及其分类,推理的基本概念,推理方法及其分类,1.,按推理的逻辑基础分：,演绎，归纳，类比归纳推理,演绎推理与归纳推理的区别：,演绎推理是在已知领域内的一般性知识的前提下，通过演绎求解一个具体问题或者证明一个结论的正确性。,它所得出的结论实际上早已蕴含在一般性知识的前提中,，演绎推理只不过是将已有事实揭露出来，因此,它不能增殖新知识,。,归纳推理所推出的结论是没有包含在前提内容中的,。这种由个别事物或现象推出一般性知识的过程，,是增殖新知识的过程,。,推理的基本概念推理方法及其分类,推理的基本概念,推理方法及其分类,2.,按推理过程所用知识的确定性分,确定性推理,不确定性推理,3.,按推理过程推出的结论是否单调增加分,单调推理,非单调推理,4.,按推理过程是否利用问题的启发性知识分,启发式推理,非启发式推理,推理的基本概念推理方法及其分类,推理的基本概念,推理的控制策略及其分类,推理过程不仅依赖于所用的推理方法，同时也依赖于推理的控制策略。,推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略,。,推理的控制策略可分为：,搜索策略,推理策略,推理的基本概念推理的控制策略及其分类,推理的基本概念,推理的控制策略及其分类,搜索策略：,在知识库中寻找可利用的知识，从而构造一条,代价较小,的推理路线。主要解决推理线路、推理效果、推理效率等问题。,按是否使用启发式信息可分为：,盲目搜索,启发式搜索,按问题的表示方式可分为：,状态空间搜索,与或树搜索,推理的基本概念推理的控制策略及其分类,推理的基本概念,推理的控制策略及其分类,推理策略：,包括推理方向控制策略、求解策略、限制策略、冲突消解策略等,推理方向控制策略：,用于确定推理的控制方向，可分为,正向推理,逆向推理,混合推理,双向推理,推理的基本概念推理的控制策略及其分类,推理的基本概念,推理的控制策略及其分类,推理方向控制策略：,正向推理：,从已知事实出发、正向使用推理规则，亦称为数据驱动推理或前向链推理。,正向推理从用户提供的,初始已知事实,出发，在,知识库,KB,中找出当前可适用的知识，构成可适用的,知识集,KS,；,然后按,某种冲突消解策略,从,KS,中选出一条知识进行推理，并将推出的,新事实,加入到数据库,DB,中，作为下一步推理的已知事实；,在此之后，再在知识库中选取可适用的知识进行推理。如此重复进行这一过程，直到求得所要求的解。,推理的基本概念推理的控制策略及其分类,推理的基本概念,推理的控制策略及其分类,推理方向控制策略：,正向推理中，如何根据已知事实到知识库中选取可用知识？当知识库中有多条知识可用时应该先使用那一条知识？这些问题涉及到了,知识的匹配方法,和,冲突消解策略。,正向推理的优点：,比较直观，允许用户主动提供有用的事实信息，适合于诊断、设计、预测、监控等领域的问题求解。,正向推理的缺点：,推理无明确目标，求解问题是可能会执行许多与解无关的操作，导致推理效率较低。,推理的基本概念推理的控制策略及其分类,推理的基本概念,推理的控制策略及其分类,推理方向控制策略：,逆向推理：,从某个假设目标出发，逆向使用规则，亦称为,目标驱动推理,或,逆向链推理,。,逆向推理首先选定一个假设目标，然后寻找支持该假设的证据，若所需的证据都能找到，则说明原假设是成立的；若找不到所需要的证据，则说明原假设不成立，此时需要另作新的假设。,推理的基本概念推理的控制策略及其分类,推理的基本概念,推理的控制策略及其分类,推理方向控制策略：,逆向推理的主要优点：,不必寻找和使用那些与假设目标无关的信息和知识，推理过程的目标明确，有利于向用户提供解释，在诊断性专家系统中较为有效。,逆向推理的主要缺点：,当用户对解的情况认识不请时，由系统自主选择假设目标的盲目性比较大，若选择不好，可能需要多次提出假设，会影响系统效率。,推理的基本概念推理的控制策略及其分类,推理的基本概念,推理的控制策略及其分类,推理方向控制策略：,混合推理：,把正向推理和逆向推理结合起来所进行的推理称为混合推理。是一种解决较复杂问题的方法。,混合推理方法的三种类型：,1.,先正向后逆向：,这种方法先进行正向推理，从已知事实出发推出部分结果，然后再用逆向推理对这些结果进行证实或提高它们的可信度。,推理的基本概念推理的控制策略及其分类,推理的基本概念,推理的控制策略及其分类,推理方向控制策略：,混合推理方法的三种类型：,2.,先逆向后正向：,这种方法先进行逆向推理，从假设目标出发推出一些中间假设，然后再用正向推理对这些中间假设进行证实。,3.,双向混合：,是指正向推理和逆向推理同时进行，使推理过程在中间的某一步结合起来。,推理的基本概念推理的控制策略及其分类,推理的基本概念,推理的控制策略及其分类,推理策略：,包括推理方向控制策略、求解策略、限制策略、冲突消解策略等,求解策略：,是指仅求一个解，还是求所有解或最优解等。,限制策略：,是指对推理的深度、宽度、时间、空间等进行的限制。,冲突消解策略：,是指当推理过程有多条知识可用时，如何从这多条可用知识中选出一条最佳知识用于推理的策略。,推理的基本概念推理的控制策略及其分类,内容提要,第三章：确定性推理,1.,推理的基本概念,2.,搜索策略,3.,自然演绎推理,4.,归结演绎推理,5.,基于规则的演绎推理,内容提要第三章：确定性推理1.推理的基本概念2.搜索策略3.,搜索策略,搜索策略,搜索的基本概念,状态空间的搜索策略,与,/,或树的搜索策略,搜索的完备性与效率,搜索策略搜索策略,搜索的基本概念,搜索的基本概念,搜索是人工智能中的一个基本问题，并与推理密切相关，搜索策略的优劣，将直接影响到智能系统的性能与推理效率。,搜索的定义：,依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索。,搜索的适用情况：,不良结构或非结构化问题；难以获得求解所需的全部信息；更没有现成的算法可供求解使用。,搜索的基本概念搜索的基本概念,搜索的基本概念,搜索的类型,按是否使用启发式信息：,盲目搜索：,按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。,启发式搜索：,在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。,按问题的表示方式：,状态空间搜索：,用状态空间法求解问题进行的搜索,与或树搜索：,用问题归约法求解问题进行的搜索,搜索的基本概念搜索的类型,状态空间的搜索策略,状态空间的搜索策略,状态空间搜索的基本思想,图搜索的一般过程,状态空间的盲目搜索,广度优先搜索,深度优先搜索,代价树搜索,状态空间的启发式搜索,启发性信息和估价函数,A,算法和,A*,算法,状态空间的搜索策略状态空间的搜索策略,状态空间的搜索策略,状态空间搜索的基本思想,先把问题的初始状态作为当前,扩展节点,对其进行,扩展,，生成一组子节点。,然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没出现，则再,按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点,。,重复上述过程，直到目标状态出现在子节点中或者没有可供操作的节点为止。,所谓对一个节点进行,“,扩展,”,是指对该节点用某个可用操作进行作用，生成该节点的一组子节点,。,状态空间的搜索策略状态空间搜索的基本思想,状态空间的搜索策略,状态空间搜索算法的数据结构和符号约定,OPEN,表：,未扩展节点表，用于存放刚生成节点,CLOSED,表：,已扩展节点表，用于存放已经扩展或将要扩展节点的,S,：,用表示问题的初始状态,G,：,表示搜索过程所得到的搜索图,M,：,表示当前扩展节点新生成的且不为自己先辈的子节点集,状态空间的搜索策略状态空间搜索算法的数据结构和符号约定,状态空间的搜索策略,图搜索的一般过程,(1),把初始节点,S,放入未扩展节点表,OPEN,表，并建立目前仅包含,S,的图,G,；,(2),检查,OPEN,表是否为空，若为空，则问题无解，失败退出；,(3),把,OPEN,表的,第一个节点,取出放入已扩展节点表,CLOSED,表，并记该节点为节点,n,；,(4),考察节点,n,是否为目标节点。若是则得到了问题的解，成功退出。此时的解为追踪图,G,中沿着指针,（步骤,6,中设置的指针）,从,n,到初始节点,S,的路径。,状态空间的搜索策略图搜索的一般过程,状态空间的搜索策略,图搜索的一般过程,(5),扩展节点,n,，生成一组子节点。把这些子节点中,不是节点,n,先辈,的那部分子节点记入集合,M,，并把这些子节点作为节点,n,的子节点加入,G,中,(6),针对,M,中子节点的不同情况，分别作如下处理：,对那些没有在,G,中出现过的,M,成员