《启发式搜索的分类》作业 一、选择题 1. 启发式搜索中，根据是否考虑路径代价和启发式估计，可以将搜索算法分为哪几类？ A. 盲目搜索和启发式搜索 B. 深度优先搜索和广度优先搜索 C. A搜索和贪心最佳优先搜索 D. 确定性搜索和不确定性搜索 答案：A 解析：在启发式搜索中，根据是否考虑路径代价和启发式估计，搜索算法可以分为盲目搜索（如深度优先搜索和广度优先搜索）和启发式搜索（如A搜索和贪心最佳优先搜索）。盲目搜索不考虑任何启发式信息，而只关注已知的路径成本；启发式搜索则利用启发式信息来指导搜索过程。 2. 以下哪种搜索算法是启发式搜索的典型代表？ A. Dijkstra算法 B. A算法 C. 深度优先搜索 D. 广度优先搜索 答案：B 解析：A算法是启发式搜索的典型代表之一，它结合了Dijkstra算法的最佳优先搜索策略和启发式搜索的优势，能够在保证找到最短路径的同时提高搜索效率。 3. 在启发式搜索中，如果评价函数总是返回0，这种搜索策略被称为？ A. 无信息搜索 B. 广度优先搜索 C. 深度优先搜索 D. A搜索 答案：A 解析：如前所述，如果评价函数总是返回0，意味着没有启发式信息可用，此时搜索将退化为无信息搜索，即按照节点的生成顺序进行扩展，直到找到目标。 4. 在启发式搜索中，当评价函数低估了实际代价时，这种搜索策略被称为？ A. 乐观估计 B. 悲观估计 C. 精确估计 D. 不确定估计 答案：A 解析：如前所述，当评价函数低估了实际代价时，这种搜索策略被认为是乐观的，因为它对找到解决方案持乐观态度。 5. 在启发式搜索中，以下哪种算法不是基于启发式信息的？ A. A算法 B. Greedy Best First Search C. Dijkstra算法 D. Uniform Cost Search 答案：C 解析：如前所述，Dijkstra算法是一种基于广度优先搜索的算法，它不考虑任何启发式信息，只关注已知的路径成本。而A、Greedy Best First Search和Uniform Cost Search都使用启发式信息来指导搜索过程。 二、填空题 6. 启发式搜索是一种利用_____来指导搜索过程的方法。 答案：先验知识/启发式信息 解析方法：启发式搜索通过使用先验知识（如经验规则、直觉或近似解）来评估不同路径的潜在价值，从而更高效地找到解决方案。 7. 在启发式搜索中，_____函数用于计算从当前状态到目标状态的估计代价。 答案：启发式/估价 解析方法：启发式函数（或估价函数）是启发式搜索的核心组成部分，它提供了一种快速估计从当前状态到目标状态代价的方法，帮助算法决定哪些路径更有可能接近最优解。 8. A算法结合了_____算法的最佳优先搜索和Dilkstra算法的启发式搜索。 答案：Dijkstra 解析方法：A算法通过结合Dijkstra算法的最佳优先搜索策略（即总是选择代价最低的节点进行扩展）和启发式搜索的优势（即使用启发式信息来估计剩余代价），能够在保证找到最短路径的同时提高搜索效率。 9. 在启发式搜索中，如果评价函数总是返回0，搜索将变成_____搜索。 答案：广度优先 解析方法：如前所述，如果评价函数总是返回0，意味着没有启发式信息可用，此时搜索将退化为广度优先搜索。 10. 在启发式搜索中，当评价函数低估了实际代价时，这种搜索策略被称为_____估计。 答案：乐观 解析方法：如前所述，当评价函数低估了实际代价时，搜索策略被认为是乐观的，因为它对找到解决方案持乐观态度。 11. 在启发式搜索中，_____算法是一种基于广度优先搜索的算法，它不考虑任何启发式信息。 答案：Dijkstra 解析方法：如前所述，Dijkstra算法是一种经典的单源最短路径算法，它通过广度优先搜索的方式遍历图中的所有节点，并记录到达每个节点的最短路径长度。由于它不考虑任何启发式信息，因此可以保证找到的是最优解。 12. 在启发式搜索中，_____搜索总是选择当前看起来最有希望的节点进行 ... ...
