思考题

5.1 什么是搜索？有哪两大类不同的搜索方法？两者的区别是什么？

搜索是在问题的状态空间中寻找从初始状态到目标状态的路径或序列的过程。搜索方法主要有两大类：盲目搜索（无信息搜索）和启发式搜索（有信息搜索）。

• 盲目搜索：不使用关于目标的任何额外信息，仅依靠问题的定义进行搜索。常见的盲目搜索策略有广度优先搜索（BFS）、深度优先搜索（DFS）等。
• 启发式搜索：利用启发信息（heuristic information）来指导搜索过程，优先探索更有可能 leading to the goal 的路径。常见的启发式搜索算法有 A* 算法等。

区别在于，盲目搜索不使用任何额外信息来指导搜索，而启发式搜索使用启发信息来优化搜索过程，通常更高效。

5.2 什么是启发式搜索？什么是启发信息？

• 启发式搜索：是一种利用问题领域知识来指导搜索过程的搜索方法，旨在提高搜索效率。
• 启发信息：是用于评估从当前状态到目标状态的“好”路径的估计值，通常表示为估价函数（如 f(n) = g(n) + h(n)），其中 h(n) 是启发函数，表示从节点 n 到目标的估计成本。

5.3 用状态空间法表示问题时，什么是问题的解？求解过程的本质是什么？什么是最佳解？最优解唯一吗？

• 问题的解：是从初始状态到目标状态的一条有效路径或序列。
• 求解过程的本质：是在状态空间中搜索从初始状态到目标状态的路径。
• 最佳解：是成本最低（或步数最少）的解。
• 最优解唯一性：不一定唯一，可能有多个最优解。

5.4 请写出状态空间图的一般搜索过程。在搜索过程中 open 表和 closed 表的作用分别是什么？有何区别？

• 状态空间图的一般搜索过程：
  1. 将初始状态加入 open 表。
  2. 如果 open 表为空，搜索失败，终止。
  3. 从 open 表中选择一个节点进行扩展，并将其移动到 closed 表。
  4. 生成该节点的所有子节点，并检查每个子节点是否是目标状态。如果是，搜索成功，终止。
  5. 将未在 open 表或 closed 表中的子节点加入 open 表。
  6. 重复步骤 2-5。
• open 表：用于存储待扩展的节点。
• closed 表：用于存储已扩展的节点。
• 区别：open 表用于选择下一个要扩展的节点，而 closed 表用于避免重复扩展同一节点。

5.5 什么是盲目搜索？主要有几种盲目搜索策略？