广西民族大学高级人工智能期末复习笔记（4）

盲目搜索与启发式搜索

选择题

1、

在启发式搜索中，哪个算法是利用启发信息来指导搜索的？
A) 广度优先搜索
B) 深度优先搜索
C) A*算法
D) 均匀代价搜索
答案：C) A*算法
解析：A*算法是启发式搜索的一种，它结合了最佳优先搜索的启发性以及Dijkstra算法的确保找到最佳解的特点。它使用一个启发式函数来估算从任意节点到目标节点的代价，以减少搜索范围并提高效率。

2、

盲目搜索算法不考虑哪种信息？
A) 路径代价
B) 状态空间
C) 目标状态
D) 启发信息
答案：D) 启发信息
解析：盲目搜索，也称为无信息搜索，是指不利用任何有关问题领域的特定知识来指导搜索的搜索策略。它不考虑启发信息，即不使用任何关于到达目标状态的路径代价的估计。

3、

哪个是不完全搜索策略？
A) A*算法
B) 迭代加深搜索
C) 广度优先搜索
D) 贪心最佳优先搜索
答案：B) 迭代加深搜索
解析：迭代加深搜索是一种将深度限制逐渐增加的深度优先搜索。虽然它能够找到解决方案，但不保证找到最优解。在某些情况下，如果问题空间是无限的或解的深度未知，迭代加深搜索可能无法找到解，因此它被认为是不完全的搜索策略。

判断题

1、

启发式搜索比盲目搜索需要更多的内存空间。（对/错）
答案：错
解析：启发式搜索（如A*搜索）通常更高效，因为它们使用启发式信息来指导搜索，从而减少了必须探索的状态数量。相比之下，盲目搜索（如广度优先搜索）不使用额外信息，可能会探索大量无关的路径，导致在最坏情况下空间复杂度非常高。

2、

广度优先搜索在最坏情况下的空间复杂度是指数级的。（对/错）
答案：对
解析：广度优先搜索（BFS）在最坏情况下需要存储所有扩展出的节点，在完全二叉树中，这意味着每增加一层，存储的节点数几乎翻倍。因此，其空间复杂度是指数级的，这可以迅速消耗大量内存。

3、

A*算法保证找到最优解，前提是启发函数是可采纳的。（对/错）
答案：对
解析：A*算法能够保证找到最优解，条件是其使用的启发函数是相容的（或称为可采纳的），即启发函数不会高估从任何节点到达目标节点的实际成本。

应用题

1、给定一个8拼图问题，使用A*算法解决该问题。假设初始状态是[5,1,3,4,2,6,7,8,0]，目标状态是[1,2,3,4,5,6,7,8,0]，启发函数h(n)定义为不在位的数码个数。请问初始节点的f(n) = g(n) + h(n)值是多少？这里g(n)是从初始状态到当前状态的实际代价，h(n)是启发函数的估计代价。

答案：
- 初始状态的g(n)值为0，因为还没有任何移动。
- h(n)的值为3，因为数字1, 2, 和 5 不在正确位置上。
- 因此，f(n) = g(n) + h(n) = 0 + 3 = 3。

解析：
- g(n)代表从起始状态到当前状态的实际步骤数，在初始状态下为0。
- h(n)是启发式函数，计算不在目标位置的数码个数，在这里是3个。
- f(n)是A*算法中用于比较的评估函数，它是g(n)和h(n)的总和。