湖南大学人工智能课件3-2

第三章PartII有信息的搜索策略内容提要最佳优先搜索贪婪最佳优先搜索A*搜索启发式函数松弛问题一种搜索策略实际上就是根据树结点扩张的顺序来决定的基本思路：通过对每一个结点设置一个评价函数f(n),找到一个代价最低的未扩散的结点实现：根据结点的评价函数值从低到高在队列中对结点进行排序大多数评价函数由启发函数h构成h(n):结点到目标结点的最小代价路径的代价估计值最佳优先搜索vs.一致代价搜索？代价函数的定义不同算法实例贪婪最佳优先搜索A*树评价函数f(n)=h(n)从结点n到目标结点的代价估测值罗马尼亚问题：贪婪最佳优先搜索首先扩展与目标结点估测距离最近的结点罗马尼亚问题中使用直线距离为估测距离完备性？最优性？时间复杂度：O(bm)空间复杂度:O(bm)评价函数f(n)=g(n)+h(n)g(n)=到达结点n已经花费的代价h(n)=结点n到目标节点的评估代价f(n)=通过结点n到达目标结点的总评估代价启发函数h(n)是可采纳的条件：如果对于每个结点n,h(n)h*(n)，其中h*(n)是到达目标结点的真实代价可采纳启发函数绝不会高估到达目标结点的代价，因此它是最优的定理：如果启发函数h(n)是可采纳的，那么A*使用树搜索是最优的证明：假定存在一个局部最优目标G2和一个全局最优目标G,设n是一个未扩散的结点且n在到达G的最短路径上，n,G2都位于算法的fringe队列之中如下图所示一个启发函数是一致的条件：对于任意一个结点n，以及n的行为a产生的后继结点n’,满足如下公式：h(n)≤c(n,a,n')+h(n')如果h(n)是一致的，我们得到定理：如果h(n)是一致的，A*使用图搜索是最优的证明：A*根据f值从小到大扩展结点;A*选择扩散结点n时，就已经找到了达到结点n的最优路径Environment:Patient,hospital,staffActuators:Screendisplay(questions,tests,diagnoses,treatments,referrals)Sensors:Keyboard(entryofsymptoms,findings,patient'sanswers)完备性每步的代价都大于某个常数e，并且分支数b是有限的最优性时间复杂度O(bΔ)空间复杂度O(bΔ)19例子：八数码问题平均解的深度？22平均分支因数？320例子：八数码问题h1(n):不在位的棋子数h2(n):所有棋子到其目标位置的距离和h1(n)=8,h2(n):=3+1+2+2+2+3+3+2=1821有效分支因子：对于某一问题，如果A*算法生成的总结点数为N,解的深度为d,那么b*就是深度为d的标准搜索树为了能够包括N+1个结点所必需的分支因子N+1=1+b*+(b*)2+…+(b*)d有效分支因子越小，算法性能越好22SearchCost(nodesgenerated)EffectiveBranchingFactordIDSA*(h1)A*(h2)IDSA*(h1)A*(h2)210662.451.791.79411213122.871.481.45668020182.731.341.308638439252.801.331.24104712793392.781.381.2223对于所有的结点n,h1(n)=h2(n)(两个函数都是可采纳的)，我们说h2(n)比h1(n)有优势。典型的搜索代价(平均结点扩展数)：d=12IDS=3,644,035nodesA*(h1)=227nodesA*(h2)=73nodesd=24IDS=toomanynodesA*(h1)=39,135nodesA*(h2)=1,641nodes减少了行动限制的问题称为松弛问题。松弛问题增加了状态空间的边原有问题的任一最优解同样也是松弛问题的最优解，但松弛问题可能存在更好的解。八数码问题行动描述棋子可以从方格A移动到方格B如果A与B水平或者垂直相邻并且B是空的三个松弛问题：去掉条件B的空的：h2将给出最短解的确切步数去掉条件AB相邻上述两者都去掉：h1将给出最短解的确切步数最佳优先搜索贪婪最佳优先搜索A*搜索启发式函数松弛问题QA？