Page 39 - 高中 信息技术 选择性必修4 人工智能初步
P. 39
2.2 启发式搜索
2.2 启发式搜索
启发式搜索（Heuristic Search）是人工智能领域解决问题常用的方法之一。基于已有
知识和经验，根据问题的实际情况，不断寻找可利用知识，从而构造一条效率最高的推理
路线，使问题得以解决的过程称为搜索。对于人工智能系统而言，问题的状态空间随搜索
的深入呈现指数或阶乘增长。为了准确地找出正确答案，启发式搜索将沿最有希望的路径
穿越状态空间来降低解决问题的复杂性；同时，把没有希望的状态及这些状态的后代排
广东教育出版社
除，这样便可以克服组合“爆炸”，找到可接受的解。
探究活动
讨 论
下面以如图2-5所示的简化地图为例，探讨导航问题
（真实的地图导航虽然更复杂，但两者基本原理一致）。
图中每一步都有上下左右四种可能的走法，所有可
能的走法所构成的路径全集组成了问题的状态空间，而
其中任意一条从起点到终点的通路就是问题的一个解，
没有通路就代表问题无解。启发式搜索在求解的过程
中，并非穷举上下左右四个方向盲目搜索，而是根据当
前位置与目标之间的一些相关信息（例如与终点的距离
图2-5 简化地图导航问题
等），优先选择最有希望的方向去搜索，如果路线不
通，再搜索其次有希望的方向，从而尽可能快地找到通路。
2 . 2 . 1 启发式搜索原理
由于求解条件的不确定性和不完备性，
求解问题的过程可能会有很多分支。我们把
每条可能的分支画成一幅图，这幅图表示的
就是问题的状态空间。问题的状态空间即问
题的解空间，或称其为“状态树”，如图
2-6所示。图中的节点S （i=1，2，3，…）
i
表示状态，状态之间的连接采用有向线段来
表示状态之间的转换关系。 图2-6 问题的状态空间
31 31
21Y3228.indd 31 2019/10/10 14:23:29
