【答案-搜索算法】day06 探索路径

01）在宽度优先搜索（BFS）中，扩展节点的顺序是（ ） A. 按照节点的深度从深到浅 B. 按照节点的深度从浅到深 C. 随机选择节点 D. 按照节点的价值从高到低

参考答案：B

解题思路：宽度优先搜索（BFS）使用队列结构，先扩展深度较浅的节点，按层扩展，因此是按照深度从浅到深的顺序。

02）深度优先搜索（DFS）通常使用的数据结构是（ ） A. 队列 B. 栈 C. 堆 D. 优先队列

参考答案：B

解题思路：深度优先搜索（DFS）使用栈结构（显式或隐式），沿着一个分支一直深入到底，然后回溯。

03）A*算法是一种（ ） A. 盲目搜索算法 B. 启发式搜索算法 C. 贪婪算法 D. 动态规划算法

参考答案：B

解题思路：A*算法利用启发函数h(n)来指导搜索方向，属于启发式搜索算法，在满足可采纳性条件时能保证找到最优解。

04）在A*算法中，评估函数f(n) = g(n) + h(n)，其中g(n)表示（ ） A. 从起点到当前节点的实际代价 B. 从当前节点到目标节点的实际代价 C. 从当前节点到目标节点的估计代价 D. 路径的总代价

参考答案：A

解题思路：在A*算法中，g(n)表示从起始节点到当前节点n的实际代价（已知的），h(n)表示从当前节点n到目标节点的估计代价（启发函数）。

05）启发式搜索与盲目搜索的主要区别是（ ） A. 是否使用队列 B. 是否使用剪枝 C. 是否利用问题启发信息 D. 是否保证最优解

参考答案：C

解题思路：盲目搜索按照固定规则扩展节点，不利用任何问题相关信息；启发式搜索利用启发函数h(n)提供的启发信息来指导搜索方向，提高效率。

06）以下哪种搜索算法一定能找到最优解（ ） A. DFS B. BFS C. 贪婪算法 D. 随机搜索

参考答案：B

解题思路：在有限状态空间中，BFS（宽度优先搜索）按层次扩展，能够保证找到从起点到目标的最短路径（最优解）。DFS不保证最优解，贪婪算法和随机搜索也不保证。

07）A*算法的启发函数h(n)如果满足可采纳性条件，则一定能找到最优解。

答案解析：可采纳性（admissible）是指启发函数h(n)永远不会高估从节点n到目标节点的实际代价，即h(n) ≤ h*(n)，其中h*(n)是实际最小代价。

08）在状态空间搜索中，如果搜索树深度无限，则深度优先搜索可能陷入死循环。

答案解析：DFS沿着一条路径一直深入，如果搜索树深度无限且没有剪枝策略，则可能沿着一条无限路径一直搜索下去，无法找到解。

09）BFS算法的时间复杂度为O(b^d)，其中b为分支因子，d为深度。

答案解析：BFS在最坏情况下需要扩展所有深度小于等于d的节点，时间复杂度呈指数级增长。

10）启发式搜索中，h(n)的值越大，说明从当前节点到目标节点越近（容易到达）。

答案解析：h(n)表示从当前节点n到目标节点的估计代价，值越大表示估计代价越高，即距离目标越远；值越小表示距离目标越近。但需要注意，如果h(n)不满足可采纳性，则这个关系可能不成立。

11）简述宽度优先搜索（BFS）和深度优先搜索（DFS）的优缺点。

参考答案：

BFS（宽度优先搜索）优点：

BFS缺点：

DFS（深度优先搜索）优点：

DFS缺点：

12）说明A*算法中启发函数h(n)的作用，并解释为什么h(n)需要满足可采纳性。

参考答案：

启发函数h(n)的作用：启发函数h(n)估计从当前节点n到目标节点的最小代价。它引导搜索向目标节点方向进行，提高搜索效率。h(n)越大，表示估计从n到目标越近，搜索越有希望快速找到解。

可采纳性的必要性：可采纳性是指h(n) ≤ h*(n)，即h(n)不会高估实际代价。满足可采纳性时，A*算法能够保证找到最优解。如果h(n)不满足可采纳性（高估了代价），则可能错过最优解。

13）比较盲目搜索和启发式搜索的特点，并说明各自适用场景。

参考答案：

适用场景：