不知情的搜索技术

广度优先搜索需要存储节点的边界以供下次访问（“访问”基本上意味着：查看它是否是目标，生成它的子节点，否则添加到边界）。您可以将其内存需求可视化为金字塔；最初，您只有根节点。随着搜索过程的继续，你继续往下走，它会变得越来越宽（需要更多的内存）。在最坏情况下找到深度节点所需的内存量$d$可以表示为$O(b^d)$， 在哪里$b$是分支因子（请参阅此处的详细信息）。直观地说，每当你更深一层时，你的内存需求就会乘以一个因子$b$（你的金字塔变成$b$倍宽；实际上这意味着金字塔的形状并不完全正确，它应该迅速向外弯曲并且比三角形/金字塔更快地变宽）。

深度优先搜索还存储了下一个要访问的节点的边界（或 DFS 的情况下的堆栈）。但是，在 DFS 的情况下，这通常增长较慢。每当您访问一个节点（将其从堆栈中弹出）时，您都会生成它的所有子节点并将它们推送到堆栈顶部。然而，BFS 将继续“向右”访问一个相对“旧”的节点并再次生成其所有子节点，而 DFS 继续“向下”并访问一个刚刚被推入堆栈的子节点。一旦 DFS 完成了搜索树的一部分（您可以在脑海中将其想象为 DFS 已完成搜索，例如金字塔的左半部分），整个部分不再需要存储在内存中。$d$，最坏情况的空间复杂度是$O(bd)$（您必须一直搜索一条路径，直至达到$d$，并且对于这些级别中的每一个都有$b$堆栈中的节点）。

请注意，基于上述内容，将您的比较描述为“不知情”与“知情”搜索是不够的。我们只看到了不知情的搜索技术，并且已经有两种不同的内存要求。

在上面，我也没有考虑诸如您是否还记住您之前已经访问过的图形的哪些节点这样的微妙问题，以便您可以避免再次访问它们。这在树中不是必需的，但在具有循环的图中可能是必需的。

知情搜索技术

A * 可能是知情搜索算法中最典型的例子之一。在最坏情况下的内存需求方面，它与 BFS 非常相似；它还存储了接下来要访问的节点的边界，但根据对“好”的某种估计而不是广度优先顺序对这些节点进行优先级排序。如果您使用的信息（通常是已知/已发生成本 + 对未来成本的启发式估计的组合）质量极差，这可能会回归到广度优先搜索的水平，因此最坏情况下的空间复杂度与 BFS 相同（请参阅详细信息）。在实践中，如果你有高质量的信息（好的启发式），内存需求会很大不过更好；在理想/完美启发式的情况下，您的搜索算法几乎可以直接到达目标，几乎不需要任何内存。

还有一种称为迭代深化 A*的算法，它具有更好的空间复杂度，但代价通常是速度较慢。尽管如此，它仍然是一种使用与 A* 完全相同的信息的知情搜索算法。

所以，真的，内存需求不能用知情搜索与非知情搜索来描述。在这两种情况下，都有需要大量内存的算法和需要较少内存的算法。