人工智能ArtificialIntelligence.ppt

《人工智能ArtificialIntelligence.ppt》由会员分享，可在线阅读，更多相关《人工智能ArtificialIntelligence.ppt（158页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、人工智能人工智能Artificial IntelligenceArtificial Intelligence第三章第三章史忠植史忠植 中国科学院计算技术研究所自动推理自动推理Automated Reasoning2022/11/18史忠植人工智能：自动推理12022/11/18史忠植人工智能：自动推理2内容提要内容提要自动推理是人工智能的核心内容之一，是专家系统、程序推导、程序正确性证明、智能机器人等研究领域的重要基础。自动推理早期的工作主要集中在机器定理证明。1930年希尔伯特（Herbrand）为定理证明建立了一种重要方法，他的方法奠定了机械定理证明的基础。机械定理证明的主要突破是1965

2、年由鲁宾逊做出的，他建立了所谓归结原理，使机械定理证明达到了应用阶段。在本章，首先讨论三段论推理和搜索策略，然后讨论归结演绎推理、产生式系统，最后讨论非单调推理。自动推理自动推理2022/11/183史忠植人工智能：自动推理2022/11/18史忠植人工智能：自动推理4内容提要内容提要三段论是一种常用的推理形式，它由三个性质命题组成，其中两个性质命题是前提，另一个性质命题是结论。例如 科学是不断发展的；(大前提)智能科学是科学：(小前提)所以，智能科学是不断发展的。(结论)这就是一个三段论。前两个性质判断包含着一个共同项“科学”，由这两个具有同项的判断推出一个新的性质判断：智能科学是不断发展的

3、。三段论三段论2022/11/185史忠植人工智能：自动推理其中，结论中的主项叫做小项，用“S”表示，如上例中的“智能科学；结论中的谓项叫做大项，用“P”表示，如上例中的“不断发展的；两个前提中共有的项叫做中项，用“M”表示，如上例中的“科学。在三段论中，含有大项的前提叫大前提，如上例中的“科学是不断发展的”；含有小项的前提叫小前提，如上例中的“智能科学是科学。三段论三段论2022/11/186史忠植人工智能：自动推理三段论的公理三段论的公理三段论的公理是三段论推理的基本依据。三段论的公理是客观事物的最一般、最普遍的关系在人们思维中的反映，是在人类长期反复实践中被总结出来的，并不断被实践所证明

4、的，具有不证自明性。三段论的公理内容：对一类事物的全部有所断定（肯定或否定），则对该类事物的部分也就有所断定（肯定或否定）。三段论的公理用图表示如下：2022/11/187史忠植人工智能：自动推理P M SS M P图1图2三段论的公理三段论的公理 在图1中，M类全部包含在P类中（所有M是P），S类是M类的一部分（所有S是M），可见，S类的全部必然包含在P类中的。在图2中，M类全部与P类相排斥（所有M不是P），S类是M类的一部分（所有S是M），可见，S类的全部必然与P类相排斥。2022/11/188史忠植人工智能：自动推理三段论的格三段论的格三段论的格就是根据中项在三段论中的不同位置所构成的不

5、同形式的三段论。在三段论的第一格中，中项是大前提的主项、小前提的谓项；在第二格中，中项是大、小前提的谓项；在第三格中，中项是大、小前提的主项；在第四格中，中项是大前提的谓项、小前提的主项。三段论的四个格可以分别表示如下：第一格第二格第三格第四格MPPMMPPMSMSMMSMSSPSPSPSP2022/11/189史忠植人工智能：自动推理构成三段论推理的三个性质命题，在质和量上的不同，就形成了三段论的不同形式，这些不同的形式叫做三段论的式。三段论总是由质和量不同的A（全称肯定命题）、E（全称否定命题）、I（特称肯定命题）、O（特称否定命题）四种命题组合而成，任何一个三段论推理都表现为一定的格和式

6、。A、E、I、O都可以作为大前提、小前提和结论，其排列组合数目是：444=64。这样，每个格都有64式，四个格共有644=256式。但大多数是违反三段论规则的，是错误的式或无效式。三段论的式三段论的式2022/11/1810史忠植人工智能：自动推理根据三段论推理的规则，就可以确定出各个格的正确式。四个格总共有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，

7、EIO。上面的各个式中，凡带有括号的式叫做“弱式”，共有五个弱式。弱式就是指可推出全称结论但只推出一个特称结论的式。如第一格中AII式。我们知道，在第一格中，从AA这两个前提可以推出全称结论A，但得出AAI式却是一个特称结论，因而这个式就是弱式。例如：所有的植物都是生物；（A）所有的玫瑰花都是植物；（A）所以，有的玫瑰花是生物。（I）三段论的式三段论的式2022/11/1811史忠植人工智能：自动推理2022/11/18史忠植人工智能：自动推理12内容提要内容提要问题求解问题求解AI中每个研究领域都有其各自的特点和规律,但就求解问题的过程看,都可抽象为一个问题求解过程。问题求解过程实际上是一个

8、搜索,广义地说,它包含了全部计算机科学。任何问题求解技术都包括两个重要的方面:表示和搜索表示是基本的,搜索必须要在表示的基础上进行。表示关系到搜索的效率。本章讨论的表示主要包括:状态空间表示问题空间表示2022/11/18史忠植人工智能：自动推理13搜搜 索索q1974年，Nilsson归纳出的AI研究的基本问题知识的模型化和表示常识性推理、演绎和问题解决启发式搜索人工智能系统和语言q搜索是人工智能中的一个基本问题,是推理不可分割的一部分,直接关系到智能系统的性能和运行效率qAI为什么要研究search?问题没有直接的解法;需要探索地求解;2022/11/18史忠植人工智能：自动推理14什么是

9、搜索什么是搜索根据问题的实际情况不断寻找可利用的知识,构造出一条代价较少的推理路线,使问题得到圆满解决的过程称为搜索包括两个方面：n 找到从初始事实到问题最终答案的一条推理路径n 找到的这条路径在时间和空间上复杂度最小2022/11/18史忠植人工智能：自动推理15搜索策略搜索策略盲目搜索:也称为无信息搜索，即只按预定的控制策略进行搜索,在搜索过程中获得的中间信息不用来改进控制策略启发式搜索:在搜索中加入了与问题有关的启发性信息,用于指导搜索朝着最有希望的方向进行,加速问题的求解过程并找到最优解2022/11/18史忠植人工智能：自动推理16搜索策略搜索策略一般搜索策略可以通过下面4个准则来评

10、价：（1）完备性：如果存在一个解答，该策略是否保证能够找到？（2）时间复杂性：需要多长时间可以找到解答？（3）空间复杂性：执行搜索需要多大存储空间？（4）最优性：如果存在不同的几个解答，该策略可以发现是否最高质量的解答？2022/11/18史忠植人工智能：自动推理17盲目搜索盲目搜索n盲目搜索一般是按预定的搜索策略进行搜索。由于这种搜索总是按预定的路线进行，没有考虑到问题本身的特性，所以这种搜索具有很大的盲目性，效率不高，不便于复杂问题的求解。深度优先搜索宽度优先搜索迭代加深搜索2022/11/18史忠植人工智能：自动推理1819深度优先搜索深度优先搜索(Dephth-first)(Depht

11、h-first)n深度优先搜索生成节点并与目标节点进行比较是沿着树的最大深度方向进行的，只有当上次访问的节点不是目标节点，而且没有其他节点可以生成的时候，才转到上次访问节点的父节点。转移到父节点后，该算法会搜索父节点的其它的子节点。n防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度深度界限。2022/11/18史忠植人工智能：自动推理20深度优先搜索示意图深度优先搜索示意图SLOMFPQNFFF2022/11/18史忠植人工智能：自动推理21开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表是否

12、有后继节点是否有后继节点为目标节点？为目标节点？扩展扩展n，把，把n的后继节点放入的后继节点放入OPEN表的表的前前端，提供返回节点端，提供返回节点n的指针的指针失败失败成功成功是是否否是是否否节点节点n的深度等于最大深度？的深度等于最大深度？否否深度优先算法框图深度优先算法框图2022/11/18史忠植人工智能：自动推理22有界深度有界深度(4)优先的八数码问题深度优先搜索树优先的八数码问题深度优先搜索树1238456712384567（目标状态）（目标状态）（初始状态（初始状态）深度优先搜索树深度优先搜索树2022/11/18史忠植人工智能：自动推理23八数码有界深度优先搜索树八数码有界深

13、度优先搜索树2022/11/18史忠植人工智能：自动推理(1)把初始节点S0放入OPEN表(2)如果OPEN表为空,则问题无解,退出(3)把OPEN表的第一个节点(记为节点n)取出,放入CLOSED表(4)考查节点n是否为目标节点.若是,则求得了问题的解,退出(5)若节点n不可扩展,则转第(2)步(6)扩展节点n,将其子节点放入OPEN表的首部,并为每一个子节点都配置指向父节点的指针,转第(2)步深度优先搜索过程深度优先搜索过程2022/11/18史忠植人工智能：自动推理2425SLOMFPQNFFF宽度优先搜索示意图宽度优先搜索示意图2022/11/18史忠植人工智能：自动推理26（1）把起

14、始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。（2）如果OPEN是个空表，则没有解，失败退出；否则继续。（3）把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。（4）扩展节点n。如果没有后继节点，则转向上述第(2)步。（5）把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。（6）如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。宽度优先搜索算法宽度优先搜索算法2022/11/18史忠植人工智能：自动推理27开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个

15、节点(n)从从OPEN表移至表移至CLOSED表表是否有后继节点是否有后继节点为目标节点？为目标节点？扩展扩展n，把，把n的后继节点放入的后继节点放入OPEN表的表的末末端，提供返回节点端，提供返回节点n的指针的指针失败失败成功成功是是否否是是否否宽度优先算法框图宽度优先算法框图2022/11/18史忠植人工智能：自动推理28八数码难题（八数码难题（8-puzzle problem8-puzzle problem）1238456712384567（目标状态）（目标状态）（初始状态（初始状态）规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展2

16、6个节点，共生成46个节点之后才求得解（目标节点）。宽度优先算法例子宽度优先算法例子2022/11/18史忠植人工智能：自动推理29八数码宽度优先搜索树八数码宽度优先搜索树2022/11/18史忠植人工智能：自动推理迭代加深搜索迭代加深搜索对于有界深度搜索策略，有下面几点需要说明：1）在有界深度搜索算法中，深度限制dm是一个很重要的参数。2）深度限制dm不能太大。3）有界深度搜索的主要问题是深度限制值dm的选取。问题：但是对很多问题，我们并不知道该值到底为多少，直到该问题求解完成了，才可以确定出深度限制dm。2022/11/18史忠植人工智能：自动推理30迭代加深搜索迭代加深搜索改进方法-迭代

17、加深搜索算法 先任意给定一个较小的数作为dm，然后按有界深度算法搜索，若在此深度限制内找到了解，则算法结束；如在此限度内没有找到问题的解，则增大深度限制dm，继续搜索。迭代加深搜索是一种回避选择最优深度限制问题的策略，它是试图尝试所有可能的深度限制：首先深度为0，然后深度为1，然后为2，等等，一直进行下去。问题迭代加深搜索看起来会很浪费，因为很多节点都要扩展多次。2022/11/18史忠植人工智能：自动推理312022/11/18史忠植人工智能：自动推理32内容提要内容提要2022/11/18史忠植人工智能：自动推理33回溯算法回溯算法有些问题需要彻底的搜索才能解决问题，然而，彻底的搜索要以大

18、量的运算时间为代价，对于这种情况可以通过回溯法来去掉一些分枝，从而大大减少搜索的次数。八皇后问题迷宫问题深度优先周游树或图 四皇后问题中隐含的状态树 四皇后问题四皇后问题2022/11/18史忠植人工智能：自动推理342022/11/18史忠植人工智能：自动推理35四皇后问题树四皇后问题树回溯算法回溯算法empty assignment1st variable2nd variable3rd variableAssignment=2022/11/18史忠植人工智能：自动推理36empty assignment1st variable2nd variable3rd variableAssignme

19、nt=(var1=v11)回溯算法回溯算法2022/11/18史忠植人工智能：自动推理37empty assignment1st variable2nd variable3rd variableAssignment=(var1=v11),(var2=v21)回溯算法回溯算法2022/11/18史忠植人工智能：自动推理38empty assignment1st variable2nd variable3rd variableAssignment=(var1=v11),(var2=v21),(var3=v31)回溯算法回溯算法2022/11/18史忠植人工智能：自动推理39empty assign

20、ment1st variable2nd variable3rd variableAssignment=(var1=v11),(var2=v21),(var3=v32)回溯算法回溯算法2022/11/18史忠植人工智能：自动推理40empty assignment1st variable2nd variable3rd variableAssignment=(var1=v11),(var2=v22)回溯算法回溯算法2022/11/18史忠植人工智能：自动推理41empty assignment1st variable2nd variable3rd variableAssignment=(var1=

21、v11),(var2=v22),(var3=v31)回溯算法回溯算法2022/11/18史忠植人工智能：自动推理422022/11/18史忠植人工智能：自动推理43递归回溯算法递归回溯算法Recursive procedure BACKTRACK(DATA)1.if TERM(DATA),return NIL;/*TERM是一个谓词，对满足产生式系统结束条件变量来说取值为真。在成功结束时，返回空表N1L。*/2.if DEADEND(DATA),retulrn FAIL;/*DEADEND是一个谓词，对已经知道不在一条解路上的自变量来说取值为真。在这种情况下，过程返回符号FAIL。*/3.RU

22、LESAPPRULUES(DATA);/*APPRULUES是一个函数，它计算可应用于其自变量的规则并排列这些规则(任意排列或者按照启发式准则排列)。*/4.LOOP:if NULL(RULES),return FAIL;/*如果不再有可应用的规则，那么过程失败。*/5.RFIRST(RULES);/*选出最好的一条可应用规则。*/2022/11/18史忠植人工智能：自动推理44递归回溯算法递归回溯算法6.RULESTAIL(RULES);/*删去刚才选用的一条规则，缩小可应用的规则表。*/7.RDATAR(DATA);/*应用规则R产生一个新的数据库。*/8.PATHBACKTRACK(RD

23、ATA);/*在新数据库上递归调用BACKTRACK。*/9.if PATH=FAIL,go LOOP;/*若递归调用失败，则试另一条规则。*/10.return CONS(R,PATH);/*否则，通过把R加到表的前面，向上走一遍成功的规则表。*/2022/11/18史忠植人工智能：自动推理45内容提要内容提要启发式搜索启发式搜索q前面讨论的方法都是盲目的搜索方法,即都没有利用问题本身的特性信息,在决定要被扩展的节点时,都没有考虑该节点在解的路径上的可能性有多大,它是否有利于问题求解以及求出的解是否为最优q启发式搜索要用到问题自身的某些特性信息,以指导搜索朝着最有希望的方向前进启发信息的强度

24、强：降低搜索工作量，但可能导致找不到最优解弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解2022/11/18史忠植人工智能：自动推理46启发式搜索启发式搜索q启发性信息和估价函数用于指导搜索过程,且与具体问题有关的控制性信息称为为启发性信息用于评价节点重要性的函数称为估价函数.记为 f(x)=g(x)+h(x)g(x)为从初始节点S0到节点x已经实际付出的代价h(x)是从节点x到目标节点Sg的最优路径的估价代价,体现了问题的启发性信息,称为启发函数f(x)表示从初始节点经过节点x到达目标节点的最优路径的代价估价值,其作用是用来评估OPEN表中各节点的重要性,决定其次序20

25、22/11/18史忠植人工智能：自动推理47启发式搜索启发式搜索n例：八数码问题，评价函数nf(n)=d(n)+W(n)nd(n):节点n的深度;nW(n):与目标相比,错位的数字数目;1238476528316475初始状态目标状态 2022/11/18史忠植人工智能：自动推理482 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47

26、 6 51 2 38 47 6 51 2 37 8 4 6 5s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目标123456八数码启发式搜索八数码启发式搜索2022/11/18史忠植人工智能：自动推理49启发式搜索启发式搜索启发式就是要猜测：从节点n开始，找到最优解的可能性有多大？从起始节点开始，经过节点n，到达目标节点的最佳路径的费用是多少？gh2022/11/18史忠植人工智能：自动推理50局部择优搜索局部择优搜索(爬山法爬山法)搜索过程如下:(1)把初始节点S0放入OPEN表,计算f(S0)(2)如果OPEN表为空,则问题

27、无解,退出(3)把OPEN表的第一个节点(记为节点n)取出,放入CLOSED表(4)考查节点n是否为目标节点.若是,则求得了问题的解,退出(5)若节点n不可扩展,则转第(2)步(6)扩展节点n,用估价函数f(x)计算每个子节点的估价值,并按估价值从小到大的顺序依次放入OPEN表的首部,并为每一个子节点都配置指向父节点的指针,转第(2)步2022/11/18史忠植人工智能：自动推理51局部择优搜索局部择优搜索(爬山法爬山法)爬山法的三个问题：1.局部最大。2.高地：也称为平顶，在某一局部点周围f(x)为常量。此时，搜索就无法确定要搜索的最佳方向，会产生随机走动，这使得搜索效率降低。3.山脊：山脊

28、可能具有陡峭的斜面，所以搜索可以比较容易地到达山脊的顶部，但是山脊的顶部到山峰之间可能倾斜的很平缓。除非正好有合适的操作符直接沿着山脊的顶部移动，该搜索可能会在山脊的两面来回震荡，搜索的前进步伐会很小。2022/11/18史忠植人工智能：自动推理52全局择优搜索全局择优搜索(有序搜索有序搜索/最好优先最好优先)搜索过程如下:(1)把初始节点S0放入OPEN表,计算f(S0)(2)如果OPEN表为空,则问题无解,退出(3)把OPEN表的第一个节点(记为节点n)取出,放入CLOSED表(4)考查节点n是否为目标节点.若是,则求得了问题的解,退出(5)若节点n不可扩展,则转第(2)步(6)扩展节点n

29、,用估价函数f(x)计算每个子节点的估价值,并为每一个子节点都配置指向父节点的指针,把这些子节点都送入OPEN表,然后对OPEN表中的全部节点按估价值从小到大的顺序进行排列(7)转第(2)步2022/11/18史忠植人工智能：自动推理53A*A*算法算法q将状态空间一般搜索过程进行如下的限制,就是A*算法1)把OPEN表中的节点按估价函数 f(x)=g(x)+h(x)的值从小到大进行排序2)g(x)是对g*(x)的估价,g(x)03)h(x)是h*(x)的下界,即对所有的x,h(x)=h*(x)其中:g*(x)是从初始节点S0到节点x的最小代价 h*(x)是从节点x到目标节点的最小代价,若有多

30、个目标节点,则为其中最小的一个2022/11/18史忠植人工智能：自动推理54A*A*算法算法f*(S)f*(S)=g*(S)+h*(S)=h*(S)从S无约束地到达目标的最佳路经上的耗散值;g(n)一般取实际走过的路径的费用和.g(n)g*(n)随着算法的执行，由于指针的变动，g(n)会下降.h0没有启发式信息;nSg*(n)h*(n)g2022/11/18史忠植人工智能：自动推理55A*A*算法算法8数码问题h(n)=“不在位”的将牌数h(n)=将牌“不在位”的距离和2 8 31 6 47 51 2 3457 6 8将牌1：1将牌2：1将牌6：1将牌8：22022/11/18史忠植人工智能

31、：自动推理56A*A*算法算法2022/11/18史忠植人工智能：自动推理57A*A*算法算法2022/11/18史忠植人工智能：自动推理58A*A*算法可纳性算法可纳性q对于可解状态图(即从初始节点到目标节点有路径存在)所说,如果一个搜索算法能在有限步内终止,并且能找到最优解,则称该搜索算法是可纳的.q定理:A*算法是可纳的,即在有限步内终止,并且找到最优解q证明思路对于有限图,A*算法一定会在有限步内终止对应无限图,只要从初始节点到目标节点有路径存在,A*算法也必然终止A*算法一定终止在最优路径上2022/11/18史忠植人工智能：自动推理59A*A*算法的最优性算法的最优性q最优性A*算

32、法的搜索效率在很大程度上取决于h(x),在满足h(x)=h*(x)的前提下,h(x)的值越大越好.H(x)所携带的启发性信息越多,搜索时所扩展的节点数越少,搜索效率就越高2022/11/18史忠植人工智能：自动推理60A*A*算法的单调性算法的单调性q单调性限制单调性限制是指h(x)满足如下两个条件1)h(Sg)=02)设xj是节点xi 的任意子节点,则有 h(xi)-h(xj)(3,3,3)(1,1,1)=(3,3,3)(1,1,1)=(1,1,3)(1,1,1)=(1,1,3)(1,2,3)=(1,2,2)(1,2,3)=(1,2,2)(3,2,2)=(3,2,1)(3,2,2)=(3,2

33、,1)(3,3,1)=(3,3,3)(3,3,1)=(3,3,3)(1,1,3)=(1,2,3)(1,1,3)=(1,2,3)(3,2,1)=(3,3,1)(3,2,1)=(3,3,1)(1,1,1)=(1,2,2)(1,1,1)=(1,2,2)(1,2,2)=(3,2,2)(1,2,2)=(3,2,2)(3,2,2)=(3,3,3)(3,2,2)=(3,3,3)梵塔问题的与或树梵塔问题的与或树2022/11/18史忠植人工智能：自动推理71把本原问题的解按照从左至右的顺序排列，就得到了原始问题的解：(1,1,1)=(1,1,3)(1,1,3)=(1,2,3)(1,2,3)=(1,2,2)(1

34、,2,2)=(3,2,2)(3,2,2)=(3,2,1)(3,2,1)=(3,3,1)(3,3,1)=(3,3,3)任何一个状态图都可以转化为与或图。三阶梵塔问题的与或树三阶梵塔问题的与或树2022/11/18史忠植人工智能：自动推理72与或图搜索与或图搜索有界深度优先搜索算法步1 把初始节点S0放入OPEN表。步2 把OPEN表中的第一个节点（记为节点N）取出放入CLOSED 表，并冠以编号n。步3 如果节点N的深度大于等于深度界限，则转步5第（1）点。步4 如果节点N可扩展，则作下列工作：(1)扩展节点N，将其子节点放入OPEN表首部，并为每个子节点配置指向父节点的指针，以备标示过程中使用

35、。2022/11/18史忠植人工智能：自动推理73与或图搜索与或图搜索(2)考查这些节点中是否有终止节点。若有，标示这些节点为可解 节点并用可解标示过程对其先辈节点中的可解节点进行标示。如果也被标示为可解节点，就得到解树，搜索成功，退出。（3）若不能确定为可解节点，则从OPEN表中删除具有可解先辈 节点。转步2步5 如果节点N不可扩展，则作如下工作：（1）表示节点N为不可解节点。（2）应用不可解节点标示过程对节点N的先辈节点中不可解的节点 进行标示。如果初始节点S0也被标示为不可解节点，则搜索 失败，退出搜索过程；如果不能确定S0为不可解节点，则从 OPEN表中删去具有不可解先辈的节点。（3）

36、转步2。2022/11/18史忠植人工智能：自动推理 AO*AO*算法算法n算法交替执行以下两个阶段的操作：w 第一阶段：自顶向下地生成局部与或图-选择迄今为止最好的局部解图；对该解图的一个非终叶节点进行扩展，计算该节点各个K-连接符连接的后继节点解图的花费计值；如果可能，标记后继节点为能解节点。w 第二阶段：自下而上地计算修正与或图花费估计值-确定最小花费连接符；如果必要，修改父节点的花费值；或标记父节点为能解节点;此过程不断进行直到到达局部解图的根节点为止。2022/11/18史忠植人工智能：自动推理74AO*AO*算法数据结构算法数据结构 s：初始节点；n：当前节点。G：以 s 为根节点

37、产生的与或图；G：当前选择的局部与或解图；h(m)：任意节点 m 到 N 的启发式费用估计值；q(n)：目前得到的以节点 n 为根的解图的最小耗费；q0(n)：上一次获得的以节点n为根的解图的最小耗费。2022/11/18史忠植人工智能：自动推理75 AO*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)；根

38、据连接符标记（指针）找出一个待扩展的侯选局部解图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);2022/11/18史忠植人工智能：自动推理767 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,

39、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*AO*搜索算法搜索算法2022/11/18史忠植人工智能

40、：自动推理77AO*AO*搜索算法流程图搜索算法流程图选择最有希望的局部解图G 及G 中合适的非叶节点n：G:=Find(G),n:=Select(G)扩展节点 n，计算 mj 的启发式信息：mi :=Expand(n),G:=mi G,对所有mj:q(mj):=h(mj)mj 到 N 的估计值;如果 mj 属于 N 则 Mark(mj，Sovled)。建立以 n 节点为初始节点的祖先节点集合：A:=n A=?YesNo2022/11/18史忠植人工智能：自动推理78 m:=Remove(A)针对m 的L个 k 连接符，求 m 的最小花费q(m)：qi(m):=C(mi)+q(ni1)+q(n

41、i2)+q(nik)1 i Mark(m,Sovled),Mark(m,Sovled)q(m)q0(m)将 m 的父节点 ma 送集合A:A:=A ma YesNoAO*AO*搜索算法流程图搜索算法流程图2022/11/18史忠植人工智能：自动推理79与A*算法的区别评价函数只考虑 h(n):理由:算法有自下而上的修正费用的的操作,实际上局部解图费用值的估计是在起始节点S 比较,计算 g 既无必要也不可能.不能优先扩展具有最小费用的节点:理由:K-连接符连接的有关子节点对父节点的可解性及费用值的估计都会产生影响.仅适用于无环图,否则耗散值递归计算不收敛:方法:当新生成的节点已在图中时,判断是否

42、为正被扩展节点的先辈节点.控制策略不同:没有 OPEN 表和 CLOSED 表,只用生成的解图结构 G,h(n)是最佳解图的费用估计.AO*AO*算法与算法与A*A*算法的区别算法的区别2022/11/18史忠植人工智能：自动推理802022/11/18史忠植人工智能：自动推理81内容提要内容提要博弈一向被认为是富有挑战性的智力活动，如下棋、打牌、作战、游戏等等。博弈的研究不断为人工智能提出新的课题，可以说博弈是人工智能研究的起源和动力之一。博弈的特性是：n两个棋手交替地走棋；n比赛的最终结果，是赢、输和平局中的一种；n可用图搜索技术进行，但效率很低；n博弈的过程，是寻找置对手于必败态的过程；

43、n双方都无法干预对方的选择。博弈博弈2022/11/18史忠植人工智能：自动推理8220世纪60年代，研制出的西洋跳棋和国际象棋达到了大师级的水平。1958年麦卡锡提出博弈树剪枝算法1997年，IBM公司研制的“深蓝”国际象棋 程序，采用博弈树搜索算法，该程序战胜了国际象棋世界冠军卡斯帕罗夫。博弈博弈2022/11/18史忠植人工智能：自动推理83与深蓝下棋的卡斯帕罗夫与深蓝下棋的卡斯帕罗夫1997“深蓝”赢了卡斯帕罗夫2022/11/18史忠植人工智能：自动推理84对各个局面进行评估评估的目的：对后面的状态提前进行考虑，并且以各种状态的评估值为基础作出最好的走棋选择。评估的方法：用评价函数对

44、棋局进行评估。赢的评估值设为+，输的评估值设为-，平局的评估值设为0。评估的标准：由于下棋的双方是对立的，只能选择其中一方为评估的标准方。极大极小搜索过程极大极小搜索过程2022/11/18史忠植人工智能：自动推理85命名博弈的双方，一方为“正方”，对每个状态的评估都是对应于该方的输赢的。例如，赢2个，输1个等，都是指正方的。正方每走一步，都在选择使自己赢得更多的节点，因此这类节点称为“MAX”节点；另一方为“反方”，对每个状态的评估都是对应于对手的输赢的。例如，赢2个，输一个，其实是指自己输2个，赢1个的。反方每走一步，都在选择使对手输得更多的节点，因此这类节点称为“MIN”节点。极大极小搜

45、索过程极大极小搜索过程2022/11/18史忠植人工智能：自动推理86极大极小搜索过程极大极小搜索过程2022/11/18史忠植人工智能：自动推理87015-33 3-3022-3 0-23 5 4 1-30 6 8 9-30-33-3-3-21-36-3031601MAXMINMAXMIN极大极小搜索过程极大极小搜索过程2022/11/18史忠植人工智能：自动推理88n-剪枝法的引入 在极大极小法中，必须求出所有终端节点的评估值，当预先考虑的棋步比较多时，计算量会大大增加。为了提高搜索的效率，引入了通过对评估值的上下限进行估计，从而减少需进行评估的节点范围的-剪枝法。-搜索过程搜索过程202

46、2/11/18史忠植人工智能：自动推理89nMAX节点的评估下限值 作为正方出现的MAX节点，假设它的MIN子节点有N个，那么当它的第一个MIN子节点的评估值为时，则对于其它的子节点，如果有高过的，就取那最高的值作为该MAX节点的评估值；如果没有，则该MAX节点的评估值为。nMIN节点的评估上限值 作为反方出现的MIN节点，假设它的MAX子节点有N个，那么当它的第一个MAX子节点的评估值为时，则对于其它子节点，如果有低于的，就取那个低于的值作为该MIN节点的评估值；如果没有，则该MIN节点的评估值取。-搜索过程搜索过程2022/11/18史忠植人工智能：自动推理90MAX节点节点MIN节点节点

47、=剪剪枝ABCD-搜索过程搜索过程n剪枝法 设MAX节点的下限为，则其所有的MIN子节点中，其评估值的上限小于等于的节点，其以下部分的搜索都可以停止了，即对这部分节点进行了剪枝。2022/11/18史忠植人工智能：自动推理91n剪枝法 设MIN节点的上限为，则其所有的MAX子节点中，其评估值的下限大于等于的节点，其以下部分的搜索都可以停止了，即对这部分节点进行了剪枝。MAX节点节点MIN节点节点=剪剪枝ABCD-搜索过程搜索过程2022/11/18史忠植人工智能：自动推理92A B CDEFG H I J K L N O M-搜索过程搜索过程MAX节点节点MAX节点节点MIN节点节点终端节点终

48、端节点356521642022/11/18史忠植人工智能：自动推理93MAX节点节点(5,)35652164(6,)(2,)(-,5,5)(-,2,2)(5,)MIN节点节点终端节点终端节点 剪剪枝剪剪枝 剪枝剪枝A B CDEFG H I J K L N O MMAX节点节点-搜索过程搜索过程2022/11/18史忠植人工智能：自动推理94一字棋一字棋-剪枝剪枝2022/11/18史忠植人工智能：自动推理95-剪枝剪枝极大节点的下界为。极小节点的上界为。剪枝的条件：后辈节点的值祖先节点的值时，剪枝后辈节点的 值祖先节点的值时，剪枝简记为：极小极大，剪枝极大极小，剪枝2022/11/18史忠植

49、人工智能：自动推理96当算法给出所选的走步后，不要马上停止搜索，而是在原先估计可能的路径上再往前搜索几步，再次检验会不会出现意外，这是一种增添辅助搜索的方法。对某些博弈的开局阶段和残局阶段，往往总结了一些固定的对弈模式，因此可以利用这些知识编好走步表，以便在开局和结局时使用查表法。只是在进入中盘阶段后，再调用其他有效的搜索算法，来选择最优的走步。-搜索过程搜索过程2022/11/18史忠植人工智能：自动推理972022/11/18史忠植人工智能：自动推理98内容提要内容提要归结演绎推理归结演绎推理归结演绎推理本质上就是一种反证法，它是在归结推理规则的基础上实现的。为了证明一个命题P恒真，它证明

50、其反命题P恒假，即不存在使得P为真的解释。由于量词，以及嵌套的函数符号，使得谓词公式往往有无穷的指派，不可能一一测试P是否为真或假。那么如何来解决这个问题呢？幸运的是存在一个域，即Herbrand域，它是一个可数无穷的集合，如果一个公式基于Herbrand解释为假，则就在所有的解释中取假值。基于Herbrand域，希尔伯特（Herbrand D）给出了重要的定理，为不可满足的公式判定过程奠定了基础。Robinson给出了用于从不可满足的公式推出F的归结推理规则，为定理机械证明取得了重要的突破，使其达到了应用的阶段。2022/11/18史忠植人工智能：自动推理99归结演绎推理归结演绎推理归结证明