1.
广度优先搜索
在广度优先搜索，搜索树从顶部按图中给出的算法探索给底部 6.6 页上的 90 ，直到找到一个解。首先，测试节点列表中的每个节点是否是目标节点，并且在成功的情况下，程序停止。否则，将生成节点的所有后继节点。然后在所有新生成的节点的列表上递归地继续搜索。整个过程重复进行，直到不再生成后继者为止。
该算法是通用的。也就是说，如果提供了两个特定于应用程序的函数“GoalReached”和“Successors”，它适用于任意应用程序。“GoalReached”计算参数是否为目标节点，“Successors”计算其参数的所有后继节点的列表。图 6.7 页 90 显示广度优先搜索的快照。
B READTH – FIRST – SEARCH（NodeList，Goal）
NewNodes =∅
如果GoalReached（节点，目标）
返回（“找到解决方案”，节点）
NewNodes = Append（NewNodes，Successors（Node））
返回（B READTH – FIRST – SEARCH（NewNodes，Goal））
其他
返回（“无解”）
如果NewNodes =∅
对于所有节点∈节点列表
图6.6 广度优先搜索算法
图6.7 第三级节点扩展期间的广度优先搜索。节点根据生成的顺序进行编号。尚未生成的
分析由于广度优先搜索完全搜索每个深度并在有限时间内到达每个深度，如果分支因子b 是有限的，则完成。如果所有操作的成本相同，则找到最佳（即最短）解决方案（参见第110 页的练习6.7）。计算时间和存储空间随着树的深度呈指数增长。对于具有恒定分支因子b和深度d的树，因此总计算时间由下式给出
d
c ・
i = 0
bi =
b d +
1 – 1
b – 1
= O（bd）。
虽然只有最后一级保存在内存中，但内存空间要求也是O（bd）。
凭借当今计算机的速度，可以在几分钟内生成数十亿个节点，主存储器迅速填满，搜索结束。不总是找到最短解的问题可以通过所谓的统一成本搜索来解决，其中具有最低成本的节点从上升排序
D EPTH – 第一 – 搜索（节点，目标）
如果GoalReached（节点，目标）返回（“找到解决方案”）
NewNodes =后继者（节点）
结果= D EPTH – 第一次 – 搜索（第一个（新节点），目标）
如果Result =“找到解决方案”返回（“找到解决方案”）
NewNodes = Rest（NewNodes）返回（“无解”）
而NewNodes =∅
图6.8 深度优先搜索算法。函数“First”返回列表的第一个元素，并“休息”列表的其余部分
节点列表总是被扩展，新节点排序。因此我们找到了最佳解决方案。但是，内存问题尚未解决。深度优先搜索提供了针对该问题的解决方案。
2.
深度优先搜索
在深度优先搜索中，一次只有少数节点存储在存储器中。扩展节点后，只保存其后继节点，并立即展开第一个后继节点。因此，搜索很快变得非常深刻。只有当节点没有后继并且搜索在该深度处失败时，下一个打开节点才会通过回溯扩展到最后一个分支，依此类推。我们可以在图
6.8中的优雅递归算法和第 92页的图 6.9中的搜索树中最好地理解这一点。
・
分析深度优先搜索比广度优先搜索需要更少的内存，因为在每个深度处最多保存b个节点。因此我们需要bd存储单元。但是，对于无限深度树，深度优先搜索不完整，因为当最左边分支中没有解时，深度优先搜索会进入无限循环。因此，找到最佳解决方案的问题已经过时。由于无限循环，不能给出计算时间的限制。在具有深度d的有限深度搜索树的情况下，生成总共约bd个节点。
因此，计算时间增长，就像在广度优先搜索中一样，随着深度呈指数增长。
我们可以通过设置深度限制来使搜索树有限。现在，如果在修剪的搜索树中找不到解决方案，那么仍然可以是超出限制的解决方案。因此搜索变得不完整。然而，有一些明显的想法可以使搜索完整。
图6.9 执行深度优先搜索。深度为3的所有节点都不成功并导致反向跟踪。节点按生成顺序编号
图6.10 搜索树的迭代深入开发具有限制的示意图从1到7的树的广度对应于2
3.
迭代深化
我们开始深度优先搜索，深度限制为1.如果没有找到解，我们将限制提高1并从头开始搜索，依此类推，如图6.10 所示。这种深度限制的迭代提升称为迭代加深。
=∅
我们必须使用两个附加参数“Depth”和“Limit” 来扩充第
91 页的图 6.8中给出的深度优先搜索程序。“深度”是通过一个在递归调用提高，while循环的头行被替换为“ 虽然NewNodes 和深度< 限制”。修改后的算法如第 93 页的图 6.11 所示。
–
分析内存要求与深度优先搜索相同。有人可能会争辩说，在深度为零的情况下反复重新开始深度优先搜索会导致大量的冗余工作。对于大分支因子，情况并非如此。我们现在表明，在搜索的所有树中，直到最后一个dmax 1 之前的所有深度的节点数的总和远小于搜索的最后一个树中的节点数。
I TERATIVE D EEPENING（节点，目标）
DepthLimit = 0
重复
结果= d EPTH ˚F IRST小号EARCH -B（节点，目标，0，深度优先搜索）
DepthLimit = DepthLimit + 1
d EPTH ˚F IRST小号EARCH -B（节点，目标，深度，限制）
如果GoalReached（节点，目标）返回（“找到解决方案”）
而 NewNodes =∅ 和深度 <限制
如果Result =“找到解决方案”返回（“找到解决方案”）NewNodes = Rest（NewNodes）
返回（“无解”）
d EPTH ˚F IRST小号EARCH -B（初（NewNodes），目标，深度+ 1，限制）
结果=
NewNodes =后继者（节点）
直到Result =“找到解决方案”
图6.11迭代加深算法，调用带有深度限制的略微修改的深度优先搜索（T IEFENSUCHE -B）
令Nb（d）为具有分支因子b的搜索树的节点数，并且深度d和dmax是搜索的最后深度。搜索到的最后一棵树包含
Nb（dmax）=
d 最大
i = 0
bi =
b d max + 1 – 1
b – 1
节点。事先一起搜索过的所有树木都有
d max – 1
Nb（d）=
d m a x – 1 b d +
1 – 1
1 d m a x –
1
b d + 1
– dmax + 1
d = 1
d = 1
b – 1
b – 1
d = 1
=
b d
最多 1 天
– dmax + 1
=
b – 1
d = 2
1 bd max +
1 – 1 – – – +
= b – 1
b – 1
1 b dmax 1
1 bd max +
1 – 1 1
≈ b – 1
b – 1
= b – 1 Nb（dmax）
表6.1不知情搜索算法的比较。（*）表示只有持续的行动成本才能使该陈述成立。d s是有限搜索树的最大深度
|
广度优先搜索 |
统一成本搜索 |
深度优先搜索 |
迭代加深 |
|
|
完整性 |
是 |
是 |
没有 |
是 |
|
最佳解决方案 |
是的（*） |
是 |
没有 |
是的（*） |
计算时间 b d
b d ∞ 或 b d 小号 b d
记忆用途 b d b d bd bd
b – 1
= – =
节点。对于b> 2，这小于最后一棵树中节点的数量Nb（dmax）。为b
20中的第一DMAX 1种树木一起含有仅约1 1 / 19中的最后一个树节点的数目的。除了最后一次迭代之外的所有迭代的计算时间都可以忽略。
就像广度优先搜索一样，这个方法是完整的，并且给定所有操作的固定成本，它找到最短的解决方案。
4.
对照
所描述的搜索算法已并列在表 6.1中。
我们可以清楚地看到，迭代深化是此测试的赢家，因为它在所有类别中都获得了最佳成绩。事实上，在所有四种算法中，它是唯一实用的算法。
×
我们确实有这个测试的赢家，但对于实际应用，它通常不会成功。即使是15拼图，8拼图的大哥（见第 110 页的练习 6.4 ），也有大约2 10 13个不同的状态。对于非平凡的推理系统，状态空间要大许多个数量级。如Sect。中所示。6.1 ，世界上所有的计算能力都无济于事。相反，我们需要的是一种智能搜索，它只能探索搜索空间的一小部分并在那里找到解决方案。
