启发式搜索课件.ppt

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

1、第3章搜索策略√3.4启发式搜索3.1引言3.2基于状态空间图的搜索技术(1)(2)3.3盲目搜索(1)(2)2021/7/2913.4启发式搜索前面讨论的各种搜索方法都是按事先规定的路线进行搜索，没有用到问题本身的特征信息，具有较大的盲目性，产生的无用节点较多，搜索空间较大，效率不高。如果能够利用问题自身的一些特征信息来指导搜索过程，则可以缩小搜索范围，提高搜索效率。像这样利用问题自身特征信息来引导搜索过程的方法称为启发式方法。2021/7/292启发式搜索通常用于两种不同类型的问题：正向推理反向推理正向推理一般用于状态

2、空间的搜索。在正向推理中，推理是从预选定义的初始状态出发向目标状态方向执行。反向推理一般用于问题规约中。在反向推理中，推理是从给定的目标状态向初始状态执行。3.4启发式搜索2021/7/293在前一类使用启发式函数的搜索算法中，包括通常所谓的OR图算法或者最好优先算法，以及根据启发式函数的不同而得到的其他的一些算法，如A*算法等等。另一方面，启发式反向推理算法通常称为AND-OR图搜索算法，AO*算法就是其中一种算法。3.4启发式搜索2021/7/2943.4.1启发性信息和评估函数（启发式搜索）如果在选择节点时能充分利用

3、与问题有关的特征信息，估计出节点的重要性，就能在搜索时选择重要性较高的节点，以利于求得最优解。我们把这个过程为启发式搜索。“启发式”实际上代表了“大拇指准则(ThumbRules)”，即在大多数情况下是成功的，但不能保证一定成功的准则。2021/7/295其中：g(x)——从初始节点S0到节点x的实际代价；h(x)——从x到目标节点Sg的最优路径的评估代价，它体现了问题的启发式信息，其形式要根据问题的特性确定，h(x)称为启发式函数。评估函数f(x)定义为从初始节点S0出发，约束地经过节点x到达目标节点Sg的所有路径中最小

4、路径代价的估计值。评估函数的一般形式为：f(x)=g(x)+h(x)其主要功能：用来评估节点重要性。评估函数2021/7/296启发式方法把问题状态的描述转换成了对问题解决程度的描述。这一程度用评估函数的值来表示。评估函数2021/7/297评估函数Snng目标状态节点ng初始状态节点S节点n搜索图Gh(n):n-ng的估计最小路径代价g(n):s-n的实际路径代价f(n):s-n-ng的估计最小路径代价2021/7/298A算法的设计与一般图搜索相同，划分为二个阶段：1、初始化建立只包含初始状态节点s的搜索图G:={s}

5、OPEN:={s}CLOSE:={}2、搜索循环MOVE-FIRST(OPEN)-取出OPEN表首的节点n扩展出n的子节点,插入搜索图G和OPEN表适当的标记和修改指针（子节点父节点）排序OPEN表（评价函数f(n)的值排序）通过循环地执行该算法，搜索图会因不断有新节点加入而逐步长大，直到搜索到目标节点。启发式搜索A算法2021/7/299扩展出n的子节点ni,插入搜索图G和OPEN表对每个子节点ni,计算f(n,ni)=g(n,ni)+h(ni)适当的标记和修改指针（子节点父节点）(i)全新节点：f(ni)=f(n,

6、ni)(ii)已出现在OPEN表中的节点(iii)已出现的CLOSE表中的节点IFf(ni)>f(n,ni)THEN令f(ni)=f(n,ni)修改指针指向新父结点n排序OPEN表（f(n)值从小到大排序）启发式搜索A算法---修改指针2021/7/29102.若OPEN表是空表，则失败退出；算法A3.选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSE表中，称此节点为节点n；1.建立一个只包含起始节点S的搜索图G,把S放到一个叫OPEN的未扩展节点表中；建立一个叫做CLOSE的已扩展节点表，其初始为空表；5

7、.扩展节点n，同时生成不是n的祖先的那些子节点的集合M,把M的这些成员作为n的后继节点添入搜索图G中；对于M中每个子节点ni,计算:f(n,ni)=g(n,ni)+h(ni)4.若n为一目标节点，则有解成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的；2021/7/29116.对那些未曾在G中出现过的M成员（全新结点）设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN表上的每一个M成员，比较子节点ni经由新、老父节点的评价函数值f(n,ni)、f(ni);若f(n,ni)

8、ni)=f(n,ni),并移动子节点指向老父节点的指针，改为指向新父节点。对已在CLOSE表上的每个M成员，作与第2类同样的处理，并把这些子结点从CLOSE表移出，重新加入OPEN表。7.按f(n)排序OPEN表中的节点，f(n)值最小者排在首位，重排OPEN表；8.转2。此过程生成一个明确的图G（搜索