启发式搜索课件.ppt

第3章搜索策略√(1)(2)(1)(2)2020/9/,没有用到问题本身的特征信息,具有较大的盲目性,产生的无用节点较多,搜索空间较大,效率不高。如果能够利用问题自身的一些特征信息来指导搜索过程,则可以缩小搜索范围,提高搜索效率。像这样利用问题自身特征信息来引导搜索过程的方法称为启发式方法。2020/9/202启发式搜索通常用于两种不同类型的问题:正向推理反向推理正向推理一般用于状态空间的搜索。在正向推理中,推理是从预选定义的初始状态出发向目标状态方向执行。反向推理一般用于问题规约中。在反向推理中,推理是从给定的目标状态向初始状态执行。,包括通常所谓的OR图算法或者最好优先算法,以及根据启发式函数的不同而得到的其他的一些算法,如A*算法等等。另一方面,启发式反向推理算法通常称为AND-OR图搜索算法,AO*算法就是其中一种算法。.1启发性信息和评估函数(启发式搜索)如果在选择节点时能充分利用与问题有关的特征信息,估计出节点的重要性,就能在搜索时选择重要性较高的节点,以利于求得最优解。我们把这个过程为启发式搜索。“启发式”实际上代表了“大拇指准则(ThumbRules)”,即在大多数情况下是成功的,但不能保证一定成功的准则。2020/9/205其中:g(x)——从初始节点S0到节点x的实际代价;h(x)——从x到目标节点Sg的最优路径的评估代价,它体现了问题的启发式信息,其形式要根据问题的特性确定,h(x)称为启发式函数。评估函数f(x)定义为从初始节点S0出发,约束地经过节点x到达目标节点Sg的所有路径中最小路径代价的估计值。评估函数的一般形式为:f(x)=g(x)+h(x)其主要功能:用来评估节点重要性。评估函数2020/9/206启发式方法把问题状态的描述转换成了对问题解决程度的描述。这一程度用评估函数的值来表示。评估函数2020/9/207评估函数Snng目标状态节点ng初始状态节点S节点n搜索图Gh(n):n-ng的估计最小路径代价g(n):s-n的实际路径代价f(n):s-n-ng的估计最小路径代价2020/9/208A算法的设计与一般图搜索相同,划分为二个阶段:1、初始化建立只包含初始状态节点s的搜索图G:={s}OPEN:={s}CLOSE:={}2、搜索循环MOVE-FIRST(OPEN)-取出OPEN表首的节点n扩展出n的子节点,插入搜索图G和OPEN表适当的标记和修改指针(子节点父节点)排序OPEN表(评价函数f(n)的值排序)通过循环地执行该算法,搜索图会因不断有新节点加入而逐步长大,直到搜索到目标节点。启发式搜索A算法2020/9/209扩展出n的子节点ni,插入搜索图G和OPEN表对每个子节点ni,计算f(n,ni)=g(n,ni)+h(ni)适当的标记和修改指针(子节点父节点)(i)全新节点:f(ni)=f(n,ni)(ii)已出现在OPEN表中的节点(iii)已出现的CLOSE表中的节点IFf(ni)>f(n,ni)THEN令f(ni)=f(n,ni)修改指针指向新父结点n排序OPEN表(f(n)值从小到大排序)启发式搜索A算法---修改指针2020/9/2010