人工智能第三章-搜索策略-优秀PPT.ppt

《人工智能第三章-搜索策略-优秀PPT.ppt》由会员分享，可在线阅读，更多相关《人工智能第三章-搜索策略-优秀PPT.ppt（102页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、2022/10/301启发式搜寻启发式搜寻o启发式学问指导启发式学问指导OPEN表排序的一般图搜寻：表排序的一般图搜寻：o全局排序全局排序对对OPEN表中的全部节点排序，表中的全部节点排序，使最有希望的节点排在表首。使最有希望的节点排在表首。oA算法，算法，A*算法（驾驭！）算法（驾驭！）o局部排序局部排序仅对新扩展出来的子节点排序，仅对新扩展出来的子节点排序，使这些新节点中最有希望者能优先取出考察使这些新节点中最有希望者能优先取出考察和扩展；和扩展；o爬山法（了解，对深度优先法的改进）；爬山法（了解，对深度优先法的改进）；2022/10/302 简洁的搜寻策略：简洁的搜寻策略：g(n)0,f

2、(n)=h(n),g(n)0,f(n)=h(n),局部排序局部排序只排序新扩展出来的子节点，即局部排序只排序新扩展出来的子节点，即局部排序 简洁易行，适用于不要求最优解答的问题求解任务。简洁易行，适用于不要求最优解答的问题求解任务。1 1）爬山法）爬山法实现启发式搜寻的最简洁方法。实现启发式搜寻的最简洁方法。类似于人爬山类似于人爬山只要好爬，总是选取最陡处，以求快速登顶。只要好爬，总是选取最陡处，以求快速登顶。求求函函数数极极大大值值问问题题非非数数值值解解法法，依依靠靠于于启启发发式式学学问问，摸摸爽爽性性地地逐逐步向顶峰靠近步向顶峰靠近 适用于能逐步求精的问题。适用于能逐步求精的问题。爬山

3、法特点：爬山法特点：只能向上，不准后退，从而简化了搜寻算法；体现在：只能向上，不准后退，从而简化了搜寻算法；体现在：*从从当当前前状状态态节节点点扩扩展展出出的的子子节节点点（相相当当于于找找到到上上爬爬的的路路径径）中中，将将h(n)h(n)最最小小的的子子节节点点（对对应应于于到到顶顶峰峰最最近近的的上上爬爬路路径径）作作为为下下一一次次考考察察和和扩展的节点，其余子节点全部丢弃。扩展的节点，其余子节点全部丢弃。不需设置不需设置OPENOPEN和和CLOSECLOSE表，因为没有必要保存任何待扩展节点；表，因为没有必要保存任何待扩展节点；爬爬山山法法对对于于单单一一极极值值问问题题（登登单

4、单一一山山峰峰）特特殊殊有有效效而而又又简简便便,对对于于具具有有多极值的问题无能为力多极值的问题无能为力会错登上次高峰而失败：不能到达最高峰。会错登上次高峰而失败：不能到达最高峰。回溯策略和爬山法回溯策略和爬山法 2022/10/303 2 2）回溯策略）回溯策略 可可以以有有效效地地克克服服爬爬山山法法面面临临的的困困难难保保存存了了每每次次扩扩展展出出的的子子节节点点，并并按按h(n)h(n)值值从从小到大排列。小到大排列。相相当当于于爬爬山山的的过过程程中中记记住住了了途途经经的的岔岔路路口口路路径径搜搜寻寻失失败败时时回回溯溯（后后退退），向向另一路径方向搜寻另一路径方向搜寻 回溯策

5、略和爬山法回溯策略和爬山法 2022/10/304 2 2）回溯策略）回溯策略 递归过程递归过程实现回溯策略的有效方式实现回溯策略的有效方式 算算法法就就取取名名为为BACKTRACK(n),BACKTRACK(n),参参数数n n为为当当前前被被扩扩展展的节点，的节点，初次调用时初次调用时n n即为初始状态节点即为初始状态节点s s；分二个部分：分二个部分：*推断当前节点推断当前节点n n的状态，的状态，*作作搜搜寻寻工工作作扩扩展展节节点点n n，递递归归调调用用该该算算法法，处理返回结果。处理返回结果。回溯策略和爬山法回溯策略和爬山法 2022/10/305令令PATHPATH、SNLS

6、NL、n n、n n 为局部变量：为局部变量：PATH-PATH-节点列表，指示解答路径；节点列表，指示解答路径；SNL-SNL-当前节点扩展出的子节点列表；当前节点扩展出的子节点列表；MOVE-FIRST(SNL)-MOVE-FIRST(SNL)-把把SNLSNL表表首首的的节节点点移移出出，作作为为下下一一次次要要加加以以扩扩展展的的节点；节点；n n、n-n-分别指示当前考察和下一次考察的节点。分别指示当前考察和下一次考察的节点。该该递递归归过过程程的的算算法法就就取取名名为为BACKTRACK(n),BACKTRACK(n),参参数数n n为为当当前前被被扩扩展展的的节节点点，算算法的

7、初次调用式是法的初次调用式是BACKTRACK(s),sBACKTRACK(s),s即为初始状态节点。算法的步骤如下：即为初始状态节点。算法的步骤如下：（1 1）若若n n是目标状态节点，则算法的本次调用成功结束，返回空表；是目标状态节点，则算法的本次调用成功结束，返回空表；（2 2）若若n n是失败状态，则算法的本次调用失败结束，返回是失败状态，则算法的本次调用失败结束，返回FAILFAIL；（3 3）扩扩展展节节点点n n，将将生生成成的的子子节节点点置置于于列列表表SNLSNL，并并按按评评价价函函数数f(k)f(k)=h(k)h(k)的值从小到大排序（的值从小到大排序（k k指示子节点

8、）；指示子节点）；（4 4）若若SNLSNL为空，则算法的本次调用失败结束，返回为空，则算法的本次调用失败结束，返回FAILFAIL；（5 5）n=MOVE-FIRST(SNL)n=MOVE-FIRST(SNL)；（6 6）PATH=BACKTRACK(n)PATH=BACKTRACK(n)；（7 7）若若PATH=FAIL,PATH=FAIL,返回到语句（返回到语句（4 4）；）；（8 8）将将nn加到加到PATHPATH表首，算法的本次调用成功结束，返回表首，算法的本次调用成功结束，返回PATHPATH。2022/10/306 2 2）回溯策略）回溯策略 三种失败状态：三种失败状态：不不合

9、合法法状状态态（如如传传教教士士和和野野人人问问题题中中所所述述的那样）的那样）旧旧状状态态重重现现（如如八八数数码码游游戏戏中中某某一一棋棋盘盘布布局的重现，会导致搜寻算法死循环），局的重现，会导致搜寻算法死循环），状状态态节节点点深深度度超超过过预预定定限限度度（例例如如八八数数码码游戏中，指示解答路径不超过游戏中，指示解答路径不超过6 6步）。步）。回溯条件回溯条件 失败状态，由算法第（失败状态，由算法第（2 2）句指示；）句指示；搜搜寻寻进进入入“死死胡胡同同”，由由该该算算法法的的第第(4)(4)句定义。句定义。回溯策略和爬山法回溯策略和爬山法 2022/10/307 2 2）回溯策

10、略）回溯策略 解解答答路路径径的的生生成成从从相相应应于于目目标标状状态态节节点点的的空空表起先，递归返回表起先，递归返回PATHPATH。影响回溯算法效率的关键因素影响回溯算法效率的关键因素回溯次数。回溯次数。回溯回溯搜寻到失败状态时的一种弥补行为，搜寻到失败状态时的一种弥补行为，精精确确选选择择下下一一步步搜搜寻寻考考察察的的节节点点大大幅幅度度削减甚至避开回溯。削减甚至避开回溯。设计好的启发式函数设计好的启发式函数h(n)h(n)是至关重要的。是至关重要的。回溯策略和爬山法回溯策略和爬山法 2022/10/308课堂练习课堂练习:提高题提高题o在应用递归回溯算法解决四皇后的问题中，若按行

11、在应用递归回溯算法解决四皇后的问题中，若按行的序号从小到大摸爽性放置各列的皇后，请画出搜的序号从小到大摸爽性放置各列的皇后，请画出搜寻图，并指出分别从算法第寻图，并指出分别从算法第2步和第步和第4步回溯的次数。步回溯的次数。2022/10/309 定义定义L，为表示清晰起见，为表示清晰起见,L表中只记载皇后所在列表中只记载皇后所在列,皇后所在行可由在皇后所在行可由在L表中的先后位置指示表中的先后位置指示,例如例如L=(1 3)指示两个皇后位置分别为第指示两个皇后位置分别为第1行第行第1列和第列和第2行第行第3列。列。搜寻图(树)如右图所示:共回溯22次,其中算法第2步的回溯18次,算法第4次的

12、回溯4次。2022/10/30103.4 3.4 问题归约和与或图启发式搜寻问题归约和与或图启发式搜寻o问题归约是人求解问题常用的策略：问题归约是人求解问题常用的策略：o把困难的问题变换为若干须要同时处理的较为把困难的问题变换为若干须要同时处理的较为简洁的子问题后再加以分别求解简洁的子问题后再加以分别求解o只有子问题全部解决时，问题才算解决；只有子问题全部解决时，问题才算解决；o问题的解答由子问题的解答联合构成。问题的解答由子问题的解答联合构成。o本节主要内容：本节主要内容：o问题归约的描述（理解）问题归约的描述（理解）o与或图搜寻的基本过程（理解）与或图搜寻的基本过程（理解）o与或图的启发式

13、搜寻（驾驭）与或图的启发式搜寻（驾驭）2022/10/3011问题归约法问题归约法（Problem Reduction Representation）子子问题问题1子子问题问题n原始问题原始问题子问题集本本原原问问题题2022/10/3012o问题归约可以用三元组表示：（问题归约可以用三元组表示：（S S0 0，O O，P P），其中），其中nS S0 0是初始问题，即要求解的问题；是初始问题，即要求解的问题；nP P是本原问题集，其中的每一个问题是不用证是本原问题集，其中的每一个问题是不用证明的，自然成立的，如公理、已知事实等，或明的，自然成立的，如公理、已知事实等，或已证明过的问题；已证明

14、过的问题；nO O是操作算子集，它是一组变换规则，通过一是操作算子集，它是一组变换规则，通过一个操作算子把一个问题化成若干个子问题。个操作算子把一个问题化成若干个子问题。2022/10/3013o问题归约表示方法就是由初始问题动身，运问题归约表示方法就是由初始问题动身，运用操作算子产生一些子问题，对子问题再运用操作算子产生一些子问题，对子问题再运用操作算子产生子问题的子问题，这样始终用操作算子产生子问题的子问题，这样始终进行到产生的问题均为本原问题，则问题得进行到产生的问题均为本原问题，则问题得解。解。2022/10/3014o看如下符号积分问题：看如下符号积分问题：o初始问题初始问题f(x)

15、dxf(x)dxo变换规则变换规则积分规则积分规则o本原问题本原问题可干脆求原函数和积分，可干脆求原函数和积分，如如sin(x)dxsin(x)dx，cos(x)dxcos(x)dx等。等。o全部问题归约的最终目的是产生本原问全部问题归约的最终目的是产生本原问题。题。2022/10/3015符号符号积分分问题（sin3x+x4/(x2+1)）dx=sin3xdx+(x4/(x2+1)dx=-(1-cos2x)dcosx+(x2-1+1/(1+x2)dx=(-dcosx+cos2xdcosx)+(x2dx-dx+(1/(1+x2)dx）=-cosx+cos3x/3+x3/3-x+arctgx20

16、22/10/3016分子分子结构构识别问题 如何区分分子式相同但分子如何区分分子式相同但分子结结构不同的有机化合物成构不同的有机化合物成为为重要而又困重要而又困难难的的问题问题。著名的。著名的专专家系家系统统 DENDRAL能用能用于有效地于有效地识别识别分子分子结结构，构，该该系系统统建立了一套重写建立了一套重写规则规则去去把分子式重写把分子式重写为为原子数原子数较较少的分子式和原子少的分子式和原子间结间结合关系合关系的混合的混合结结构构 2022/10/3017o问题归约的实质：问题归约的实质：o 从目标从目标(要解决的问题要解决的问题)动身逆向推动身逆向推理，建立子问题以及子问题的子问题

17、，理，建立子问题以及子问题的子问题，直至最终把初始问题归约为一个平凡直至最终把初始问题归约为一个平凡的本原问题集合。的本原问题集合。2022/10/3018n应用问题归约策略得到的状态空间图，也称为应用问题归约策略得到的状态空间图，也称为“与或图与或图”n逻辑逻辑“与与”关系关系用圆弧将几条节点间关联弧连接在用圆弧将几条节点间关联弧连接在一起一起n表示问题分解为子问题；表示问题分解为子问题；n子问题的状态联合起来构成问题状态。子问题的状态联合起来构成问题状态。n子问题全部解决才会导致问题的解决；子问题全部解决才会导致问题的解决；n逻辑逻辑“或或”关系：关系：n问题可以有多种分解方式；问题可以有

18、多种分解方式；n问题（子问题）可能激活多个状态变迁操作；问题（子问题）可能激活多个状态变迁操作；n只要一种分解方式或状态变迁操作能导致最终的解答成只要一种分解方式或状态变迁操作能导致最终的解答成功即可；功即可；n导致多个可能的解答。导致多个可能的解答。与或图与或图2022/10/3019o用用AND-ORAND-OR图图把问题归约为子问题替换集合。把问题归约为子问题替换集合。o如，假设问题如，假设问题A A既可通过问题既可通过问题C C1 1与与C C2 2，也可通过问题，也可通过问题C C3 3、C C4 4和和C C5 5，或者由单独求解问题，或者由单独求解问题C C6 6来解决，如下图所

19、示。图中各节来解决，如下图所示。图中各节点表示要求解的问题或子问题。点表示要求解的问题或子问题。与或图与或图2022/10/3020梵塔问题梵塔问题问题描述：问题描述：初始状态下三个盘按初始状态下三个盘按A、B、C依次堆放在依次堆放在1号柱子上；号柱子上；目标状态下三个盘以同样次序依次堆放在目标状态下三个盘以同样次序依次堆放在3号柱子上；号柱子上；盘子的搬移规则：盘子的搬移规则：每次只能搬一个盘子；每次只能搬一个盘子；较大盘不能压放在较小盘之上；较大盘不能压放在较小盘之上；CAB初始状态初始状态(1 1 1)目标目标状态状态(3 3 3)CAB132132与或图与或图2022/10/3021梵

20、塔问题梵塔问题状态空间图状态空间图(1,1,1)(3,3,3)(1,1,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3)(2,2,1)132CAB(2,2,3)123ABC目标目标状态状态(3 3 3)CAB1322022/10/3022梵塔问题梵塔问题状态空间图状态空间图(1,1,1)(3,3,3)(1,1,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3)(1,1,1)(3,1,1)(3,2,1)(2,2,1)(3,1,1)(3,2,1)(1,2,3)(1,3,3)(2,2,3)(1,2,3)(1,3,3)(3,3,3)2022/10/30

21、23梵塔问题梵塔问题(1,1,1)(3,3,3)(1,1,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3)(1,1,1)(3,1,1)(3,2,1)(2,2,1)(3,1,1)(3,2,1)(1,2,3)(1,3,3)(2,2,3)(1,2,3)(1,3,3)(3,3,3)123456789子问题间有交互作用，子问题间有交互作用，问题分解留意正确的依次问题分解留意正确的依次2022/10/3024与或图搜寻与或图搜寻o与或图与或图视为对视为对一般图一般图(或图或图)的扩展；的扩展；n引入引入K-连接连接o父子节点父子节点间可以存在间可以存在“与与”关系关系n结果结果解

22、图解图。o解答路径往往不复存在，代之以广义的解路径解答路径往往不复存在，代之以广义的解路径解图解图。问题归约求解问题的过程问题归约求解问题的过程表示为与或图搜寻表示为与或图搜寻2022/10/3025与或图搜寻与或图搜寻o1)与或图搜寻的基本概念与或图搜寻的基本概念o1、K-连接连接o从父节点到从父节点到K个子节点的连接，子节点间有个子节点的连接，子节点间有“与与”关系；关系；o以圆弧指示这些子节点间的以圆弧指示这些子节点间的“与与”关系；关系；o一个父节点可以有多个一个父节点可以有多个K-连接连接oK-连接间连接间”或或”关系关系o当全部的当全部的K都等于都等于1时，与或图蜕化为一般图（或图

23、）。时，与或图蜕化为一般图（或图）。3个子节点个子节点2个子节点个子节点2022/10/3026与或图搜寻与或图搜寻o1)与或图搜寻的基本概念与或图搜寻的基本概念o2、根、叶、终节点、根、叶、终节点o根节点根节点无父节点的节点无父节点的节点o用于指示问题初始状态（和一般图一样）用于指示问题初始状态（和一般图一样）o叶节点叶节点无子节点的节点无子节点的节点o终节点终节点能用于联合表示目标状态的节点能用于联合表示目标状态的节点o终节点必定是叶节点，反之不然；终节点必定是叶节点，反之不然；o目标状态目标状态终结点的集合。终结点的集合。2022/10/3027一些关于与或图的术语一些关于与或图的术语H

24、MBCDEFGAN父节点父节点与节与节点点弧线弧线或节或节点点子节子节点点终节点终节点2022/10/3028与或图搜寻与或图搜寻o1)与或图搜寻的基本概念与或图搜寻的基本概念o3、解图的生成、解图的生成o解图纯粹是一种解图纯粹是一种“与与”图图o解图中，节点或节点组间不存在解图中，节点或节点组间不存在“或或”关关系；系；o全部叶节点都是终节点全部叶节点都是终节点2022/10/3029与或图搜寻与或图搜寻o1)与或图搜寻的基本概念与或图搜寻的基本概念o3、解图的生成、解图的生成o自根节点起先选自根节点起先选K-连接连接;o从该从该K-连接指向的每个子连接指向的每个子节点动身，再选一节点动身，

25、再选一K-连接连接;o如此反复进行，直到全部如此反复进行，直到全部K-连接都指向终节点为止连接都指向终节点为止.2022/10/30302022/10/3031与或图搜寻与或图搜寻o1)与或图搜寻的基本概念与或图搜寻的基本概念o3、解图的生成、解图的生成o解图纯粹是一种解图纯粹是一种“与与”图图o解图中，节点或节点组间不存在解图中，节点或节点组间不存在“或或”关系；关系；o全部叶节点都是终节点全部叶节点都是终节点o与或图中存在与或图中存在“或或”关系，搜寻到多个解图；关系，搜寻到多个解图；2022/10/3032与或图搜寻与或图搜寻o2)解图、解图代价、能解节点和不能解节点的定义解图、解图代价

26、、能解节点和不能解节点的定义o(1)解图解图与或图（记为与或图（记为G）任一节点（记为）任一节点（记为n）到终）到终节点集合的解图（记为节点集合的解图（记为G）是）是G的子图。的子图。o(1)若若n是终节点，则是终节点，则G就由单一节点就由单一节点n构成；构成；o(2)若若n有一有一K-连接指向子节点连接指向子节点n1，n2，nk,且每个子且每个子节点都有到终节点集合的解图，则节点都有到终节点集合的解图，则G由该由该k-连接和全部连接和全部这些相应于子节点的解图构成这些相应于子节点的解图构成;o(3)否则不存在否则不存在n到终节点集合的解图。到终节点集合的解图。2022/10/3033与或图搜

27、寻与或图搜寻o2)解图、解图、解图代价解图代价、能解节点和不能解节点的定义、能解节点和不能解节点的定义n(2)解图代价解图代价 以以C(n)指示节点指示节点n到到终节点集合终节点集合解图解图的代价，并令的代价，并令K-连接的代价就为连接的代价就为K,则则 o(1)若若n是终节点，则是终节点，则C(n)=0；o(2)若若n有一有一K-连接连接指向子节点指向子节点n1，n2，nk,且这且这些子节点每个都有到终节点集合的解图些子节点每个都有到终节点集合的解图,则则C(n)=K+C(n1)+C(n2)+C(nk)352022/10/3034与或图搜寻与或图搜寻o2)解图、解图代价、解图、解图代价、能解

28、节点能解节点和和不能解节点不能解节点的定义的定义n(3)能解节点能解节点 o(1)终节点是能解节点终节点是能解节点；o(2)若节点若节点n有有一一K-连接连接指向子节点指向子节点n1，n2，nk,且这些且这些子节点都是能解节点子节点都是能解节点，则，则n是能解节点；是能解节点；能解节点能解节点能解节点能解节点能解节点能解节点能解节点能解节点2022/10/3035与或图搜寻与或图搜寻o2)解图、解图代价、解图、解图代价、能解节点能解节点和和不能解节点不能解节点的定义的定义n(4)不能解节点不能解节点o(1)非终节点的叶节点是不能解节点非终节点的叶节点是不能解节点；o(2)若节点若节点n的的每一

29、个每一个K-连接连接都都至少至少指向一个不能解指向一个不能解节点节点，则，则n是不能解节点。是不能解节点。能解节点能解节点不能解节点不能解节点能解节点能解节点不能解节点不能解节点不能解节点不能解节点2022/10/3036与或图的启发式搜寻与或图的启发式搜寻o与或图中搜寻的是解图，不是解答路径；与或图中搜寻的是解图，不是解答路径；o评价函数评价函数f(n)=h(n)oh(n)是对是对n到终节点集合解图最小解图代价的估计；到终节点集合解图最小解图代价的估计；o与或图中存在与或图中存在“或或”关系，会有多个候选的局部解图；关系，会有多个候选的局部解图；o选择局部解图中可能代价最小的用于下一步搜寻。

30、选择局部解图中可能代价最小的用于下一步搜寻。o1)（局部）解图代价（局部）解图代价f(n0)on0初始状态节点初始状态节点o递归地计算出递归地计算出f(n0),比干脆用比干脆用h(n0)估算更为精确。估算更为精确。o父节点父节点n的的K-连接指向的子节点：连接指向的子节点：n1，n2，nkof(n)=K+h(n1)+h(n2)+h(nk)，代替，代替h(n)2022/10/3037与或图的启发式搜寻与或图的启发式搜寻o2)AO*算法算法o符号说明：符号说明：oG-搜寻图；搜寻图；oG-被选中的待扩展局部解图；被选中的待扩展局部解图；oLGS-待扩展局部解图集；待扩展局部解图集；on0-根节点，

31、即初始状态节点；根节点，即初始状态节点；on-被选中的待扩展节点；被选中的待扩展节点；ofi(n0)-第第i个待扩展局部解图的可能代价。个待扩展局部解图的可能代价。2022/10/3038与或图的启发式搜寻与或图的启发式搜寻o2)AO*算法算法o算法划分二个阶段：算法划分二个阶段：o1、初始化、初始化 o建立只包含初始状态节点建立只包含初始状态节点n0的搜寻图的搜寻图G:=n0；o待扩展局部解图集待扩展局部解图集LGS:=；o2、搜寻循环、搜寻循环o选择和扩展选择和扩展LGS中的局部解图；中的局部解图；o精化新局部解图代价的估计；精化新局部解图代价的估计；o传递节点的能解性。传递节点的能解性。

32、2022/10/3039与或图的启发式搜寻与或图的启发式搜寻o2、搜寻循环、搜寻循环o选择和扩展选择和扩展LGS中的局部解图；中的局部解图；o选择选择LGS中中fi(n0)最小的待扩展解图最小的待扩展解图G；o随机选择随机选择G中一个非终节点的叶节点作为中一个非终节点的叶节点作为n；o扩展扩展no建立建立K-连接，子节点连接，子节点ni并加入并加入G；o计算子节点计算子节点ni的的f(ni)=h(ni)o若若n存在存在j个个K-连接连接oLGS中删除中删除Go将将j个新的局部解图加入个新的局部解图加入LGS;2022/10/3040与或图的启发式搜寻与或图的启发式搜寻o2、搜寻循环、搜寻循环o

33、选择和扩展选择和扩展LGS中的局部解图；中的局部解图；o精化新局部解图代价的估计精化新局部解图代价的估计o用公式用公式f(n)=K+h(n1)+h(n2)+h(nk)取取代原先的代原先的f(n);o递归地作用到初始节点递归地作用到初始节点n0；o传递新局部解图中节点的能解性传递新局部解图中节点的能解性o标记作为终节点的子节点为能解节点；标记作为终节点的子节点为能解节点；o递归地传递节点的能解性到初始节点递归地传递节点的能解性到初始节点n0。f(n)=h(n)2022/10/30412022/10/3042与或图的启发式搜寻与或图的启发式搜寻o2)AO*算法算法oAO*算法应用例算法应用例o搜寻

34、过程中，启发式函数搜寻过程中，启发式函数h(ni)的的o 估算如下：估算如下：oh(n0)=3oh(n1)=2oh(n2)=1oh(n3)=1oh(n4)=4oh(n5)=2oh(n6)=2oh(n7)=1oh(n8)=1oh(n13)=30123546 7 891011 121314 15161718 19 202022/10/3043初始化初始化候选的待扩展局部解图集候选的待扩展局部解图集LGS:0302022/10/3044012354循环循环1候选的待扩展局部解图集候选的待扩展局部解图集LGS:32114202022/10/3045012354循环循环1候选的待扩展局部解图集候选的待扩

35、展局部解图集LGS:321142031201235432114202022/10/3046012354循环循环1候选的待扩展局部解图集候选的待扩展局部解图集LGS:10211420512f(n)=K+h(n1)+h(n2)+h(nk)取代原先的取代原先的f(n);f1(n0)=2+h(n1)+h(n2)=5f2(n0)=3+h(n3)+h(n4)+h(n5)=102022/10/3047012354循环循环2候选的待扩展局部解图集候选的待扩展局部解图集LGS:1021142056 7 8211122022/10/3048012354循环循环2候选的待扩展局部解图集候选的待扩展局部解图集LGS:

36、1021142057 811012215623422022/10/3049012354循环循环2候选的待扩展局部解图集候选的待扩展局部解图集LGS:1041142077 8110123166234225252022/10/3050012354候选的待扩展局部解图集候选的待扩展局部解图集LGS:1041142077 81101231662342131430循环循环32022/10/3051012354候选的待扩展局部解图集候选的待扩展局部解图集LGS:1041142077 81101261965342131430循环循环33622022/10/3052012354循环循环4候选的待扩展局部解图集

37、候选的待扩展局部解图集LGS:1041142077 811012619653421314301402022/10/3053012354循环循环5候选的待扩展局部解图集候选的待扩展局部解图集LGS:1041142077 811012619653421314301401502022/10/3054012354循环循环5候选的待扩展局部解图集候选的待扩展局部解图集LGS:1051142087 812012619653421314301401504712022/10/3055012354循环循环6候选的待扩展局部解图集候选的待扩展局部解图集LGS:1051142087 8120126196534213

38、1430140150902022/10/3056012354搜寻成功！搜寻成功！候选的待扩展局部解图集候选的待扩展局部解图集LGS:1051142087 81201261965342131430140150902022/10/3057与或图的启发式搜寻与或图的启发式搜寻o4）算法应用的若干问题）算法应用的若干问题o1、从局部解图、从局部解图G中选择加以扩展的节点中选择加以扩展的节点no与或图搜寻的是解图而非解路径；与或图搜寻的是解图而非解路径；o选择选择f(n)=h(n)的值最小的节点的值最小的节点n加以扩展并不加以扩展并不确定会加速搜寻过程；确定会加速搜寻过程；o应选择导致解图代价发生较大变

39、更的节点应选择导致解图代价发生较大变更的节点n优先优先加以扩展；加以扩展；o使搜寻的留意力快速地聚焦到实际代价较小的使搜寻的留意力快速地聚焦到实际代价较小的候选解图上；候选解图上；o简洁状况下，可随机选择加以扩展的节点。简洁状况下，可随机选择加以扩展的节点。2022/10/3058与或图的启发式搜寻与或图的启发式搜寻o4）算法应用的若干问题）算法应用的若干问题o2、算法、算法AO*与与A*的比较的比较o解图解图解答路径，解答路径，o估计代价最小的局部解图加以优先扩展估计代价最小的局部解图加以优先扩展OPEN表中表中f(n)最小的节点；最小的节点；o只考虑评价函数只考虑评价函数f(n)=h(n)

40、同时计算重量同时计算重量g(n)和和h(n)，o应用应用LGS存放待扩展局部解图，并依据存放待扩展局部解图，并依据fi(n0)值值排序排序应用应用OPEN表和表和CLOSE表分别存放待表分别存放待扩展节点和已扩展节点，并依据扩展节点和已扩展节点，并依据f(n)值排序值排序OPEN表。表。2022/10/3059与或图的启发式搜寻与或图的启发式搜寻o4）算法应用的若干问题）算法应用的若干问题o3、解图代价的重复计算、解图代价的重复计算o某些子节点可能会有多个父节点；某些子节点可能会有多个父节点；o这种子节点到终节点集合的解图代价在计算自这种子节点到终节点集合的解图代价在计算自根节点根节点n0动身

41、的解图时被重复累计。动身的解图时被重复累计。17 817 814 1512517 8142216241182022/10/3060博弈博弈 n博弈供应了一个可构造的任务领域，在这个领博弈供应了一个可构造的任务领域，在这个领域中，具有明确的成功和失败；域中，具有明确的成功和失败；n博弈问题对人工智能探讨提出了严峻的挑战。博弈问题对人工智能探讨提出了严峻的挑战。例如，如何表示博弈问题的状态、博弈过程和例如，如何表示博弈问题的状态、博弈过程和博弈学问等。博弈学问等。o这里讲的博弈是这里讲的博弈是二人博弈二人博弈，二人零和二人零和、全信息全信息、非偶然博弈非偶然博弈，博弈双方的利益是，博弈双方的利益是

42、完全对立完全对立的。的。2022/10/3061n所谓所谓“二人零和二人零和”，是指在博弈中只有，是指在博弈中只有“敌、我敌、我”二方。二方。且双方的利益完全对立，其赢得函数之和为零，即且双方的利益完全对立，其赢得函数之和为零，即n 1+2=0n 式中，式中，1为我方赢得为我方赢得(利益利益)；2为敌方赢得为敌方赢得(利益利益)。n 即：博弈的双方有三种结局：即：博弈的双方有三种结局：n (1)我胜：我胜：10；敌负：；敌负：2=-10。n (2)我负：我负：1=-20。n (3)平局：平局：1=0，2=0。n 博弈问题对人工智能探讨提出了严峻的挑战。例如，博弈问题对人工智能探讨提出了严峻的挑

43、战。例如，如何表示博弈问题的状态、博弈过程和博弈学问等。如何表示博弈问题的状态、博弈过程和博弈学问等。2022/10/3062n所谓所谓“全信息全信息”，是指博弈双方都了解当前的，是指博弈双方都了解当前的格局及过去的历史。格局及过去的历史。n所谓所谓“非偶然非偶然，是指博弈双方都可依据得失大，是指博弈双方都可依据得失大小进行分析，选取我方赢得最大，敌方赢得最小进行分析，选取我方赢得最大，敌方赢得最小的对策，而不是偶然的随机对策。小的对策，而不是偶然的随机对策。2022/10/3063（1 1）对垒的双方）对垒的双方MAXMAX和和MINMIN轮番实行行动，博轮番实行行动，博弈的结果只能有弈的结

44、果只能有3 3种状况：种状况：MAXMAX胜、胜、MINMIN败；败；MAXMAX败，败，MINMIN胜；和局。胜；和局。（2 2）在对垒过程中，任何一方都了解当前的）在对垒过程中，任何一方都了解当前的格局和过去的历史。格局和过去的历史。（3 3）任何一方在实行行动前都要依据当前的）任何一方在实行行动前都要依据当前的实际状况，进行得失分析，选择对自己最实际状况，进行得失分析，选择对自己最为有利而对对方最不利的对策，在不存在为有利而对对方最不利的对策，在不存在“碰运气碰运气”的偶然因素，即双方都很理智的偶然因素，即双方都很理智地确定自己的行动。地确定自己的行动。这类博弈如一字棋、象棋、围棋等。博

45、弈的特点博弈的特点博弈的特点博弈的特点 2022/10/3064o另外一种博弈是机遇性博弈，是指不行预料另外一种博弈是机遇性博弈，是指不行预料性的博弈，如掷硬币游戏等。性的博弈，如掷硬币游戏等。2022/10/3065例：例：o假设有七枚钱币，任一选手只能将已分好的假设有七枚钱币，任一选手只能将已分好的一堆钱币分成两堆个数不等的钱币，两位选一堆钱币分成两堆个数不等的钱币，两位选手轮番进行，直到每一堆都只有一个或两个手轮番进行，直到每一堆都只有一个或两个钱币，不能再分为止，哪个选手遇到不能再钱币，不能再分为止，哪个选手遇到不能再分的状况，则为输。分的状况，则为输。2022/10/3066o用数字

46、序列加上一个说明表示一个状态，其中数字用数字序列加上一个说明表示一个状态，其中数字表示不同堆中钱币的个数，说明表示下一步由谁来表示不同堆中钱币的个数，说明表示下一步由谁来分，分，o如如（7 7，MINMIN）表示只有一个由七枚钱币组成的堆，表示只有一个由七枚钱币组成的堆，由由MINMIN走，走，MINMIN有有3 3种可供选择的分法，即种可供选择的分法，即n（6 6，1 1，MAXMAX），（），（5 5，2 2，MAXMAX），（），（4 4，3 3，MAXMAX），），o其中其中MAXMAX表示另一选手，不论哪一种方法，表示另一选手，不论哪一种方法，MAXMAX在它在它的基础上再作符合要求

47、的划分。的基础上再作符合要求的划分。2022/10/3067o下图已将双方可能的方案完全表示出来了，无下图已将双方可能的方案完全表示出来了，无论论MINMIN起先时怎么走法，起先时怎么走法，MAXMAX总可以获胜，取胜总可以获胜，取胜的策略用双线箭头表示。的策略用双线箭头表示。2022/10/3068o实际的状况没有这么简洁，任何一种棋都不行实际的状况没有这么简洁，任何一种棋都不行能将全部状况列尽，因此，只能模拟人能将全部状况列尽，因此，只能模拟人“向前向前看几步看几步”，然后做出决策，确定自己走哪一步，然后做出决策，确定自己走哪一步最有利。最有利。o只能给出几层走法，然后依据确定的估算方法，

48、只能给出几层走法，然后依据确定的估算方法，确定走哪一步棋。确定走哪一步棋。o在双人完备信息博弈过程中，双方都希望自己在双人完备信息博弈过程中，双方都希望自己能够获胜。因此当一方走步时，都是选择对自能够获胜。因此当一方走步时，都是选择对自己最有利，而对对方最不利的走法。己最有利，而对对方最不利的走法。2022/10/3069o假设博弈双方为假设博弈双方为MAXMAX和和MINMIN。在博弈的每一步，可。在博弈的每一步，可供他们选择的方案都有很多种。供他们选择的方案都有很多种。o从从MAXMAX的观点看，可供自己选择的方案之间是的观点看，可供自己选择的方案之间是“或或”的关系，缘由是主动权在自己手

49、里，选择哪个的关系，缘由是主动权在自己手里，选择哪个方案完全由自己确定，可供自己选择的方案之间方案完全由自己确定，可供自己选择的方案之间是是“或或”的关系，而对那些可供的关系，而对那些可供MINMIN选择的方案之选择的方案之间是间是“与与”的关系，这是因为主动权在的关系，这是因为主动权在MINMIN手中，手中，任何一个方案都可能被任何一个方案都可能被MINMIN选中，选中，MAXMAX必需防止那必需防止那种对自己最不利的状况出现。种对自己最不利的状况出现。2022/10/3070o下图是把双人博弈过程用图的形式表示出来，下图是把双人博弈过程用图的形式表示出来，这样就可以得到一棵这样就可以得到一

50、棵AND-ORAND-OR树，这种树，这种AND-ORAND-OR树称为博弈树。树称为博弈树。o在博弈树中，那些下一步该在博弈树中，那些下一步该MAXMAX走的节点称走的节点称为为MAXMAX节点，而下一步该节点，而下一步该MINMIN走的节点称为走的节点称为MINMIN节点。节点。2022/10/3071o下图下图 所示是向前看两步，共四层的博弈树，用所示是向前看两步，共四层的博弈树，用表示表示MAXMAX，用用表示表示MINMIN，端节点上的数字表示它对应的估价函数的值。，端节点上的数字表示它对应的估价函数的值。在在MINMIN处用圆弧连接，用处用圆弧连接，用0 0表示其子节点取估值最小的