外观
无信息搜索
约 699 字大约 2 分钟
2025-02-26
1. 定义与基本概念
无信息搜索（Uninformed Search），又称盲目搜索（Blind Search），是指搜索过程中不依赖任何问题定义之外的启发信息，仅基于状态空间的扩展规则进行遍历的策略。其核心特点是：
- 仅通过生成后继节点和判断目标状态来探索解空间；
- 搜索顺序由节点的扩展规则决定（如广度优先、深度优先等）；
- 评价标准包括完备性、最优性、时间复杂度和空间复杂度。
2. 无信息搜索的特点
| 特性 | 描述 |
|---|---|
| 完备性 | 当问题存在解时，算法是否总能找到解（如BFS是完备的，DFS在无限空间下不完备） |
| 最优性 | 能否找到代价最小的解（如一致代价搜索UCS具备最优性） |
| 时间复杂度 | 通常为指数级复杂度（如BFS的时间复杂度为O(b^d)，b为分支因子，d为解的深度） |
| 空间复杂度 | 取决于存储中间节点的数据结构（如DFS的空间复杂度为O(bm)，m为最大深度） |
3. 各算法详解
| 算法 | 数据结构 | 完备性 | 最优性（条件） | 时间复杂度 | 空间复杂度 | 核心策略 |
|---|---|---|---|---|---|---|
| 广度优先 (BFS) | 队列 (FIFO) | 是（有限状态空间） | 是（路径代价与深度非递减） | O(bᵈ) | O(bᵈ) | 逐层扩展，保证最短路径 |
| 一致代价 (UCS) | 优先队列 | 是（非负权边） | 是（带权图最短路径） | O(b^(1+C/ε)) | O(b^(1+C/ε)) | 按实际路径成本扩展 |
| 深度优先 (DFS) | 栈 (LIFO) | 有限状态空间下是 | 否 | O(bᵐ) | O(b·m) | 深入到底再回溯 |
| 深度受限 (DLS) | 栈 | 若限制深度≥解深度 | 否 | O(bˡ) | O(b·l) | 限制最大深度l的DFS |
| 迭代加深 (IDS) | 栈 | 是 | 是（路径代价与深度非递减） | O(bᵈ) | O(b·d) | 动态增加深度限制的DFS |
| 双向搜索 | 双队列/双栈 | 是（交汇条件满足） | 是（若双向BFS） | O(2b^(d/2)) | O(b^(d/2)) | 起点与终点同步扩展 |
参数说明
- b: 分支因子（每个节点的平均子节点数）
- d: 解的深度（最短路径层级）
- m: 状态空间最大深度
- C: 最优解的总代价
- ε: 最小边权（一致代价搜索中）
- l: 深度限制（DLS中预设的探索上限）
版权所有
版权归属：NateHHX