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

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

搜索即设法在庞大状态空间图中找到目标。启发式搜索又称为有信息搜索，它基于问
题的状态空间，利用问题的启发信息来引导搜索，达到减少搜索范围、降低问题复杂度的
目的。启发式搜索依据某种知识及信息的指导，通过逐一状态比较而找到符合规定条件的

目标状态解。
1. 状态空间搜索
状态空间搜索的问题求解过程表现为在状态空间中寻找从初始状态到目标状态的可行
路径。通俗地说，就是在求解问题时，找到解题的过程，最终得到问题的解答。常用的状

态空间搜索有广度优先和深度优先两种方法。广度优先是从初始状态一层一层向下找，直
到找到目标为止；深度优先是按照一定的顺序先查找完一个分支，再查找另一个分支，直

到找到目标为止。广度优先和深度优先搜索都有一个很大的缺陷，就是它们都是在一个给
广东教育出版社
定的状态空间中穷举。这在状态空间不大的情况下是合适的算法，可是当状态空间十分庞
大的情况下就不可取了，它们的效率实在太低，甚至不可完成。
2. 估价函数

启发式搜索在解决问题的过程中，由于只有有限的信息（比如当前状态的描述），要
想进一步预测搜索过程中状态空间的具体行为很难。因此，启发式搜索极易出错。通过启
发式搜索可能得到一个最优解，也可能一无所获。这是启发式搜索固有的局限性，且这种

局限性不能由所谓更好的启发式策略或更有效的搜索算法来消除。
一般来说，启发信息越强，扩展的无用节点就越少，就越可能大大降低搜索工作量，
但不能保证找到最佳路径。因此，在实际应用中，最好在引入降低搜索工作量的启发信息

的同时，不降低找到最佳路径的可能性。在启发式搜索中，用于评价状态空间节点x重要
性的函数称为估价函数，其一般形式为
f (x)=g (x) + h (x)

其中，g (x) 为从初始节点到节点 x 付出的实际代价，h (x) 为从节点 x 到目标节点的最优路
径的估计代价，也称为启发函数。
估价函数 f (x) 是根据具体问题的不同而人为设定的，设定的有效性会直接影响搜索算
法的效率。如图2-5所示的简化地图导航问题，可以把实际代价 g (x) 设定为已经走过的路

径长度，估计代价 h (x) 设定为当前位置与终点之间的直线距离，也可以设置权重等。
3. 启发函数
启发性信息主要包含在启发函数 h (x) 中，其形式要根据问题的特点来确定。虽然启发

式搜索有望很快到达目标节点，但需要花费一些时间来评价新生节点。因此，在启发式搜
索中，估价函数的定义十分重要。如定义不当，搜索算法不一定能找到问题的解，即使找
到解，也不一定是最优的。启发函数 h (x) 的启发性信息通俗地说就是在估计下一个节点的

值时的约束条件。约束条件的多少会影响计算的耗时与准确性。如果信息越多或约束条件
越多，则排除的节点就越多，计算准确度就越高；但同时，启发函数 h (x) 包含的信息越
多，它的计算量就越大，计算耗费的时间就越多。因此，适当地设定启发函数 h (x) 所包含

的信息量、平衡准确度与耗时的关系非常重要。

32 32

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