人工智能 第2章 课后习题

讨论题

1．搜索为什么是 AI 系统的重要组成部分？

人工智能中的搜索指依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程，是AI系统的核心内容。

2．状态空间图是什么？

状态空间图是对问题的一种表示方法，将某个具体问题的解对应为状态空间图中的一条路径，使人们可以根据空间图探索和分析通往解的可能的可选路径。

3．描述生成-测试范式。

生成-测试范式是问题求解的一种直接方式，即先给出可能的解，再检查每个可能的解，看是否有候选解能够构成问题的解。

4．生成器有什么属性？

可以一边循环一边进行计算。

5．回溯法如何对完全枚举法进行改进？

完全枚举法会在已经发现当前步骤不可能成功得到解的情况下，还可能从部分解开始进一步往后搜索。而回溯法在发现当前步骤不可能成功得到解的情况下，会返回上一个步骤重新求解，避免了许多无意义的计算。

6．用一两句话描述贪心算法。

贪心算法将解决一个问题分为若干个步骤，并在每一个步骤中求最优解但不一定是整体的最优解。

7．陈述旅行商问题

给定 n 个顶点的加权图（即每条边上带有开销值），求从某个顶点 Vi出发经过加权图中的所有顶点（每个顶点只经过一次），然后返回到 Vi的最短路径，即寻找最短的回路。

8．简述 3 种盲目搜索算法。

深度优先搜索（DFS），是试图尽可能快地深入树中进行搜索。每当搜索方法可以做出选择时，就选择最左（或最右）分支（通常选择最左分支）。

广度优先搜索（BFS），以从左到右（或从右到左，不过从左到右更常见）的方式，可以逐层访问节点。必须首先访问第 i层的所有节点，然后才能访问第 i +1 层的节点。

迭代加深的深度优先搜索（DFS-ID），与深度优先搜索类似，但是对搜索的深度进行了限制，使得在搜索到限制深度后必须开始新的搜索路径。在每一次深度优先搜索结束后，都会改变深度限制，通常为加一。

9．在何种意义上，盲目搜索算法是盲目的？

盲目搜索方法又叫非启发式搜索，是一种无信息搜索，一般只适用于求解比较简单的问题，盲目搜索通常是按预定的搜索策略进行搜索，而不会考虑到问题本身的特性。

盲目搜索算法是不使用领域知识的不知情搜索算法。这些方法假定不知道状态空间的任何信息。

它们不使用启发式估计。如果使用启发式估计，那么搜索将沿着最有希望得到解决方案的路径前进。

10．按照完备性、最优性和时空复杂性，比较本章描述的 3 种盲目搜索算法。

BFS

• 完备性：当树的分支因子 b 是有限的，则算法是完备的。
• 最优性：如果路径代价是基于结点深度的非递减函数，则算法是最优的，否则不具备最优性。
• 复杂性：显然时空复杂度均为 O(bd)。

DFS

• 完备性：对于树搜索，DFS 总是不完备的；而对于图搜索，DFS 在有限状态空间下是完备的，而在无限状态空间下是不完备的。
• 最优性：显然不是最优的
• 复杂性：时间复杂度为 O(bm)，空间复杂度为 O(bm)，可见其空间复杂度比上述两种搜索小很多，这也是深度优先搜索最大的优势。

DFS-ID

IDS 算法评估（设分支因子为 b，限定的深度为 l，最浅的目标结点的深度为 d）：

完备性：当分支因子是有限的的时候，IDS 是完备的
最优性：类似于宽度优先搜索算法，如果路径代价是基于结点深度的非递减函数，则算法是最优的。
复杂性：时间复杂度为 O(bd)，空间复杂度为 O(bd)。

11．在什么情况下，DFS 比 BFS 好？

树很深。

分支因子不太大，并且

解出现在树中的位置相对较深。

12．在什么情况下，BFS 比 DFS 好？

搜索树的分支因子不太大（一个适度的 b 值）。当整棵树的分支因子实际上很大时，BFS 会因为有过多的路径需要探索而不堪重负。

解出现在树中的位置在合理的深度（一个适度的 d 值），并且

所有路径都不是特别深。

13．在什么意义上，可以说 DFS-ID 是 BFS 和 DFS 的折中？

DFS-ID 可以作为 BFS 和 DFS 的折中；在搜索树上，尤其是在深度为 0、1、2 等受限深度的搜索树上，DFS-ID 执行的是一个完备的 DFS 搜索过程。换句话说，DFS-ID 同时具有 DFS 和 BFS 的优点，即 DFS 的中等存储空间需求以及 BFS 的完备性和最优性。

练习题

1．在只允许称重 3 次的情况下，求解 12 枚硬币的假币问题。回忆一下，天平可以返回以下 3 种结果之一：相等、左侧轻或左侧重。

先取1234与5678称重若1234=5678，再取123与91011称重，如果123=91011，则假币为12，再取1与12称重，确定假币是轻还是重。

另一种情况，第一次称重，1234与5678，1234>5678，第二次称重，1235与491011，如果1235>491011，那么可以确定假币在1 2 3中(这里可以用假设法，假设4为假币，那么4就应该是轻的假币，这与1 2 3 4>5 6 7 8相矛盾，所以4为正币，4为正币，那么假币就在1 2 3 5之间，假设5为假币，那么5就应该是重的假币，这与1 2 3 4>5 6 7 8相矛盾，所以5为正币)，且假币较重。第三次称重，用1和2称重，如果1=2，那么3为假币，如果1>2,那么1为假币，如果1<2,那么2为假币。
其他情况以此类推。

2．在只称重两次的情况下，求解微型假币问题或证明这是不可能的。

称重两次一共有9种状态，6枚硬币一共6*2=12种可能，9<12所以不可能。

3．非确定性搜索（nondeterministic search）是本章未讨论的一种盲目搜索方法。在这种搜索

中，刚刚扩展的子节点以随机顺序放在开放表中。请判断非确定性搜索是否完备以及是否最优。