启发式搜索策略讲稿_启发式搜索法

启发式搜索策略讲稿由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“启发式搜索法”。

启发式搜索策略讲稿

1.引入启发式搜索策略的定义。

通过前面的学习，我们了解可以采用前面的一些搜索策略来解决梵塔问题，当它的阶数较小（如小于6）时，在计算机上求解并不难，但当阶数再增加时，其时空要求将会急剧的增加。对于那些大状态空间问题，这些搜索策略就不能胜任了。

又如博弈问题，就可能的棋局数讲，国际象棋是10^120，假设每步可以选择一种棋局，用极限并行速度计算，国际象棋的算法也得1亿亿年才可以算完。

因此，为了寻找更有效的搜索方法，人们提出了启发式搜索策略。

定义：为减小搜索范围而需要利用某些已知的、有关具体问题领域的特性信息。此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。

其基本思想是：在搜索路径的控制信息中增加关于被解问题的某些特征，用以指导搜索朝着最有希望到达目标节点的方向前进。

2.启发式搜索策略的主要特点。

由于充分考虑到问题求解所应用到的各种启发信息及知识，包括利用常识性推理和专家经验等信息与知识，启发式搜索能够动态地确定操作排序，优先调用较合适的操作规则，扩展、比较并选择最有希望的节点，使搜索尽可能以最快的速度，最短的距离、最小的代价，朝着最有利于达到目标节点的方向推进。3.估价函数和启发函数。

估价函数：搜索特性的一种数学表示，是指从问题树根节 点到达目标节点所要耗费全部代价的一种估计值。

f（n）=g（n）+h（n）

启发函数：在表达式f（n）=g（n）+h（n）中，g（n）部分是已确立的搜索路径基础上已耗费的代价，其轨迹和效率是无法再更改的；唯有h(n)才是可以积极争取按照希望方向来改变的部分，是可以更新的内容。

h（n）

4.局部择优搜索和全部择优搜索。

局部择优搜索：它是一种启发式搜索方法，是对深度优先搜索方法的一种改进。

全局择优搜索：按这种方法搜索时，每次总是从OPEN表中的全体节点中选择一个估价值最小的节点。

5.讲解例题：用全局择优搜索解决8数码问题。

f(x)=d(x)+h(x)

其中，d(x)表示节点x的深度

h(x)表示节点x的格局与目标节点格局不相同的牌数

6.回顾内容，课程小结。

a.启发式策略

b.局部择优搜索

c.全局择优搜索

d.八数码问题