人工智能导论第 5 版 思考题 第五章

5.1 什么是搜索？ 有哪两大类不同的搜索方法？两者的区别是什么？

搜索：根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使得问题得以解决的过程称为搜索。

两大类不同的搜索方法：盲目搜索、启发式搜索。

两者的区别：在搜索过程中是否使用启发式信息。

5.2 什么是启发式搜索？什么是启发信息？

启发式搜索又称有信息搜索，它是指在搜索求解过程中，根据问题本身的特性或搜索过程中产生的一些信息来不断地改变或调整搜索的方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解。

可用于指导搜索过程且与具体问题求解有关的控制性信息称为启发信息。

5.3 用状态空间法表示问题时，什么是问题的解？求解过程的本质是什么？什么是最优解？最优解唯一吗？

用状态空间法表示问题时问题的解就是有向图中从某一节点 (初始状态节点) 到另一节点 (目标状态节点) 的路径。

求解过程的本质就是对状态空间图的搜索即在状态空间图上寻找一条从初始状态到目标状态的路径。 在不考虑搜索的代价时即假设状态空间图中各节点之间的有向边的代价相同时最优解就是解路径中长度最短的那条路径在考虑搜索代价时最优解则是解路径中代价最小的那条路径。

因为在状态空间图中可能存在几条长度或代价相等的最短解路径所以最优解可能会不唯一。

5.4 请写出状态空间图的一般搜索过程。在搜索过程中open表和closed 表的作用分别是什么？有何区别？

先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或者没有可供操作的节点为止。所谓对一个节点进行 “扩展” 是指对该节点用某个可用操作进行作用，生成该节点的一组子节点。 

OPEN 表用于存放刚生成的节点，对于不同的搜索策略，节点在 OPEN 表中的排序是不同的。

CLOSED 表用于存放将要扩展或者已扩展的节点。

5.5 什么是盲目搜索？主要有几种盲目搜索策略？

盲目搜索又称无信息搜索，即在搜索过程中，只按预先规定的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略。

主要的盲目搜索策略有：宽度优先搜索、深度优先搜索、有界深度优先搜索、代价树的宽度优先搜索和代价树的深度优先搜索。

5.6 在深度优先搜索中，每个结点的子结点是按某种次序生成和扩展的，在决定生成子状态的最优次序时，应该用什么标准来衡量？

用路径长短来衡量。

5.7 宽度优先搜索与深度优先搜索有何不同？分析深度和宽度优先的优缺点。在何种情况下,宽度优先搜索优于深度优先搜索？在何种情况下，深度优先搜索优于宽度优先搜索？

深度优先搜索与宽度优先搜索的区别就在于：在对节点 n 进行扩展时其后继节点在 OPEN 表中的存放位置。宽度优先搜索是将后继节点放入 OPEN 表的末端；而深度优先搜索则是将后继节点放入 OPEN 表的前端。

即宽度优先搜索按照 “先扩展出的节点先被考察” 的原则进行搜索；而深度优先搜索则按照 “后扩展出的节点先被考察” 的原则进行搜索。

宽度优先搜索是一种完备搜索即只要问题有解就一定能够求出；而深度优先搜索是不完备搜索。 

在不要求求解速度且目标节点的层次较深的情况下宽度优先搜索优于深度优先搜索因为宽度优先搜索效率低但却一定能够求得问题的解；在要求求解速度且目标节点的层次较浅的情况下深度优先搜索优于宽度优先搜索。因为当搜索算法在一个扩展的很深但又没有解的分支上进行搜索是一种无效搜索降低了求解的效率有时甚至不一定能求得问题的解。

5.8 什么是 A * 算法？它的估价函数是如何确定的？A * 算法与 A 算法的区别是什么？

A * 算法是一种启发式搜索方法利用这种算法进行搜索时对扩展节点的选择方法做了一些限制。

依据估价函数 f (x)=g (x)+h (x) 对 OPEN 表中的节点进行排序，并且要求启发函数 h (x) 是 h*(x) 的一个下界即 h (x)≤h*(z)。h*(x) 则是从 x 节点到目标节点的最小代价路径上的代价。

A * 算法与 A 算法的区别就是 A 算法不要求启发函数 h (x) 是 h*(x) 的一个下界即不限制条件 h (x)≤h*(x)。