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