人工智能课件第2章2

2.3.2 几种最基本的搜索策略 下面主要介绍采用Best-first策略的几个基本方法，这些方法构成了许多AI系统的构架，其效率取决于问题所在领域知识的利用与开发。由于这些方法的通用性，并且难于克服搜索过程的组合爆炸问题，所以又称为弱法(Weekmethod）。2.3.2 几种最基本的搜索策略 弱法主要包括：最佳优先法生成测试法爬山法广度优先法问题归约法约束满足法手段目的分析法。1生成测试法生成测试法(Generate-and-test）生成测试法的基本步骤为：1.生成一个可能的解，此解是状态空间一个点，或一条始于S0的路径。2.用生成的“解”与目标比较。3.达到目标则停止，否则转第一步。1生成测试法生成测试法(Generate-and-test）此方法属于深度优先搜索(depth-first-search）,因为要产生一个完全的解后再判断，若不是目标又要生成下一个“解”。这种方法几乎接近耗尽式搜索，因而效率低。于是人们考虑能否利用反馈信息以帮助决定生成什么样的解，这种改进就是下面要讲的爬山法。2爬山法(Hill-climbing）1生成第一个可能的解。若是目标，则停止；否则转下一步。2从当前可能的解出发，生成新的可能解集。2.1用测试函数测试新的可能解集中的元素，若是解，则停止；否则转2.2。2.2若不是解，则将它与至今已测试过的“解”比较。若它最接近解，则保留作为最佳元素；若它不最接近解，则舍弃。3以当前最佳元素为起点，转(）。2爬山法(Hill-climbing）爬山法在生成的元素中寻找最优解，这种最优是局部最优。爬山法会产生下述问题：(1）找到的是局部最大值。(如图2-18(a)(2）碰到平顶时无法处理。(如图2-18(b)爬山法(Hill-climbing）图2-18(a)搜索中遇到局部最优点图2-18(b)搜索中遇到平顶(3）碰到山脊时无法处理。爬山法(Hill-climbing）碰到山脊的克服办法是：(1)退回较大一步，即允许回朔。(2)向前跨一大步。(3)多设几个初始点，从几个初始点同时或先后进行搜索。3最佳优先搜索最佳优先搜索(Best-first search)1生成第一个可能的解。若是目标，则停止；否则转下一步。2从该可能的解出发，生成新的可能解集。2.1用测试函数测试新的可能解集中的元素，若是解，则停止；否则转a。2.2若不是解，则将新生成的“解”集加入到原可能“解”集中。3从解集中挑选最好的元素作为起点，再转。最佳优先算法是从“可能解集”中找最佳，因此是全局最优。爬山法是从当前后继中求最好的，因此比爬山法考虑的因素要多一些。4.模拟退火法模拟退火法(simulated Annealing)退火是冶金专家为了达到某些特种晶体结构重复将金属加热或冷却的过程,该过程的控制参数为温度T。这种思想应用于许多优化问题就产生了模拟退火算法,模拟退火法的基本思想是,在系统朝着能量减小的趋势这样一个变化过程中,偶尔允许系统跳到能量较高的状态，以避开局部极小点,最终稳定到全局最小点。4.模拟退火法模拟退火法(simulated Annealing)如图2-20所示，若使能量在C点突然增加h，就能跳过局部极小点B,而找到全局最小点A。现在的问题是何时增加能量？应该增加多少 能 量？为 此，柯 克 帕 特 里 克(S.Kirkpatrick）提出了模拟退火算法。BA4.模拟退火法模拟退火法(simulated Annealing)模拟退火算法：1随机挑选一单元k，并给它一个随机的位移，求出系统因此而产生的能量变化EK；2若EK0，该位移可采纳，而变化后的系统状态可作为下次变化的起点；若EK0，位移后的状态可采纳的概率为:PK=1/(1+e-EK/T)4.模拟退火法模拟退火法(simulated Annealing)式中T为温度,然后从(0，1）区间均匀分布的随机数中挑选一个数R。若RPK，则将变化后的状态作为下次的起点，否则,将变化前的状态作为下次的起点。3.转1继续执行，直至达到平衡状态为止。4.模拟退火法模拟退火法(simulated Annealing)对于搜索问题中的爬山法,利用模拟退火算法,可以不断变化的随机选择一些大的步长,以跨过局部极小点.通常的作法是:最初阶段倾向于取大步；后阶段倾向于取小步。4.模拟退火法模拟退火法(simulated Annealing)如果希望小球离开A点然后停在B点,使用能量减小的的方法来摇动系统,这小球只能停在A点。若开始以较大的速度摇动,后来满满的减轻,则小球很可能就会落在B点,且小球到B点之后,就不易从B点摇到A点。AB24 图搜索策略图搜索策略图搜索策略是一种在图中寻找解路径的方法。我们首先看看对于一个实际搜索问题,应该采用什么形式来表示,是用图还是用树,可以作如下比较:(1）用树结构，允许搜索图中有相同结点出现，不必考虑产生的是否为重复的结点，因为同一个结点可由许多不同的路径产生。优点：控制简单。缺点：占空间较大，产生相同结点多，则时空均需要较大的代价24 图搜索策略图搜索策略(2）用图结构，不允许搜索图中有相同结点出现。优点：节省大量空间(相同的结点只存一次）和时间(相同结点不需要重复产生）。缺点：每产生一个新的结点需判断这个节点是否已生成过,因而控制更复杂，判断也要占用时间。碰到具体问题时，要权衡二者的利弊。若可能产生大量相同结点，则应采用搜索图。24 图搜索策略图搜索策略图搜索算法只记录状态空间那些被搜索过的状态，它们组成一个搜索图叫G。G由两张表内的节点组成：Open表：用于存放已经生成，且已用启发式函数作过估计或评价，但尚未产生它们的后继节点的那些结点，也称未考察结点。24 图搜索策略图搜索策略Closed表：用于存放已经生成，且已考察过的结点。还有一个结构Tree,它的节点为G的一个子集。Tree用来存放当前已生成的搜索树,该树由G的反向边(反向指针)组成。24 图搜索策略图搜索策略或图通用搜索算法：或图通用搜索算法：设S0：初态,Sg：目标状态1.产生一仅由S0组成的open表；2.产生一空closed表；3.如果open为空，失败退出；4.在open表上按某一原则选出第一个优先结点，称为n，放n到closed表中，并从open表中去掉n；24 图搜索策略图搜索策略5.若nSg，则成功退出；解为在Tree中沿指针从n到s0的路径，或n本身。(如八皇后问题给出n即可，八数码问题要给出路径）6.产生n的一切后继，将后继中不是n的先辈点的一切点构成集合M，将装入G作为n的后继,这就除掉了既是n的先辈又是n的后继的结点就避免了回路,节点之间有偏序关系存在。24 图搜索策略图搜索策略7.对M中的元素P，分别作两类处理：7.1若P/G，即P不在open表中也不在closed表中，则P加入open表注1，同时加入搜索图G中，对P进行估计放入Tree中。7.2PG，则决定是否更改Tree中P到n的指针注2。8.转3。/24 图搜索策略图搜索策略注1：若生成的后继节点放于：（1）Open表的尾部相当于Breadth-first-search；（2）Open表的首部相当于Depth-first-search；（3）根据启发式函数f的估计值确定最佳者，放于Open表的首部相当于Best-first-search。24 图搜索策略图搜索策略说明:(1)若PM且在open表中，这说明P在n之前已是某一结点m的后继,但本身尚未被考察(未生成P的后继)，S0Path1Path2nm后扩展p先扩展P在n之前已是某一结点m的后继24 图搜索策略图搜索策略这说明从S0p至少有两条路径，这时有两种情况：a若Path1的代价Path2的代价时，当前路径较好，要修改p的指针，使其指向n，即标出搜索之后的最好路径；b若Path1的代价Path2的代价时，原路径较好，不改变p的指针。24 图搜索策略图搜索策略(2）若pM且在closed表中，这说明:a.p在n之前已是某一节点m的后继，所以需要作如(1)同样的处理，如下图右部。bp在closed表中，说明p的后继也在n之前已生成，我们称为Ps，那么对Ps同样可能由于np这一路径的加入又必须比较多条路径代价后而取代价小的一条，如下图左部。24 图搜索策略图搜索策略S0过去对Ps所选现在生成P过去生成的最优路径的路径P的路径knPsmP图2-23pM且在closed表中时不同的最优路径24 图搜索策略图搜索策略即过去对S0P而言的最优路径为S0mp，现 在 要 从 S0mp与S0np中求最优路径。同理，若过去对S0Ps而言的最优 路 径 为 S0kPs,现 在 要 从S0pPs,S0kPs中选最优路径。24 图搜索策略图搜索策略 S0nPmPsPs，S0nPmPsPs，当前搜索图和搜索树例2.9设当前搜索图和搜索树分别为：24 图搜索策略图搜索策略若启发式函数f(n）为从起点S0到节点n得最短路径的长度，该长度用边的数目表示，当前扩展的节点是搜索图中的n，设p是n的后继，如下图2-25(a)，p是已考察节点，则在扩展了节点n后，P的f值应从4减少到2，这时Tree中P原来指向m的指针应改变指向n，24 图搜索策略图搜索策略 S0nFmPsPPs，S0nFmPsPPs，扩充n的搜索图修改P指针的搜索树24 图搜索策略图搜索策略 S0nFmPsPPs，P的指针改变后，Tree中指针的修改P的指针改变后，Ps，的路径自动改变了，Ps的f值从4减少到了3，这时也应该修改在Tree中的指针，修改的结果为图2-26