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的时间复杂度,同时又有更好的空间复杂度。