人工智能原理搜索技术上优秀PPT.ppt

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

1、人工智能原理人工智能原理第第2章章 搜寻技术搜寻技术（上）（上）1本章内容2.1 搜寻与问题求解2.2 无信息搜寻策略2.3 启发式搜寻策略2.4 局部搜寻算法2.5 约束满足问题2.6 博弈搜寻参考书目附录 A*算法可接受性的证明第2章 搜寻技术22.1 搜寻与问题求解2.1.1 问题与问题的解2.1.2 问题实例2.1.3 搜寻策略第2章 搜寻技术3搜寻与问题求解搜寻与问题求解问题求解过程是搜寻答案(目标)的过程/所以问题求解技术也叫搜寻技术通过对状态空间的搜寻而求解问题的技术问题求解智能体是一种基于目标的智能体在找寻到达目标的过程中，当智能风光对多个未知的选项时，首先检验各个不同的导致已

2、知评价的状态的可能行动序列，然后选择最佳序列这个过程就是搜寻第2章 搜寻技术42.1.1 2.1.1 问题与问题的解问题与问题的解问题可以形式化地定义为4个组成部分智能体的初始状态(即搜寻的起先)后继函数智能体实行的可能行动的描述，通常为/初始状态和后继函数隐含地定义了问题的状态空间/状态空间中的一条路径是通过行动序列连接起来的一个状态序列目标测试检查给定的状态是不是目标路径耗散函数每条路径都有一个数值化的耗散值，反映了性能度量/求解问题的代价第2章 搜寻技术5问题的解问题的解问题的解就是初始状态到目标状态的路径解的优劣由路径耗散函数量度(代价)最优解就是路径耗散函数值最小的路径上述解题过程把

3、解决一个问题的过程描述出来，称之为解题学问的过程性表示过程性学问与陈述性学问相对搜寻过程解题的特点没有干脆的方法(公式)可以求解，而是一步一步的探究第2章 搜寻技术6状态空间状态空间数据基：代表了所要解决的问题，有初始状态，可能有目标状态也可能没有状态空间：在解题过程中的每一时刻，数据基都处于确定的状态，数据基全部可能状态的集合称为状态空间有向图：若把每个状态看成一个节点，则整个状态空间是一个有向图/该图不确定全连通，即从某些状态不确定能到达另外一些状态第2章 搜寻技术7问题的可解性问题的可解性可解的：在每个连通部分，每个弧代表一个运算符，将状态变更/假如从代表初始状态的节点动身，有一条路径通

4、向目标状态，则称此目标状态所代表的问题在当前初始状态下是可解的搜寻空间：在解题过程中达到过的全部状态的集合，称为搜寻空间不同于状态空间，搜寻空间只是其中一部分状态空间和搜寻空间都属于过程性学问表示第2章 搜寻技术82.1.2 2.1.2 问题实例问题实例玩具问题八数码游戏(九宫图)河内塔八皇后问题真空吸尘器世界现实问题旅行商问题超大规模集成电路的布局自动装配排序/蛋白质设计互联网搜寻第2章 搜寻技术9八数码游戏八数码游戏八数码游戏：1-8数字(棋子)/9个方格(棋盘格)/1个空格可用如下形式的规则来表示数字通过空格进行移动：共24条规则=4角*2+4边*3+1中间*4搜寻依次举例：(1)优先移

5、动行数小的棋子(数字)(2)同一行中优先移动列数大的棋子约束规则：不使离开既定位置的数字数增加第2章 搜寻技术10八数码游戏的搜寻树八数码游戏的搜寻树第2章 搜寻技术既定位置=终态11八数码问题形式化八数码问题形式化初始状态初始状态向量规定向量中各重量对应的位置，各位置上的初始数字后继函数移动规则依据某条规则移动数字，将得到的新向量目标测试新向量是否是目标状态(也是向量形式)路径耗散函数每次移动代价为1第2章 搜寻技术12河内塔河内塔(1)(1)河内塔问题：n个大小不等的圆盘从一个柱子移到另一个柱子，共有3个柱子(n阶河内塔问题)约束：从第1根柱子移动到第3根柱子上去，利用第2根柱子/每次移动

6、1个盘子，且移动过程必需是小盘落大盘描述：设每个状态为(a1,a2,a3,an),ai=1,2,3表示第i个盘子在第1/2/3根柱子上第2章 搜寻技术13河内塔河内塔(2)(2)递归定义：(a1,a2,a3,an)为n阶河内塔的状态集合，则(a1,a2,a3,an,1),(a1,a2,a3,an,2),(a1,a2,a3,an,3)是n+1阶河内塔的状态集合1阶河内塔有3个状态，2阶河内塔有9个状态，n阶河内塔有3n个状态，给出1/2/3阶河内塔的状态图第2章 搜寻技术14河内塔问题图解河内塔问题图解第2章 搜寻技术15河内塔问题形式化河内塔问题形式化初始状态初始状态向量规定向量中各重量对应全

7、部n个盘子，位置上数字代表3个柱子之一后继函数移动规则依据约束条件给出的各状态的后继状态目标测试新向量是否是目标状态(也是向量形式)路径耗散函数每移动一个盘子的代价为1第2章 搜寻技术16河内塔问题求解河内塔问题求解求最短路径问题：状态图中从三角形1个顶点走到另一个顶点结论：(1)假如初始状态或目标状态在三角形顶点上，则最短路径唯一；(2)对于随意2个状态，最短求解路径至多为2条。(中国某高校探讨生证明)求解过程对状态空间的搜寻以2阶河内塔为例第2章 搜寻技术17河内塔问题的搜寻树河内塔问题的搜寻树第2章 搜寻技术1,12,13,11,12,31,13,23,32,12,2 3,12,21,3

8、2,13,32,33,31,21,12,21,23,13,3 2,23,21,31,118求解过程求解过程树搜寻树搜寻求解问题的过程运用搜寻树形式每个状态对应搜寻树中一个节点根节点对应于初始状态每次从搜寻树的上层节点动身，依据约束条件进入下一个可能的状态，即绽开新的一层树节点节点扩展节点绽开的依次即代表了不同的搜寻策略当绽开的节点为目标状态时，就找到了问题的一个解第2章 搜寻技术192.1.3 2.1.3 搜寻策略搜寻策略探讨搜寻过程考虑的若干问题(1)有限搜寻还是无限搜寻(2)已知目标还是未知目标(3)目标或目标+路径(4)有约束还是无约束(5)数据驱动(向前搜寻)还是目标驱动(6)单向搜寻

9、还是双向搜寻第2章 搜寻技术20搜寻的分类搜寻的分类搜寻过程的分类：状态空间搜寻(图搜寻方式)，问题空间搜寻(层次方法)，博弈空间搜寻无信息搜寻与启发式搜寻启发式：利用中间信息改进限制策略启发式：(1)任何有助于找到问题的解，但不能保证找到解的方法是启发式方法(2)有助于加速求解过程和找到较优解的方法是启发式方法启发式也叫启发函数第2章 搜寻技术21搜寻算法的性能搜寻算法的性能4种途径来评价搜寻算法的性能完备性当问题有解时，算法是否保证找到一个解最优性算法是否能找到一个最优解(路径耗散函数值最小的路径)时间困难性找到一个解须要花费多少时间空间困难性在搜寻过程中须要占用多少内存第2章 搜寻技术2

10、2性能量度性能量度时空困难性的量度由状态空间图的大小来衡量/相关度量如下：分支因子 b(每次绽开的平均节点个数)目标节点的深度 d路径的最大长度 m搜寻深度限制 l搜寻耗散第2章 搜寻技术232.2 无信息搜寻策略2.2.1 广度优先搜寻2.2.2 深度优先搜寻和深度有限搜寻2.2.3 叠代深化深度优先搜寻2.2.4 无信息搜寻策略性能比较2.2.5 图搜寻算法第2章 搜寻技术24盲目搜寻策略盲目搜寻策略无信息搜寻也称盲目搜寻：没有任何附加信息，只有生成后继和区分目标与非目标状态有5种盲目搜寻策略广度优先搜寻代价一样搜寻深度优先搜寻深度有限搜寻迭代深化深度优先搜寻第2章 搜寻技术252.2.1

11、 2.2.1 广度优先搜寻广度优先搜寻广度优先搜寻过程：首先扩展根节点接着扩展根节点的全部后继节点然后再扩展后继节点的后继，依此类推在下一层任何节点扩展之前搜寻树上的本层深度的全部节点都已经被扩展广度优先搜寻可以调用树搜寻算法(Tree-Search)实现其参数fringe(边缘/扩展分支)为先进先出队列FIFO第2章 搜寻技术26树搜寻算法树搜寻算法(1)(1)function Tree-Search(problem,fringe)return solution/failure(initial fringe=empty,mode=FIFO)fringeInsert(Make-Node(Ini

12、tial-Stateproblem),fringe)do while(1)if fringe=Empty then return failurenodeRemove-First(fringe)if Statenode=Goal then return Solution(node)fringeInsert-All(Expend(node,problem),fringe)第2章 搜寻技术27树搜寻算法树搜寻算法(2)(2)关键在于如何扩展节点function Expend(node,problem)return set of nodessuccessorsthe empty setfor each

13、 in Successor-Findproblem(Statenode)dosnew Node/StatesresultParent-Nodes=node/Actions=actionPath-Costs=Path-Costnode+Step-Costnode,action,sDepthsDepthnode+1add s to successorsreturn successors第2章 搜寻技术28广度优先搜寻的性能广度优先搜寻的性能在上述算法中，广度优先搜寻以Tree-Search(problem,FIFO-Queue)调用树搜寻算法从4种度量来评价广度优先搜寻：完备性总能找到一个解假如每

14、步扩展的耗散相同时，广度优先搜寻能找到最优解内存消耗是比执行时间消耗更大的问题指数级的时间消耗(空间和时间消耗的例子参见p60图3.11)第2章 搜寻技术292.2.2 2.2.2 深度优先搜寻和深度有限搜寻深度优先搜寻和深度有限搜寻深度优先搜寻过程：总是扩展搜寻树的当前扩展分支(边缘)中最深的节点搜寻干脆伸展到搜寻树的最深层，直到那里的节点没有后继节点那些没有后继节点的节点扩展完毕就从边缘中去掉然后搜寻算法回退下一个还有未扩展后继节点的上层节点接着扩展搜寻算法参见深度有限搜寻算法(l=)第2章 搜寻技术30深度优先搜寻的性能深度优先搜寻的性能深度优先搜寻通过后进先出队列LIFO(栈)调用Tr

15、ee-Search实现/通常运用递归函数实现，依次对当前节点的子节点调用该函数性能：内存需求少如分支因子=b/最大深度=m的状态空间深度优先搜寻只须要存储bm+1个节点(比较广度优先O(bd+1)不是完备的/不是最优的最坏状况下时间困难性也很高O(bm)第2章 搜寻技术31深度有限搜寻深度有限搜寻深度优先搜寻的无边界问题可以通过供应一个预先设定的深度限制l来解决深度=l的节点当作无后继节点看待虽然解决了无限路径问题，但假如ll则深度优先搜寻也不是最优的时间困难度O(bl)空间困难度O(bl)深度优先搜寻可看作是一种特例即l=第2章 搜寻技术32非递归的深度有限搜寻算法非递归的深度有限搜寻算法f

16、unction Depth-Limited-Search(problem,fringe,limit)return solution/failure/cutofffringeInsert(Make-Node(Initial-Stateproblem),fringe)(mode=LIFO)do while(1)if fringe=Empty then return failurenodeRemove-First(fringe)if Statenode=Goal then return Solution(node)else if Depthnode=limit then return cutoffe

17、lse fringeInsert-All(Expend(node,problem),fringe)第2章 搜寻技术33搜寻步数的限制搜寻步数的限制上面算法中可能有两类失败cutoff表示到达了有限深度而无解failure表示一般的返回值无解有时深度有限搜寻基于问题本身的学问，如状态空间的直径即问题求解的最大步数但对于大多数问题，不到问题解决时是无法知道求解步数的限制第2章 搜寻技术342.2.3 2.2.3 叠代深化深度优先搜寻叠代深化深度优先搜寻假如每次变更限制深度，多次调用深度有限搜寻算法，就得到了叠代深化深度优先搜寻算法其深度限制依次为0/1/2这样，当搜寻到达最浅的目标节点深度时就可以

18、发觉目标节点这种搜寻结合了广度优先和深度优先两种算法的优点(算法见p63)分支因子有限时是完备的/路径耗散是节点深度的非递增函数时是最优的空间需求为O(bd)/时间困难性为O(bd)第2章 搜寻技术35状态的生成状态的生成叠代深化搜寻中因为多次重复搜寻，因此部分状态被多次生成，看起来很奢侈但是因为在分支因子比较平衡的搜寻树中，多数节点都在最底层(即叶子节点)，所以上层节点的多次生成影响不是很大/与广度优先搜寻相比，效率还是更高一般来讲，当搜寻空间很大而解的深度未知时，叠代深化搜寻是一个首选的无信息搜寻方法第2章 搜寻技术362.2.4 2.2.4 无信息搜寻策略比较无信息搜寻策略比较第2章 搜

19、寻技术评价标准广度优先 代价一致 深度优先 深度有限 叠代深入 双向搜索是否完备时间空间是否最优 是 A 是 A/B 否 否 是 A 是 A/D O(bd+1)O(bC/e)O(bm)O(bl)O(bd)O(bd/2)O(bd+1)O(bC/e)O(bm)O(bl)O(bd)O(bd/2)是 C 是 否 否 是 C 是 C/D 关于A/B/C/D的说明：A假如b有限则是完备的/B单步耗散e则是完备的/C假如单步耗散都是相同的则是最优的/D两个方向上都运用广度优先搜寻372.2.5 2.2.5 图搜寻算法图搜寻算法已经看到搜寻过程中会出现重复的状态扩展，应当避开/假如算法不检测重复状态的话，有可

20、能使一个原来可解的问题变为不行解检测就是把要扩展的节点与已扩展的节点进行比较，把遇到的相同状态去掉所以要记录已经扩展的节点引入两个表存储已扩展的节点closed表和未扩展的节点open表(即前述fringe)新算法称为图搜寻算法第2章 搜寻技术38图搜寻算法图搜寻算法第2章 搜寻技术function Graph-Search(problem,fringe)return solution or failureclosedempty setfringeInsert(Make-Node(Initial-Stateproblem),fringe)do while(1)if fringe=Empty t

21、hen return failurenodeRemove-First(fringe)if Statenode=Goal then return Solution(node)if Statenode!CLOSED then add Statenode to closed fringeInsert-All(Expend(node,problem),fringe)39图搜寻算法的性能图搜寻算法的性能由树到图：存在不同分支节点的合并图搜寻算法与树搜寻算法比较：只是增加了对绽开节点的推断，因此由不同的待扩展节点排列方式而形成的搜寻策略(如广度优先和深度优先)的性能照旧同树搜寻算法对于含很多重复状态的问题

22、，其搜寻效率比树搜寻算法有效很多探讨参见p67第2章 搜寻技术40例子：例子：“农夫过河农夫过河”问题搜寻问题搜寻农夫过河问题用向量表示在河岸两边的状况0表示此岸/1表示彼岸过河规则有8条(隐含了约束条件)1(0,*,*,*)(1,*,*,*)/2(0,0,*,*)(1,1,*,*)3(0,*,0,*)(1,*,1,*)/4(0,*,*,0)(1,*,*,1)5(1,*,*,*)(0,*,*,*)/6(1,1,*,*)(0,0,*,*)7(1,*,1,*)(0,*,0,*)/8(1,*,*,1)(0,*,*,0)*=0/1表示随意岸边但必需相同第2章 搜寻技术41“农夫过河农夫过河”广度优先搜

23、寻广度优先搜寻第2章 搜寻技术0 0 0 01 0 1 01 1 0 00 0 1 01 1 1 00 1 0 01 1 0 10 1 0 11 1 1 11 0 1 10 0 0 1closed表所用规则序列 3/5/4/7/2所用规则序列 3/5/2/7/4所用规则序列 3/5/4/7/2/5/3所用规则序列 3/5/2/7/4/5/342“农夫过河农夫过河”深度优先搜寻深度优先搜寻第2章 搜寻技术0 0 0 01 0 1 01 1 0 00 0 1 01 1 1 00 1 0 01 1 0 10 1 0 11 1 1 1closed表所用规则序列 3/5/2/7/4所用规则序列 3/5/

24、2/7/4/5/3只运用一个搜寻分支/所扩展的第一个节点是最新节点432.3 启发式搜寻策略2.3.1 贪欲最佳优先搜寻2.3.2 A*搜寻2.3.3 启发函数2.3.4 联机搜寻第2章 搜寻技术44启发式搜寻通用算法启发式搜寻通用算法启发式搜寻也称有信息搜寻，其通用算法称为最佳优先搜寻(Best-First-Search)最佳优先搜寻基于评价函数扩展节点依据距离目标最短的评价值来扩展并不是真正的最佳只是表现得最佳/近似最佳算法的关键因素是启发函数(Heuristic function)，记为f(n)/f(n)=从节点n到目标节点的最低耗散路径的耗散估计值启发函数引导搜寻两种方式贪欲最佳优先搜

25、寻/A*搜寻(A*算法)第2章 搜寻技术452.3.1 2.3.1 贪欲最佳优先搜寻贪欲最佳优先搜寻贪欲最佳优先搜寻的评价函数f(n)=h(n)在贪欲最佳优先搜寻中总是选择当前离目标最近(最小代价)的节点进行扩展(搜寻)局部最佳未必全局最佳不是最优的(下例)运用贪欲最佳优先搜寻算法搜寻从Arad到首都的行车最短路途Arad的下一站有3个城市S(253)/T(329)/Z(374)扩展Sibiu有3个城市F(176)/O(380)/R(193)扩展Fagaras干脆可到目的地然而实际不是最优的：SFB实际全长310/SRVPB实际全长278，多了32km第2章 搜寻技术46问题实例问题实例Rom

26、aniaRomania马路图马路图第2章 搜寻技术47问题实例问题实例(1)(1)第2章 搜寻技术找寻从Arad到首都的行车最短路途评价函数f(n)=h(n)直线距离启发式hSLD 与实际距离相关但需另外给出，见下表Arad366Mehadia241Bucharest0Neamt234Craiova160Oradea380Dobreta242Pitesti100Eforie161Rimnicu Vilcea193Fagaras176Sibiu253Giurgiu77Timisoara329Hirsova151Urziceni80Iasi226Vaslui199Lugoj244Zerind374

27、48问题实例问题实例(2)(2)第2章 搜寻技术启发函数h(n)最小化会对错误的起点比较敏感例子：地图中Iasi到Fagaras的行车路途(走入死路的可能)须要细致检查重复状态，否则可能恒久找不到解与深度优先搜寻类似，非最优、非完备最坏状况下时空困难度都是O(bm)/m为最大搜寻深度492.3.2 A*2.3.2 A*搜寻搜寻A*搜寻的评价函数为f(n)=g(h)+h(n)g(n)是从初始节点到该节点n的路径耗散h(n)是从节点n到目标节点的最低耗散路径的估计耗散值，称为启发式或启发函数因此，f(n)=经过节点n、具有最低耗散值的解的估计耗散找到g(n)+h(n)值最小的节点当然是合理的(参见

28、书中p79图4.3对于地图的搜寻)若启发函数h(n)满足确定条件，则A*搜寻是完备的和最优的第2章 搜寻技术50搜寻算法的可接受性搜寻算法的可接受性定义搜寻算法的可接受性(可接受性)(Hart,Nilsson,Raphel,1968)假如状态空间中的目标状态存在，并且从初始状态到目标状态有一条通路，而搜寻算法确定能在有限步内终止并找到一个最优解(代价最低)，则这个状态空间搜寻算法称为可接受的对于A*搜寻来说，运用树搜寻算法(Tree-Search)，则它是可接受的假如对启发函数h(n)作确定限制，则运用图搜寻算法(Graph-Search)也是可接受的第2章 搜寻技术51可接受的启发函数可接受

29、的启发函数算法的可接受性取决于启发函数的可接受性启发函数h(n)是可接受的h(n)从来不会过高地估计到达目标的耗散值此即h(n)满足h(n)h*(n)，h*(n)是从当前节点n到达目标的最低耗散值此即f(n)恒久不会高估经过节点n的解的实际耗散f(n)f*(n)，所以是最优解假如h(n)是可接受的，那么运用Tree-Search的A*算法是可接受的(最优的)自己尝试证明，参考附录证明过程第2章 搜寻技术52A*搜寻的Tree-Search算法function Tree-Search(problem,fringe)return solution or failureSelect h(n)Make

30、-Node(Initial-Stateproblem&get their f(n)Insert(nodes,fringe)Sort(fringe,f(n)do while(1)if fringe=Empty then return failurenodeRemove-First(fringe)if Statenode=Goal then return Solution(node)Expend(node,problem)&get their f(n)Insert(nodes,fringe)Sort(fringe,f(n)第2章 搜寻技术53A*搜寻的Graph-Search算法假如A*搜寻运用图

31、搜寻算法，则A*必定返回最优解的结论就不成立缘由是假如最优路径不是第一个生成的，可能因为有重复状态而被丢弃解决方案：1)修改Graph-Search算法使得能够进行比较，只丢弃耗散值大的路径2)保证到达任何重复状态的最优路径总是第一条被追随的路径要求h(n)保持一样性(单调性)算法请自行给出第2章 搜寻技术54h(n)h(n)的一样性的一样性(1)(1)定义启发函数的一样性假如对于每个节点n和通过随意行动a生成n的每个后继节点n，从节点n到达目标节点的估计耗散值h(n)不大于从n到n的单步耗散与从n到目标节点的估计耗散值之和，则h(n)称为一样的此即h(n)c(n,n,a)+h(n)/是三角不

32、等式的某种形式每个一样的启发函数都是可接受的证明要点：h(n)c(n,n,a)+h(n),h(n)c*(n,n,a)+h(n)可得h(n)h*(n)h(n)h*(n)目标节点h(T)=h*(T)=0回退可得随意节点h(n)h*(n)第2章 搜寻技术55h(n)h(n)的一样性的一样性(2)(2)通常我们选择的启发函数h(n)都满足一样性要求(因而必定是可接受的)关于一样性的结论：假如h(n)是一样的，那么运用Graph-Search的A*算法是最优的附录证明似乎没有利用此条件假如h(n)是一样的，那么沿着任何路径的f(n)值是非递减的(由一样性定义可得)f(n)耗散值沿着任何路径都是非递减的结

33、论允许在状态空间中画出等值线(见下图)第2章 搜寻技术56道路里程的等值线道路里程的等值线第2章 搜寻技术ZTLMDCGUONIVHE420A380BFPRS40057A*搜寻节点的扩展A*搜寻由初始节点动身起先搜寻，以同心带状增长f(n)耗散值的方式扩展节点假如h(n)=0则为代价一样搜寻(只按g(n)值排序)则同心带为“圆型”，运用启发函数则同心带向目标节点方向拉伸假如C*是最优解路径的耗散值，则有以下结论：A*算法扩展全部f(n)C*的节点A*算法在到达目标节点之前可能会扩展一些正好处于“目标等值线”上的节点A*算法不扩展f(n)C*的节点(均被剪枝)第2章 搜寻技术58A*算法的性质算

34、法的性质(1)(1)A*算法是完备的假如解存在，就确定能找到/因为找到解只要有限步A*算法是最优的即可接受的(一个普遍接受的证明见附录)A*算法对于任何给定的启发函数都是效率最优的/没有任何其他算法扩展的节点少于A*算法但是，A*算法对于多数问题来说，搜寻空间处于目标等值线内的节点数量是求解路径长度的指数级第2章 搜寻技术59A A*算法的性质算法的性质(2)(2)假如要求不以指数级增长，则启发函数须要满足条件对于几乎全部的启发函数来说，偏差至少都是与路径耗散成正比的，而不是路径耗散的对数/所以，在实际应用中，往往不是坚持找到最优解，而是接受以下两种方式：运用A*算法的变种算法快速找到非最优解

35、设计精确而非严格可接受的启发函数第2章 搜寻技术60A A*算法在空间方面的改进算法在空间方面的改进A*算法在内存中保留全部生成的节点，消耗极大因而对于很多大规模问题时不好用的A*算法要削减对内存的需求改进递归最佳优先搜寻RBFS仿照标准的最佳优先搜寻的递归算法，只是用线性存储空间假如h(n)是可接受的，则RBFS最优MA*(存储限制A*)和SMA*(简化的MA*)充分利用可用的内存SMA*的思想当内存放满时，就丢弃最差的一个子节点而加入新节点假如任何最优解是可到达的，则SMA*是最优的第2章 搜寻技术612.3.3 2.3.3 启发函数启发函数A*搜寻的关键就是设计可接受的或者一样的(单调的

36、)启发函数如何评价启发函数/如何设计启发函数例子八数码问题关于八数码问题的一些数据：随机产生的八数码游戏的平均解的步数=22分支因子约为3穷举搜寻(盲目搜寻)考虑的状态个数3223.1*1010实际可到达的不同状态个数9!/2=181440第2章 搜寻技术62八数码问题的启发函数八数码问题的启发函数启发函数的核心决不高估到达目标的步数/对于八数码问题的常用候选：h1(n)=不在位棋子数这是一个可接受的启发函数，因为要把“不在位”的棋子都移动到正确位置上，每个错位的棋子至少要移动一次/所以有h1(n)h*(n)h2(n)=全部棋子到达其目标位置的距离和计算水平距离(曼哈顿距离)/该函数也是可接受

37、的，因为到达其目标位置至少要移动这些距离长度第2章 搜寻技术63启发函数精确度对算法性能的影响启发函数精确度对算法性能的影响刻画启发函数质量的一个度量是有效分支因子b*b*是深度为d的一样搜寻树为了能够包括N(生成的总节点数)+1个节点所必需的分支因子N+1=1+b*+(b*)2+(b*)d例如：52个节点在第5层找到解，则b*=1.92有效分支因子可以依据问题实例发生变更，但是在足够难的问题中是稳定的/因此小规模试验中测得b*值可以为启发函数的总体有效性供应指导第2章 搜寻技术64八数码问题启发函数的比较八数码问题启发函数的比较良好设计的启发函数使b*值接近1，允许对大规模的问题进行求解启发

38、函数越接近于真实最优解的值，则相应的搜寻算法效率越高/明显此时有假如h1(n)h2(n)，则h2(n)优于h1(n)(此时h2(n)信息量比h1(n)多)p85页给出了八数码问题的启发函数h1/h2的比较数据“优于”的含义运用h2的算法不会比运用h1的算法扩展更多的节点第2章 搜寻技术65如何设计启如何设计启发函数发函数A*搜寻的关键如何找到是一个合适的启发函数找寻策略：从松弛问题中获得松弛问题的最优解的耗散是原问题的一个可接受的启发函数从给定问题子问题的解耗散中获得建立模式数据库，存储每个可能子问题实例从阅历中学习运用归纳学习算法，运用相关状态特征来预料第2章 搜寻技术66松弛问题最优解作为

39、启发函数松弛问题最优解作为启发函数松弛问题降低了行动限制的问题松弛问题的最优解耗散是原问题的一个可接受的启发函数依据定义，原始问题的最优解也是该松弛问题的解，其耗散不低于松弛问题的最优解松弛问题的最优解是精确耗散，确定满足三角不等式，因而是单调的，所以作为启发函数确定是可接受的假如问题定义通过形式化语言描述，则自动地构造其松弛问题是可能的/例子八数码问题第2章 搜寻技术67子问题的解耗散作为启发函数子问题的解耗散作为启发函数子问题的最优解耗散是完整问题的耗散下界建立模式数据库存储每个可能子问题实例的精确解耗散从目标状态向后搜寻并记录下每个子问题模式的耗散，存储于数据库搜寻中遇到的每个完整状态通

40、过在数据库中查找出相应子问题布局而设计出一个可接受的启发函数对于八数码问题，这样的启发函数要比曼哈顿距离精确得多(具体数值见p87)第2章 搜寻技术68从阅历中学习启发函数从阅历中学习启发函数从实例中学习每个实例包含了解路径上的各状态及其到达解的耗散每个最优解实例供应了可学习h(n)的实例收集实际解消耗的统计数据，以此产生可预料其他状态解消耗的启发函数h(n)运用归纳学习方法八数码问题的探讨(p87)第2章 搜寻技术69A*搜寻的例子(1)积木块移动游戏初始状态：目标状态：移动规则：(1)积木移到空格/代价=1(2)积木跨越1个积木移到空格/代价=1(3)积木跨越2个积木移到空格/代价=2第2

41、章 搜寻技术70A*搜寻的例子(2)A*搜寻：至少代价=每个W左边B的个数(B到W右边的必需跨越W的代价)令h(n)=至少代价，则h(n)h*(n)且满足单调性 h(ni)h(ni+1)+g(ni+1)-g(ni)(实际是=)g(n)=到达当前状态实际付出的代价搜寻过程中括号里的数字分别为h/g值第2章 搜寻技术71A*搜寻的例子(3)第2章 搜寻技术722.3.4 2.3.4 联机搜寻联机搜寻脱机搜寻不需感知，只要计算例子：简洁游戏，通过有限的规则作用即可推算出目标所在联机搜寻必需通过行动/视察与计算交叉进行才能确定下一步搜寻两种状况：环境未知只有行动才能得知如何正确走向目标/环境空间过大虽

42、然理论上已知，但是实际不行计算(如棋类竞赛)第2章 搜寻技术73例子：迷宫问题例子：迷宫问题第2章 搜寻技术 G S3211 2 3 如左图所示，联机搜寻问题只能通过行动来解决，因为障碍是不能事先预知的 智能体初始位置在S，其已知信息为：ACTION(s)状态S下的行动列表 c(s,a,s)通过行动a从s状态到达s状态 Goal-Test(s)/G目标位置 智能体可运用曼哈顿距离启发式74竞争率竞争率(1)(1)代价智能体实际走过的路经总耗散志向耗散没有无用搜寻步骤的走过路径耗散/也就是应当走过路径的耗散竞争率代价志向耗散该值要尽可能地小第2章 搜寻技术75竞争率竞争率(2)(2)影响竞争率的

43、因素，使其无穷大行动不行逆进入一个不行到达目标的状态又不行回溯没有算法能够在全部的状态空间中避开死路(p98图4.19a)因此，通常须要假设状态空间是可平安探究的具有可逆的状态空间/从每个可达状态动身都有可达的目标状态不过，在可逆状态空间中，因为对手的存在，也会出现无界竞争率的状况(p98图4.19b)第2章 搜寻技术76联机搜寻智能体联机搜寻智能体联机搜寻智能体须要行动和感知，然后扩展当前状态的环境地图区分：联机规划与行动交叉/脱机只要规划例子：A*搜寻在不同子空间节点的跳动式扩展，模拟而非实际行动/联机算法只扩展目前实际占据的节点接受深度优先搜寻联机搜寻必需维护一个回溯表第2章 搜寻技术77