人工智能ArtificialIntelligence.ppt
人工智能Artificial Intelligence第三章,史忠植 中国科学院计算技术研究所,自动推理Automated Reasoning,2023/6/13,史忠植 人工智能：自动推理,1,2023/6/13,史忠植 人工智能：自动推理,2,内容提要,3.1 概述3.2 三段论推理3.3 盲目搜索3.4 回溯策略3.5 启发式搜索3.6 与或图启发式搜索3.7 博弈搜索3.8 归结演绎推理3.9 产生式系统3.10 自然演绎推理3.11 非单调推理3.12 小结,自动推理是人工智能的核心内容之一，是专家系统、程序推导、程序正确性证明、智能机器人等研究领域的重要基础。自动推理早期的工作主要集中在机器定理证明。1930年希尔伯特（Herbrand）为定理证明建立了一种重要方法，他的方法奠定了机械定理证明的基础。机械定理证明的主要突破是1965年由鲁宾逊做出的，他建立了所谓归结原理，使机械定理证明达到了应用阶段。在本章，首先讨论三段论推理和搜索策略，然后讨论归结演绎推理、产生式系统，最后讨论非单调推理。,自动推理,2023/6/13,3,史忠植 人工智能：自动推理,2023/6/13,史忠植 人工智能：自动推理,4,内容提要,3.1 概述3.2 三段论推理3.3 盲目搜索3.4 回溯策略3.5 启发式搜索3.6 与或图启发式搜索3.7 博弈搜索3.8 归结演绎推理3.9 产生式系统3.10 自然演绎推理3.11 非单调推理3.12 小结,三段论是一种常用的推理形式，它由三个性质命题组成，其中两个性质命题是前提，另一个性质命题是结论。例如 科学是不断发展的；(大前提)智能科学是科学：(小前提)所以，智能科学是不断发展的。(结论)这就是一个三段论。前两个性质判断包含着一个共同项“科学”，由这两个具有同项的判断推出一个新的性质判断：智能科学是不断发展的。,三段论,2023/6/13,5,史忠植 人工智能：自动推理,其中，结论中的主项叫做小项，用“S”表示，如上例中的“智能科学；结论中的谓项叫做大项，用“P”表示，如上例中的“不断发展的；两个前提中共有的项叫做中项，用“M”表示，如上例中的“科学。在三段论中，含有大项的前提叫大前提，如上例中的“科学是不断发展的”；含有小项的前提叫小前提，如上例中的“智能科学是科学。,三段论,2023/6/13,6,史忠植 人工智能：自动推理,三段论的公理,三段论的公理是三段论推理的基本依据。三段论的公理是客观事物的最一般、最普遍的关系在人们思维中的反映，是在人类长期反复实践中被总结出来的，并不断被实践所证明的，具有不证自明性。三段论的公理内容：对一类事物的全部有所断定（肯定或否定），则对该类事物的部分也就有所断定（肯定或否定）。三段论的公理用图表示如下：,2023/6/13,7,史忠植 人工智能：自动推理,图1,图2,三段论的公理,在图1中，M类全部包含在P类中（所有M是P），S类是M类的一部分（所有S是M），可见，S类的全部必然包含在P类中的。在图2中，M类全部与P类相排斥（所有M不是P），S类是M类的一部分（所有S是M），可见，S类的全部必然与P类相排斥。,2023/6/13,8,史忠植 人工智能：自动推理,三段论的格,三段论的格就是根据中项在三段论中的不同位置所构成的不同形式的三段论。在三段论的第一格中，中项是大前提的主项、小前提的谓项；在第二格中，中项是大、小前提的谓项；在第三格中，中项是大、小前提的主项；在第四格中，中项是大前提的谓项、小前提的主项。三段论的四个格可以分别表示如下：第一格 第二格 第三格 第四格 MP PM MP PM SM SM MS MS SP SP SP SP,2023/6/13,9,史忠植 人工智能：自动推理,构成三段论推理的三个性质命题，在质和量上的不同，就形成了三段论的不同形式，这些不同的形式叫做三段论的式。三段论总是由质和量不同的A（全称肯定命题）、E（全称否定命题）、I（特称肯定命题）、O（特称否定命题）四种命题组合而成，任何一个三段论推理都表现为一定的格和式。A、E、I、O都可以作为大前提、小前提和结论，其排列组合数目是：444=64。这样，每个格都有64式，四个格共有644=256式。但大多数是违反三段论规则的，是错误的式或无效式。,三段论的式,2023/6/13,10,史忠植 人工智能：自动推理,根据三段论推理的规则，就可以确定出各个格的正确式。四个格总共有256个式，其中只有24式是正确的式。各格正确式如下：第一格：AAA，（AAI），EAE，（EAO），AII，EIO。第二格：AEE，（AEO），EAE，（EAO），AOO，EIO。第三格：AAI，EAO，AII，EIO，IAI，OAO。第四格：AAI，AEE，（AEO），IAI，EAO，EIO。上面的各个式中，凡带有括号的式叫做“弱式”，共有五个弱式。弱式就是指可推出全称结论但只推出一个特称结论的式。如第一格中AII式。我们知道，在第一格中，从AA这两个前提可以推出全称结论A，但得出AAI式却是一个特称结论，因而这个式就是弱式。例如：所有的植物都是生物；（A）所有的玫瑰花都是植物；（A）所以，有的玫瑰花是生物。（I）,三段论的式,2023/6/13,11,史忠植 人工智能：自动推理,2023/6/13,史忠植 人工智能：自动推理,12,内容提要,3.1 概述3.2 三段论推理3.3 盲目搜索3.4 回溯策略3.5 启发式搜索3.6 与或图启发式搜索3.7 博弈搜索3.8 归结演绎推理3.9 产生式系统3.10 自然演绎推理3.11 非单调推理3.12 小结,问题求解,AI中每个研究领域都有其各自的特点和规律,但就求解问题的过程看,都可抽象为一个问题求解过程。问题求解过程实际上是一个搜索,广义地说,它包含了全部计算机科学。任何问题求解技术都包括两个重要的方面:表示和搜索表示是基本的,搜索必须要在表示的基础上进行。表示关系到搜索的效率。本章讨论的表示主要包括:状态空间表示问题空间表示,2023/6/13,史忠植 人工智能：自动推理,13,搜 索,1974年，Nilsson归纳出的AI研究的基本问题知识的模型化和表示常识性推理、演绎和问题解决启发式搜索人工智能系统和语言搜索是人工智能中的一个基本问题,是推理不可分割的一部分,直接关系到智能系统的性能和运行效率AI为什么要研究search?问题没有直接的解法;需要探索地求解;,2023/6/13,史忠植 人工智能：自动推理,14,什么是搜索,根据问题的实际情况不断寻找可利用的知识,构造出一条代价较少的推理路线,使问题得到圆满解决的过程称为搜索包括两个方面：找到从初始事实到问题最终答案的一条推理路径 找到的这条路径在时间和空间上复杂度最小,2023/6/13,史忠植 人工智能：自动推理,15,搜索策略,盲目搜索:也称为无信息搜索，即只按预定的控制策略进行搜索,在搜索过程中获得的中间信息不用来改进控制策略启发式搜索:在搜索中加入了与问题有关的启发性信息,用于指导搜索朝着最有希望的方向进行,加速问题的求解过程并找到最优解,2023/6/13,史忠植 人工智能：自动推理,16,搜索策略,一般搜索策略可以通过下面4个准则来评价：（1）完备性：如果存在一个解答，该策略是否保证能够找到？（2）时间复杂性：需要多长时间可以找到解答？（3）空间复杂性：执行搜索需要多大存储空间？（4）最优性：如果存在不同的几个解答，该策略可以发现是否最高质量的解答？,2023/6/13,史忠植 人工智能：自动推理,17,盲目搜索,盲目搜索一般是按预定的搜索策略进行搜索。由于这种搜索总是按预定的路线进行，没有考虑到问题本身的特性，所以这种搜索具有很大的盲目性，效率不高，不便于复杂问题的求解。深度优先搜索宽度优先搜索迭代加深搜索,2023/6/13,史忠植 人工智能：自动推理,18,19,深度优先搜索(Dephth-first),深度优先搜索生成节点并与目标节点进行比较是沿着树的最大深度方向进行的，只有当上次访问的节点不是目标节点，而且没有其他节点可以生成的时候，才转到上次访问节点的父节点。转移到父节点后，该算法会搜索父节点的其它的子节点。防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度深度界限。,2023/6/13,史忠植 人工智能：自动推理,20,深度优先搜索示意图,S,L,O,M,F,P,Q,N,F,F,F,2023/6/13,史忠植 人工智能：自动推理,21,深度优先算法框图,2023/6/13,史忠植 人工智能：自动推理,22,有界深度(4)优先的八数码问题深度优先搜索树,（初始状态）,深度优先搜索树,2023/6/13,史忠植 人工智能：自动推理,23,八数码有界深度优先搜索树,2023/6/13,史忠植 人工智能：自动推理,(1)把初始节点S0放入OPEN表(2)如果OPEN表为空,则问题无解,退出(3)把OPEN表的第一个节点(记为节点n)取出,放入CLOSED表(4)考查节点n是否为目标节点.若是,则求得了问题的解,退出(5)若节点n不可扩展,则转第(2)步(6)扩展节点n,将其子节点放入OPEN表的首部,并为每一个子节点都配置指向父节点的指针,转第(2)步,深度优先搜索过程,2023/6/13,史忠植 人工智能：自动推理,24,25,S,L,O,M,F,P,Q,N,F,F,F,宽度优先搜索示意图,2023/6/13,史忠植 人工智能：自动推理,26,（1）把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。（2）如果OPEN是个空表，则没有解，失败退出；否则继续。（3）把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。（4）扩展节点n。如果没有后继节点，则转向上述第(2)步。（5）把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。（6）如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。,宽度优先搜索算法,2023/6/13,史忠植 人工智能：自动推理,27,宽度优先算法框图,2023/6/13,史忠植 人工智能：自动推理,28,八数码难题（8-puzzle problem）,（初始状态）,规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展26个节点，共生成46个节点之后才求得解（目标节点）。,宽度优先算法例子,2023/6/13,史忠植 人工智能：自动推理,29,八数码宽度优先搜索树,2023/6/13,史忠植 人工智能：自动推理,迭代加深搜索,对于有界深度搜索策略，有下面几点需要说明：1）在有界深度搜索算法中，深度限制dm是一个很重要的参数。2）深度限制dm不能太大。3）有界深度搜索的主要问题是深度限制值dm的选取。问题：但是对很多问题，我们并不知道该值到底为多少，直到该问题求解完成了，才可以确定出深度限制dm。,2023/6/13,史忠植 人工智能：自动推理,30,迭代加深搜索,改进方法-迭代加深搜索算法 先任意给定一个较小的数作为dm，然后按有界深度算法搜索，若在此深度限制内找到了解，则算法结束；如在此限度内没有找到问题的解，则增大深度限制dm，继续搜索。迭代加深搜索是一种回避选择最优深度限制问题的策略，它是试图尝试所有可能的深度限制：首先深度为0，然后深度为1，然后为2，等等，一直进行下去。问题迭代加深搜索看起来会很浪费，因为很多节点都要扩展多次。,2023/6/13,史忠植 人工智能：自动推理,31,2023/6/13,史忠植 人工智能：自动推理,32,内容提要,3.1 概述3.2 三段论推理3.3 盲目搜索3.4 回溯策略3.5 启发式搜索3.6 与或图启发式搜索3.7 博弈搜索3.8 归结演绎推理3.9 产生式系统3.10 自然演绎推理3.11 非单调推理3.12 小结,2023/6/13,史忠植 人工智能：自动推理,33,回溯算法,有些问题需要彻底的搜索才能解决问题，然而，彻底的搜索要以大量的运算时间为代价，对于这种情况可以通过回溯法来去掉一些分枝，从而大大减少搜索的次数。八皇后问题迷宫问题深度优先周游树或图,四皇后问题中隐含的状态树,四皇后问题,2023/6/13,史忠植 人工智能：自动推理,34,2023/6/13,史忠植 人工智能：自动推理,35,四皇后问题树,回溯算法,2023/6/13,史忠植 人工智能：自动推理,36,Assignment=(var1=v11),回溯算法,2023/6/13,史忠植 人工智能：自动推理,37,Assignment=(var1=v11),(var2=v21),回溯算法,2023/6/13,史忠植 人工智能：自动推理,38,Assignment=(var1=v11),(var2=v21),(var3=v31),回溯算法,2023/6/13,史忠植 人工智能：自动推理,39,Assignment=(var1=v11),(var2=v21),(var3=v32),回溯算法,2023/6/13,史忠植 人工智能：自动推理,40,Assignment=(var1=v11),(var2=v22),回溯算法,2023/6/13,史忠植 人工智能：自动推理,41,Assignment=(var1=v11),(var2=v22),(var3=v31),回溯算法,2023/6/13,史忠植 人工智能：自动推理,42,2023/6/13,史忠植 人工智能：自动推理,43,递归回溯算法,Recursive procedure BACKTRACK(DATA)1.if TERM(DATA),return NIL;/*TERM是一个谓词，对满足产生式系统结束条件变量来说取值为真。在成功结束时，返回空表N1L。*/2.if DEADEND(DATA),retulrn FAIL;/*DEADEND是一个谓词，对已经知道不在一条解路上的自变量来说取值为真。在这种情况下，过程返回符号FAIL。*/3.RULESAPPRULUES(DATA);/*APPRULUES是一个函数，它计算可应用于其自变量的规则并排列这些规则(任意排列或者按照启发式准则排列)。*/4.LOOP:if NULL(RULES),return FAIL;/*如果不再有可应用的规则，那么过程失败。*/5.RFIRST(RULES);/*选出最好的一条可应用规则。*/,2023/6/13,史忠植 人工智能：自动推理,44,递归回溯算法,6.RULESTAIL(RULES);/*删去刚才选用的一条规则，缩小可应用的规则表。*/7.RDATAR(DATA);/*应用规则R产生一个新的数据库。*/8.PATHBACKTRACK(RDATA);/*在新数据库上递归调用BACKTRACK。*/9.if PATH=FAIL,go LOOP;/*若递归调用失败，则试另一条规则。*/10.return CONS(R,PATH);/*否则，通过把R加到表的前面，向上走一遍成功的规则表。*/,2023/6/13,史忠植 人工智能：自动推理,45,内容提要,3.1 概述3.2 三段论推理3.3 盲目搜索3.4 回溯策略3.5 启发式搜索3.6 与或图启发式搜索3.7 博弈搜索3.8 归结演绎推理3.9 产生式系统3.10 自然演绎推理3.11 非单调推理3.12 小结,启发式搜索,前面讨论的方法都是盲目的搜索方法,即都没有利用问题本身的特性信息,在决定要被扩展的节点时,都没有考虑该节点在解的路径上的可能性有多大,它是否有利于问题求解以及求出的解是否为最优启发式搜索要用到问题自身的某些特性信息,以指导搜索朝着最有希望的方向前进启发信息的强度强：降低搜索工作量，但可能导致找不到最优解弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解,2023/6/13,史忠植 人工智能：自动推理,46,启发式搜索,启发性信息和估价函数用于指导搜索过程,且与具体问题有关的控制性信息称为为启发性信息用于评价节点重要性的函数称为估价函数.记为 f(x)=g(x)+h(x)g(x)为从初始节点S0到节点x已经实际付出的代价h(x)是从节点x到目标节点Sg的最优路径的估价代价,体现了问题的启发性信息,称为启发函数f(x)表示从初始节点经过节点x到达目标节点的最优路径的代价估价值,其作用是用来评估OPEN表中各节点的重要性,决定其次序,2023/6/13,史忠植 人工智能：自动推理,47,启发式搜索,例：八数码问题，评价函数f(n)=d(n)+W(n)d(n):节点n的深度;W(n):与目标相比,错位的数字数目;,初始状态,目标状态,2023/6/13,史忠植 人工智能：自动推理,48,八数码启发式搜索,2023/6/13,史忠植 人工智能：自动推理,49,启发式搜索,启发式就是要猜测：从节点n开始，找到最优解的可能性有多大？从起始节点开始，经过节点n，到达目标节点的最佳路径的费用是多少？gh,2023/6/13,史忠植 人工智能：自动推理,50,局部择优搜索(爬山法),搜索过程如下:(1)把初始节点S0放入OPEN表,计算f(S0)(2)如果OPEN表为空,则问题无解,退出(3)把OPEN表的第一个节点(记为节点n)取出,放入CLOSED表(4)考查节点n是否为目标节点.若是,则求得了问题的解,退出(5)若节点n不可扩展,则转第(2)步(6)扩展节点n,用估价函数f(x)计算每个子节点的估价值,并按估价值从小到大的顺序依次放入OPEN表的首部,并为每一个子节点都配置指向父节点的指针,转第(2)步,2023/6/13,史忠植 人工智能：自动推理,51,局部择优搜索(爬山法),爬山法的三个问题：局部最大。高地：也称为平顶，在某一局部点周围f(x)为常量。此时，搜索就无法确定要搜索的最佳方向，会产生随机走动，这使得搜索效率降低。山脊：山脊可能具有陡峭的斜面，所以搜索可以比较容易地到达山脊的顶部，但是山脊的顶部到山峰之间可能倾斜的很平缓。除非正好有合适的操作符直接沿着山脊的顶部移动，该搜索可能会在山脊的两面来回震荡，搜索的前进步伐会很小。,2023/6/13,史忠植 人工智能：自动推理,52,全局择优搜索(有序搜索/最好优先),搜索过程如下:(1)把初始节点S0放入OPEN表,计算f(S0)(2)如果OPEN表为空,则问题无解,退出(3)把OPEN表的第一个节点(记为节点n)取出,放入CLOSED表(4)考查节点n是否为目标节点.若是,则求得了问题的解,退出(5)若节点n不可扩展,则转第(2)步(6)扩展节点n,用估价函数f(x)计算每个子节点的估价值,并为每一个子节点都配置指向父节点的指针,把这些子节点都送入OPEN表,然后对OPEN表中的全部节点按估价值从小到大的顺序进行排列(7)转第(2)步,2023/6/13,史忠植 人工智能：自动推理,53,A*算法,将状态空间一般搜索过程进行如下的限制,就是A*算法把OPEN表中的节点按估价函数 f(x)=g(x)+h(x)的值从小到大进行排序g(x)是对g*(x)的估价,g(x)0h(x)是h*(x)的下界,即对所有的x,h(x)=h*(x)其中:g*(x)是从初始节点S0到节点x的最小代价 h*(x)是从节点x到目标节点的最小代价,若有多个目标节点,则为其中最小的一个,2023/6/13,史忠植 人工智能：自动推理,54,A*算法,f*(S)f*(S)=g*(S)+h*(S)=h*(S)从S无约束地到达目标的最佳路经上的耗散值;g(n)一般取实际走过的路径的费用和.g(n)g*(n)随着算法的执行，由于指针的变动，g(n)会下降.h0没有启发式信息;,2023/6/13,史忠植 人工智能：自动推理,55,A*算法,8数码问题h(n)=“不在位”的将牌数h(n)=将牌“不在位”的距离和,2023/6/13,史忠植 人工智能：自动推理,56,A*算法,2023/6/13,史忠植 人工智能：自动推理,57,A*算法,2023/6/13,史忠植 人工智能：自动推理,58,A*算法可纳性,对于可解状态图(即从初始节点到目标节点有路径存在)所说,如果一个搜索算法能在有限步内终止,并且能找到最优解,则称该搜索算法是可纳的.定理:A*算法是可纳的,即在有限步内终止,并且找到最优解证明思路对于有限图,A*算法一定会在有限步内终止对应无限图,只要从初始节点到目标节点有路径存在,A*算法也必然终止A*算法一定终止在最优路径上,2023/6/13,史忠植 人工智能：自动推理,59,A*算法的最优性,最优性A*算法的搜索效率在很大程度上取决于h(x),在满足h(x)=h*(x)的前提下,h(x)的值越大越好.H(x)所携带的启发性信息越多,搜索时所扩展的节点数越少,搜索效率就越高,2023/6/13,史忠植 人工智能：自动推理,60,A*算法的单调性,单调性限制单调性限制是指h(x)满足如下两个条件h(Sg)=0设xj是节点xi 的任意子节点,则有 h(xi)-h(xj)=c(xi,xj)其中:Sg是目标节点,c(xi,xj)是节点xi到子节点xj的边代价A*算法的h(x)满足单调性限制时,可有下面的结论若A*算法选择节点xn进行扩展,则g(xn)=g*(x)由A*算法所扩展的节点序列其f值是非递减的,2023/6/13,史忠植 人工智能：自动推理,61,2023/6/13,史忠植 人工智能：自动推理,62,内容提要,3.1 概述3.2 三段论推理3.3 盲目搜索3.4 回溯策略3.5 启发式搜索3.6 与或图启发式搜索3.7 博弈搜索3.8 归结演绎推理3.9 产生式系统3.10 自然演绎推理3.11 非单调推理3.12 小结,与或图启发式搜索,与或（AND-OR）图的反向推理过程可以看作是一个问题归约过程，在问题求解过程中，将一个大的问题变换成若干个子问题，子问题又可以分解成更小的子问题，这样一直分解到可以直接求解为止，全部子问题的解就是原问题的解。原问题称为初始问题，可直接求解的问题称为本原问题。问题归约法不同于状态空间法，是另一种问题描述和求解的方法。,2023/6/13,史忠植 人工智能：自动推理,63,问题归约,一般说来，问题归约可以用三元组表示：（S0，O，P），其中：S0是初始问题，即要求解的问题；P是本原问题集，其中的每一个问题是不用证明的，自然成立的，如公理、已知事实等，或已证明过的问题；O是操作算子集，它是一组变换规则，通过一个操作算子把一个问题化成若干个子问题。这样，问题归约表示方法就是由初始问题出发，运用操作算子产生一些子问题，对子问题再运用操作算子产生子问题的子问题，这样一直进行到产生的问题均为本原问题，则问题得解。,2023/6/13,史忠植 人工智能：自动推理,64,与或图,与节点：把单个问题分解为几个子问题来求解。只有当所有子问题都有解，该父辈节点才有解。表示一种“与”关系。或节点：同一问题被转换为几种不同的后继问题。只要有一个后继问题有解，则原问题有解。表示一种“或”关系。与节点由与运算连接（超弧）.或节点由或运算连接.,2023/6/13,史忠植 人工智能：自动推理,65,定义：与或图就是包含与节点和或节点的图，即存在超弧的图，也称为超图.超图与状态空间图有什么区别？与或图是一种更一般的图.定义：一超弧所相关的边数（K）被称为该超弧的度，实现的连接称为K-连接.K连接符：从一个父节点指向一组含有K个后继节点的节点集.,与或图,2023/6/13,史忠植 人工智能：自动推理,66,在与或图中，节点 n0 有两个连接符：1-连接符指向节点 n1；2-连接符指向节点集合n4、n5；对于节点 n0 来讲，n1 可称为或节点，n4、n5 可称为与节点。,与或图,与或图,2023/6/13,史忠植 人工智能：自动推理,67,68,与或图知识表示,三阶梵塔问题。对于梵塔问题，我们也可以这样考虑：为把1号杆上的n个盘子搬到3号杆，可先把上面的n-1个盘子搬到2号杆上；再把剩下的一个大盘子搬到3号杆；然后再将2号杆上的n-1个盘子搬到3号杆。这样，就把原来的一个问题分解为三个子问题。这三个子问题都比原问题简单，其中第二个子问题已是直接可解的问题。对于第一和第三两个子问题，可用上面n个盘子的方法，做同样的处理。,2023/6/13,史忠植 人工智能：自动推理,69,思考：用状态空间法有多少个节点？为什么？,梵塔问题,2023/6/13,史忠植 人工智能：自动推理,70,(1,1,1)=(3,3,3),(1,1,1)=(1,1,3),(1,2,3)=(1,2,2),(3,2,2)=(3,2,1),(3,3,1)=(3,3,3),(1,1,3)=(1,2,3),(3,2,1)=(3,3,1),(1,1,1)=(1,2,2),(1,2,2)=(3,2,2),(3,2,2)=(3,3,3),梵塔问题的与或树,2023/6/13,史忠植 人工智能：自动推理,71,把本原问题的解按照从左至右的顺序排列，就得到了原始问题的解：(1,1,1)=(1,1,3)(1,1,3)=(1,2,3)(1,2,3)=(1,2,2)(1,2,2)=(3,2,2)(3,2,2)=(3,2,1)(3,2,1)=(3,3,1)(3,3,1)=(3,3,3)任何一个状态图都可以转化为与或图。,三阶梵塔问题的与或树,2023/6/13,史忠植 人工智能：自动推理,72,与或图搜索,有界深度优先搜索算法步1 把初始节点S0放入OPEN表。步2 把OPEN表中的第一个节点（记为节点N）取出放入CLOSED 表，并冠以编号n。步3 如果节点N的深度大于等于深度界限，则转步5第（1）点。步4 如果节点N可扩展，则作下列工作：(1)扩展节点N，将其子节点放入OPEN表首部，并为每个子节点配置指向父节点的指针，以备标示过程中使用。,2023/6/13,史忠植 人工智能：自动推理,73,与或图搜索,(2)考查这些节点中是否有终止节点。若有，标示这些节点为可解 节点并用可解标示过程对其先辈节点中的可解节点进行标示。如果也被标示为可解节点，就得到解树，搜索成功，退出。（3）若不能确定为可解节点，则从OPEN表中删除具有可解先辈 节点。转步2步5 如果节点N不可扩展，则作如下工作：（1）表示节点N为不可解节点。（2）应用不可解节点标示过程对节点N的先辈节点中不可解的节点 进行标示。如果初始节点S0也被标示为不可解节点，则搜索 失败，退出搜索过程；如果不能确定S0为不可解节点，则从 OPEN表中删去具有不可解先辈的节点。（3）转步2。,2023/6/13,史忠植 人工智能：自动推理,AO*算法,算法交替执行以下两个阶段的操作：第一阶段：自顶向下地生成局部与或图-选择迄今为止最好的局部解图；对该解图的一个非终叶节点进行扩展，计算该节点各个K-连接符连接的后继节点解图的花费计值；如果可能，标记后继节点为能解节点。,第二阶段：自下而上地计算修正与或图花费估计值-确定最小花费连接符；如果必要，修改父节点的花费值；或标记父节点为能解节点;此过程不断进行直到到达局部解图的根节点为止。,2023/6/13,史忠植 人工智能：自动推理,74,AO*算法数据结构,s：初始节点；n：当前节点。,G：以 s 为根节点产生的与或图；,G：当前选择的局部与或解图；,h(m)：任意节点 m 到 N 的启发式费用估计值；,q(n)：目前得到的以节点 n 为根的解图的最小耗费；,q0(n)：上一次获得的以节点n为根的解图的最小耗费。,2023/6/13,史忠植 人工智能：自动推理,75,AO*搜索算法,假设：G；G；h(n)是从节点 n 到一组终叶节点的一个最优解图的一个代价估计，评价函数q(n)=h(n)AO*过程:1.建立初始搜索图，G:=s，计算 q(s)=h(s)，IF GOAL(s)THEN M(s,SOLVED)；2.Until s 已标记为 SOLVED,do:3.Begin4.G:=FIND(G)；根据连接符标记（指针）找出一个待扩展的侯选局部解图G（连接符在11步标记）5.n:=G 中的任一非终节点;选一个当前节点6.EXPAND(n),生成子节点集ni，如果 ni G，G:=ADD(ni,G),计算 q(ni)=h(ni)，IF GOAL(ni)THEN M(ni,SOLVED);,2023/6/13,史忠植 人工智能：自动推理,76,7 S:=n;建立含 n 的节点集合S.（已扩展待修正）8 Until S为空,do:9 Begin(m为S中任一节点)10 REMOVE(m,S),当 mcS;（mmc,从底层开始修正）11 修改 m 的耗散值 q(m):对 m 指向节点集(n1i，n2i,nki)的每一个连接符 i 分别计算qi,qi(m)=Ci+q(n1i)+q(nki),并取 q(m):=min qi(m);加(或修正)指针到 min qi(m)的连接符上.IF M(nji,SOLVED)THEN M(m,SOLVED);（j=1，2，k）若该连接符的所有子节点都是能解的,则m也能解.12 IF M(m,SOLVED)(q(m)q0(m)THEN ADD(ma,S);m 能解或修正的耗散值与原先估算q0不同,则把m的所有先辈节点ma添加到S中.（能解或修正向上传递）13 end(与8匹配)14 end(与2匹配),AO*搜索算法,2023/6/13,史忠植 人工智能：自动推理,77,AO*搜索算法流程图,2023/6/13,史忠植 人工智能：自动推理,78,AO*搜索算法流程图,2023/6/13,史忠植 人工智能：自动推理,79,与A*算法的区别,评价函数只考虑 h(n):理由:算法有自下而上的修正费用的的操作,实际上局部解图费用值的估计是在起始节点S 比较,计算 g 既无必要也不可能.不能优先扩展具有最小费用的节点:理由:K-连接符连接的有关子节点对父节点的可解性及费用值的估计都会产生影响.仅适用于无环图,否则耗散值递归计算不收敛:方法:当新生成的节点已在图中时,判断是否为正被扩展节点的先辈节点.控制策略不同:没有 OPEN 表和 CLOSED 表,只用生成的解图结构 G,h(n)是最佳解图的费用估计.,AO*算法与A*算法的区别,2023/6/13,史忠植 人工智能：自动推理,80,2023/6/13,史忠植 人工智能：自动推理,81,内容提要,3.1 概述3.2 三段论推理3.3 盲目搜索3.4 回溯策略3.5 启发式搜索3.6 与或图启发式搜索3.7 博弈搜索3.8 归结演绎推理3.9 产生式系统3.10 自然演绎推理3.11 非单调推理3.12 小结,博弈一向被认为是富有挑战性的智力活动，如下棋、打牌、作战、游戏等等。博弈的研究不断为人工智能提出新的课题，可以说博弈是人工智能研究的起源和动力之一。博弈的特性是：两个棋手交替地走棋；比赛的最终结果，是赢、输和平局中的一种；可用图搜索技术进行，但效率很低；博弈的过程，是寻找置对手于必败态的过程；双方都无法干预对方的选择。,博弈,2023/6/13,史忠植 人工智能：自动推理,82,20世纪60年代，研制出的西洋跳棋和国际象棋达到了大师级的水平。1958年麦卡锡提出博弈树剪枝算法1997年，IBM公司研制的“深蓝”国际象棋 程序，采用博弈树搜索算法，该程序战胜了国际象棋世界冠军卡斯帕罗夫。,博弈,2023/6/13,史忠植 人工智能：自动推理,83,与深蓝下棋的卡斯帕罗夫,1997“深蓝”赢了卡斯帕罗夫,2023/6/13,史忠植 人工智能：自动推理,84,对各个局面进行评估评估的目的：对后面的状态提前进行考虑，并且以各种状态的评估值为基础作出最好的走棋选择。评估的方法：用评价函数对棋局进行评估。赢的评估值设为+，输的评估值设为-，平局的评估值设为0。评估的标准：由于下棋的双方是对立的，只能选择其中一方为评估的标准方。,极大极小搜索过程,2023/6/13,史忠植 人工智能：自动推理,85,命名博弈的双方，一方为“正方”，对每个状态的评估都是对应于该方的输赢的。例如，赢2个，输1个等，都是指正方的。正方每走一步，都在选择使自己赢得更多的节点，因此这类节点称为“MAX”节点；另一方为“反方”，对每个状态的评估都是对应于对手的输赢的。例如，赢2个，输一个，其实是指自己输2个，赢1个的。反方每走一步，都在选择使对手输得更多的节点，因此这类节点称为“MIN”节点。,极大极小搜索过程,2023/6/13,史忠植 人工智能：自动推理,86,极大极小搜索过程,2023/6/13,史忠植 人工智能：自动推理,87,MIN,极大极小搜索过程,2023/6/13,史忠植 人工智能：自动推理,88,-剪枝法的引入 在极大极小法中，必须求出所有终端节点的评估值，当预先考虑的棋步比较多时，计算量会大大增加。为了提高搜索的效率，引入了通过对评估值的上下限进行估计，从而减少需进行评估的节点范围的-剪枝法。,-搜索过程,2023/6/13,史忠植 人工智能：自动推理,89,MAX节点的评估下限值 作为正方出现的MAX节点，假设它的MIN子节点有N个，那么当它的第一个MIN子节点的评估值为时，则对于其它的子节点，如果有高过的，就取那最高的值作为该MAX节点的评估值；如果没有，则该MAX节点的评估值为。MIN节点的评估上限值 作为反方出现的MIN节点，假设它的MAX子节点有N个，那么当它的第一个MAX子节点的评估值为时，则对于其它子节点，如果有低于的，就取那个低于的值作为该MIN节点的评估值；如果没有，则该MIN节点的评估值取。,-搜索过程,2023/6/13,史忠植 人工智能：自动推理,90,-搜索过程,剪枝法 设MAX节点的下限为，则其所有的MIN子节点中，其评估值的上限小于等于的节点，其以下部分的搜索都可以停止了，即对这部分节点进行了剪枝。,2023/6/13,史忠植 人工智能：自动推理,91,剪枝法 设MIN节点的上限为，则其所有的MAX子节点中，其评估值的下限大于等于的节点，其以下部分的搜索都可以停止了，即对这部分节点进行了剪枝。,-搜索过程,2023/6/13,史忠植 人工智能：自动推理,92,A,B,C,D,E,F,G,H,I,J,K,L,N,O,M,-搜索过程,MAX节点,MAX节点,MIN节点,终端节点,3,5,6,5,2,1,6,4,2023/6/13,史忠植 人工智能：自动推理,93,-搜索过程,2023/6/13,史忠植 人工智能：自动推理,94,一字棋-剪枝,2023/6/13,史忠植 人工智能：自动推理,95,-剪枝,极大节点的下界为。极小节点的上界为。剪枝的条件：后辈节点的值祖先节点的值时，剪枝后辈节点的 值祖先节点的值时，剪枝简记为：极小极大，剪枝极大极小，剪枝,2023/6/13,史忠植 人工智能：自动推理,96,当算法给出所选的走步后，不要马上停止搜索，而是在原先估计可能的路径上再往前搜索几步，再次检验会不会出现意外，这是一种增添辅助搜索的方法。对某些博弈的开局阶段和残局阶段，往往总结了一些固定的对弈模式，因此可以利用这些知识编好走步表，以便在开局和结局时使用查表法。只是在进入中盘阶段后，再调用其他有效的搜索算法，来选择最优的走步。,-搜索过程,2023/6/13,史忠植 人工智能：自动推理,97,2023/6/13,史忠植 人工智能：自动推理,98,内容提要,3.1 概述3.2 三段论推理3.3 盲目搜索3.4 回溯策略3.5 启发式搜索3.6 与或图启发式搜索3.7 博弈搜索3.8 归结演绎推理3.9 产生式系统3.10 自然演绎推理3.11 非单调推理3.12 小结,归结演绎推理,归结演绎推理本质上就是一种反证法，它是在归结推理规则的基础上实现的。为了证明一个命题P恒真，它证明其反命题P恒假，即不存在使得P为真的解释。由于量词，以及嵌套的函数符号，使得谓词公式往往有无穷的指派，不可能一一测试P是否为真或假。那么如何来解决这个问题呢？幸运的是存在一个域，即Herbrand域，它是一个可数无穷的集合，如果一个公式基于Her
