Page 41 - 高中 信息技术 选择性必修4 人工智能初步

 2.2 启发式搜索

分 析

根据如图2-5所示的简化地图，分析应如何设计估价函数。

2 . 2 . 2 启发式搜索的分类

在具体选取最佳搜索节点时，基于使用策略的不同，启发式搜索算法可以分为局部择
优搜索算法、最佳优先搜索算法和A*算法等。

1. 局部择优搜索算法
广东教育出版社
局部择优搜索算法又叫爬山法。在搜索的过程中扩展当前状态空间时，该算法将在选
取最佳子节点后，舍弃其他的兄弟节点和父节点，而一直搜索下去。这种搜索的局限性很

明显，由于舍弃了其他的节点，搜索结果可能把最好的节点都舍弃了，因此求解的“最佳
节点”只是该阶段的最佳，并不一定是全局的最佳。这种算法不保存任何历史记录，所以
它不具有从失败中恢复的能力。因此，局部择优搜索算法的主要问题在于容易陷入局部最

优值。
2. 最佳优先搜索算法
对比局部择优搜索算法，最佳优先搜索算法就智能多了，该算法在搜索时，不会舍弃

节点（除非该节点是死节点），在每一步的估价中，把当前节点和以前节点的估价值做比
较，从而得到“最佳节点”，这样可以有效地防止“最佳节点”丢失。最佳优先搜索算法
使用优先队列，使得算法可以从陷入局部优先等情况中恢复，从而使启发式搜索更加灵
活。最佳优先搜索算法使用列表来维护状态，用open列表来记录搜索的当前状态，用close

列表来记录已经访问过的状态。这种算法的创新之处是对open列表中的状态进行排序，排
序的依据是对状态与目标“接近程度”的启发性估计。最佳优先搜索算法总是选择最有希

望的状态做进一步扩展。由于它正在使用的启发信息可能被证明是错误的，所以它并不会
抛弃所有状态，而是把它们记录在open列表中。一旦发现启发信息将搜索引导到一条证明
不正确的路径，那么算法会从open列表中取出“次优先”的状态，从而把搜索的焦点转移
到状态空间的另一部分。

3. A*算法
A*算法是当今自动导航和游戏软件开发中十分常用的一种路径寻找算法，它可以保证
在任何起点和任何终点间找到最佳的路径。A*算法是人工智能在实际应用中的代表，是一

种典型的启发式搜索算法。
A*算法是一种在静态路网中求解最短路径的直接搜索方法，也是解决许多搜索问题的
有效算法。算法中的距离估算值 h (x) 与实际值越接近，最终搜索速度越快。保证找到最短

路径（最优解）条件的关键在于估价函数 f (x) 的选取［或者说 h (x) 的选取］。我们以 d (x)
表达状态 x 到目标状态的实际距离，那么 h (x) 的值大致有如下三种情况：
（1）若 h (x) < d (x)，即估计距离小于实际距离，则搜索的节点数多，搜索范围大，

33 33

21Y3228.indd 33 2019/10/10 14:23:29