搜索

---

搜索问题的数学建模（状态空间图）

完备性：解存在时，算法能否保证找到。

代价最优性：算法能否找到代价最小的解。

时间复杂度：找到解所需的时间或操作数。

空间复杂度：执行算法所需的内存。

无信息搜索

算法不利用目标状态的任何领域知识，仅根据既定策略探索状态空间。

• 广度优先搜索BFS——像水一样在迷宫中蔓延

  • 逐层扩展节点，先扩展根节点，再扩展其所有子节点，依此类推。
  • 完备性：在分支因子有限时，是完备的（若解存在，则一定能找到）。
  • 最优性：当所有动作代价相同时，BFS找到的是动作步数最少（即代价最小）的解。其最优性可通过反证法证明：假设存在一个更优解，其节点必然出现在更浅的层，但BFS会先访问到该节点，矛盾。
  • 复杂度：在最坏情况下，时间和空间复杂度均为 O(b^d)，其中b是分支因子，d是最浅解的深度。

• 深度优先搜索DFS——走入迷宫，不断尝试

  • 优先深入探索一条路径，直到无法继续（叶子节点或达到深度限制），然后回溯。
  • 完备性：在无限状态空间或存在环的情况下，不完备（可能陷入无限分支）。
  • 最优性：不是最优的，可能找到非代价最小的解。
  • 复杂度：最坏时间复杂度为 O(b^m)，m是状态空间的最大深度；空间复杂度为 O(bm)，因为只需存储当前路径和待探索的兄弟节点。

• 一致代价搜索——结点被到达的顺序就是代价的排序

  • 扩展当前路径累积代价最小的节点。可视为在动作代价不均为1的图上的Dijkstra算法。
  • 完备且代价最优。

指数爆炸问题：搜索算法的时间/空间复杂度通常是指数级的\( O(b^d) \)，这限制了其在大型问题（如围棋）上的直接应用。

About 无信息搜索

在考试中给了一张图问你这是哪种搜索（选择题）

启发式搜索

现在，我们有了一些信息——算法利用启发式函数 h(n) 来估计从当前状态n到目标状态的最低代价，以指导搜索方向。

• 贪心策略

  • 总是扩展 h(n) 值最小的节点，即估计最接近目标的节点。
  • 性能：不完备（可能陷入死循环），也非最优，但通常较快。

• A*搜索

  • 结合UCS和贪婪搜索，评估函数为 f(n) = g(n) + h(n)，其中g(n)是从起点到n的实际代价，h(n)是到目标的估计代价。总是扩展 f(n) 最小的节点。
  • 可容许启发式：对于所有节点n，满足 0 ≤ h(n) ≤ h(n)，其中h(n)是真实代价。定理：若启发式函数是可容许的，则A*算法是代价最优的。
  • 一致性启发式：对于任意节点n及其后继n‘，满足 h(n) ≤ c(n, a, n’) + h(n‘)。一致性蕴含可容许性。在一致性启发式下，A*算法效率更高，每个节点最多被扩展一次。