1. 不带权搜索
| 算法 | BS 广度优先搜索 | TS 深度优先搜索 | TBS 深度限制搜索 | IV 迭代加深搜索 |
|---|---|---|---|---|
| 完整性 | 是 | 否（树高有限时“是”） | 是（t \ge d） |
是 |
| 最优 | 是 | 否 | 否 | 是 |
| 时间复杂度 | b^d |
b^m |
b^t |
b^d |
| 空间复杂度 | b^d |
bm |
bt |
bd |
b：分支因数
d：解的深度
m：树高
t：限制深度
完整性和最优性条件：
- 可解
- 有限分支因数
- 所有路径代价相同
树高有限则深度优先搜索完整，否则不具有完整性。
IV具有BS的时间复杂度，同时又有更好的空间复杂度。
