34启发式搜索 ppt课件.ppt

第3章 搜索策略
√ 启发式搜索
引言
基于状态空间图的搜索技术(1)(2)
盲目搜索(1)(2)
2020/12/2
1
启发式搜索
前面讨论的各种搜索方法都是按事先规定的路线进行搜索，没有用到问题本身的特征信息，具有较大的盲目性，产生的无用节点较多，搜索空间较大，效率不高。
如果能够利用问题自身的一些特征信息来指导搜索过程，则可以缩小搜索范围，提高搜索效率。
像这样利用问题自身特征信息来引导搜索过程的方法称为启发式方法。
2020/12/2
2
精品资料
2020/12/2
3
你怎么称呼老师？
如果老师最后没有总结一节课的重点的难点，你是否会认为老师的教学方法需要改进？
你所经历的课堂，是讲座式还是讨论式？
教师的教鞭
“不怕太阳晒，也不怕那风雨狂，只怕先生骂我笨，没有学问无颜见爹娘 ……”
“太阳当空照，花儿对我笑，小鸟说早早早……”
2020/12/2
4
启发式搜索通常用于两种不同类型的问题：
正向推理
反向推理
正向推理一般用于状态空间的搜索。在正向推理中，推理是从预选定义的初始状态出发向目标状态方向执行。
反向推理一般用于问题规约中。在反向推理中，推理是从给定的目标状态向初始状态执行。
启发式搜索
2020/12/2
5
在前一类使用启发式函数的搜索算法中，包括通常所谓的OR图算法或者最好优先算法，以及根据启发式函数的不同而得到的其他的一些算法，如A*算法等等。
另一方面，启发式反向推理算法通常称为AND-OR图搜索算法，AO*算法就是其中一种算法。
启发式搜索
2020/12/2
6
启发性信息和评估函数
（启发式搜索）如果在选择节点时能充分利用与问题有关的特征信息，估计出节点的重要性，就能在搜索时选择重要性较高的节点，以利于求得最优解。我们把这个过程为启发式搜索。
“启发式”实际上代表了“大拇指准则(Thumb Rules)”，即在大多数情况下是成功的，但不能保证一定成功的准则。
2020/12/2
7
其中：g(x)——从初始节点S0到节点x的实际代价；
h(x)——从x到目标节点Sg的最优路径的评估代价，它体现了问题的启发式信息，其形式要根据问题的特性确定，h(x)称为启发式函数。
评估函数f(x)定义为从初始节点S0出发，约束地经过节点x到达目标节点Sg的所有路径中最小路径代价的估计值。
评估函数的一般形式为：
f(x)=g(x)+h(x)
其主要功能：用来评估节点重要性。
评估函数
2020/12/2
8
启发式方法把问题状态的描述转换成了对问题解决程度的描述。
这一程度用评估函数的值来表示。
评估函数
2020/12/2
9
评估函数
S
n
ng
目标状态节点ng
初始状态节点S
节点n
搜索图G
h(n): n-ng的估计最小路径代价
g(n):s-n的实际路径代价
f(n):s-n-ng的估计最小路径代价
2020/12/2
10