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

第二章 人工智能基础算法及应用

效率低，但保证能得到最优解。
（2）若 h (x) = d (x)，即估计距离等于实际距离，则搜索将严格按照最短路径进行，
此时的搜索效率是最高的。

（3）若 h (x) > d (x)，即估计距离大于实际距离，则搜索的节点数少，搜索范围小，
效率高，但不能保证得到最优解。
A*算法按 f (x) 递增的顺序来排列可能被扩展的节点，因而优先扩展 f (x) 值最小的节
点，体现了“最佳优先”的搜索思想，但只有当 h (x) ≤ d (x) 时，才能找到最优解。实践

证明，应用这样的估价函数是可以找到最短路径的。

广东教育出版社
体 验

试用A*算法解决如图2-5所示的简化地图导航问题。
估价函数 f (x) 的设定方法和算法的大致步骤如下：
（1）建立一个搜索队列Q，用来存放待搜索的点，以及该点的来路（即上一步是从哪

个点过来的）。队列Q的初始状态为空。
（2）当有新的点加入队列Q时，计算该点的估价函数 f (x)，并且队列Q中所有的点按
照 f (x) 从小到大排列，f (x) 相同时按照先来后到的顺序排列。

（3）首先把导航的起点加入队列Q中，起点的来路为空。
（4）从队列Q中取出第一个点P（估价函数值最小的点），如果已经无点可取（队列
Q为空），则输出结果：“导航没有通路，算法结束”。否则继续下一步。
（5）如果点P就是终点，则已经找到一条通路，只要沿着点P的来路一个个点输出，

直至起点，就能输出这条通路，算法结束。否则继续下一步。
（6）把点P上下左右四个方向的邻接点依次取出，排除掉其中路不通的点，以及曾经
进入过队列Q的点，余下的点作为待搜索的点加入队列Q中［依照步骤（2）的方法］。

（7）重复步骤（4），直至算法在步骤（4）或步骤（5）处结束，或者队列Q满了，
无法继续搜索而结束。

启发式搜索的启发式信息通过设定估价函数 f (x) 来调整。特别地，如果设定 f (x) 等于
常数C，则A*算法退化成广度优先算法；如果设定 f (x) 值等于来路（上一点）的 f (x) 值的
常数C倍（0<C<1），则A*算法退化成深度优先算法。

2 . 2 . 3 启发式搜索的应用

实际生活中，启发式搜索主要应用于专家系统中。例如“深蓝”与国际象棋高手之间

的博弈、财务统计和顾问，以及一些复杂算法的求解等。它的内容也正逐步扩展，从传统
的爬山和动态规划算法到最佳优先搜索，再到二人游戏中利用极小极大选择最好、避免最

34 34

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