启发式搜索ppt课件.ppt

《启发式搜索ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、启发式搜索主要内容搜索及其类型盲目搜索宽度优先搜索深度优先搜索启发式搜索与博弈搜索及其类型1、什么是搜索人工智能所要解决的问题大部分不具备明确的解题步骤，而只能是利用已有的知识一步一步地摸索前进。根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称之为搜索。搜索及其类型2、常用的搜索技术盲目搜索又称无信息/穷举式搜索，只能按照预先规定的搜索控制策略进行搜索，没有任何中间信息来改变这些控制策略。具有盲目性，效率不高，不便于复杂问题的求解。具体可以分为宽度优先搜索和深度优先搜索两种。启发式搜索在搜索求解过程中，根据问题本身的特性或搜索过

2、程中所产生的一些与问题有关的启发性信息，指导搜索朝着最有希望的推理方向前进，加速问题的求解过程并找到最优解。盲目搜索宽度优先搜索基本思想从初始节点So开始，逐层地对节点进行扩展并考察它是否为目标节点，在第n层的节点没有全部扩展并考察之前，不对第n+1层的节点进行扩展。它是一种先生成的节点先扩展的搜索方法。课件演示8数码问题的宽度优先搜索过程宽度优先搜索示例8数码问题的宽度优先搜索树盲目搜索OPEN表用来存放将要扩展的节点。CLOSE表在进行子节点的扩展时，为了避免同一个节点被重复扩展，可以把扩展过一次的节点，记录到CLOSED表中，从而使其不再成为以后扩展时的候选对象。宽度优先

3、搜索算法盲目搜索深度优先搜索深度优先搜索中，搜索树是从树根开始一枝一枝逐渐生成的。它是一种后生成的节点先扩展的搜索方法。基本思想：从初始节点So开始，在其子节点中选择一个节点进行考察，若不是目标节点，则再在该子节点的子节点中选择一个节点进行考察，如果该子节点可以扩展，则扩展该子节点，依次向下搜索，在搜索树的每一层始终先只扩展一个子节点，如此一直向下搜索，直到某个子节点既不是目标节点又不能继续扩展时，才从当前节点返回上一级节点，沿另一方向又继续前进。盲目搜索深度优先搜索示例求解八数码问题深度优先搜索示例8数码问题的深度优先搜索树深度优先搜索算法盲目搜索有界深度优先搜索在深度优先搜

4、索的基础上，给出了搜索树深度限制，当从初始节点出发沿某一分枝扩展到一限定深度时，就不能再继续向下扩展，而只能改变方向继续搜索。算法示例八数码问题(课件演示)启发式搜索启发式搜索是指在控制性知识中增加关于被解问题和相应任务的某些特性，利用启发性信息来确定节点的生成、扩展和搜索顺序，指导搜索朝着最有希望的方向前进的一类搜索方法。启发式搜索的特点大多是深度优先搜索的改进，即尽量沿着最有希望的路径，向深度方向小范围前进；在有多条路可走时，会给出该走哪条路径的建议，从而指导搜索过程朝最有利的方向前进；利用问题求解的先验知识，使之尽快找到问题的解；可采用估值的方法进行搜索指导；生成的状态空

5、间小、搜索时间短且效率高、控制性好，易于使问题得到解。启发式搜索启发性信息的类型有效地帮助确定扩展节点的信息，即用于决定应先扩展哪一个节点，以免盲目扩展。有效地帮助决定哪些后继节点应被生成的信息，即用于决定应生成哪些后继节点，以免盲目地生成过多无用节点。能决定在扩展一个节点时哪些节点应从搜索树上删除的信息，即用于决定应删除哪些无用节点，以免造成时空浪费。估价函数用来估价节点重要性的函数f(n)=g(n)+h(n)g(n)是从初始节点So到节点n的已经实际付出的代价；h(n)是从节点n到目标节点Sg的最优路径的估计代价启发式搜索的算法启发式搜索算法有很多种，如局部择优搜索、全局择

6、优搜索等等。右图表示了全局择优的启发式搜索流程。启发式搜索示例设估价函数为f(n)=g(n)+h(n)，其中g(n)表示节点n的搜索深度，h(n)表示节点n与目标节点两个棋局之间位置不相同的棋子数。每个节点左边的蓝色数字表示其估价值。A*SearchBest-knownformofbest-firstsearchIdea:avoidexpandingpathsthatarealreadyexpensiveEvaluationfunctionf(n)=g(n)+h(n)g(n)thecost(sofar)toreachthenodeh(n)estimatedcosttogetfr

7、omthenodetothegoalf(n)estimatedtotalcostofpaththroughntogoalA*SearchA*searchusesanadmissibleheuristicAheuristicisadmissibleifitneveroverestimatesthecosttoreachthegoalFormally:1.h(n)<=h*(n)whereh*(n)isthetruecostfromn2.h(n)>=0soh(G)=0foranygoalG.e.g