关于这个概念总是有很多混淆，因为命名具有误导性，因为树和图搜索都会在探索搜索空间时生​​成一棵树（您可以从中得出路径），这通常表示为一个图。

差异

首先，我们必须了解底层问题（或搜索空间）几乎总是表示为一个图（尽管底层图可能不包含循环，因此它可能表示一棵树）。因此，区别不在于问题是树（一种特殊的图）还是一般图！

相反，区别在于我们如何遍历搜索空间（表示为图形）来搜索我们的目标状态，以及我们是否使用了额外的列表（称为封闭列表）。

所以，基本的区别是

1. 在图搜索的情况下，我们使用一个称为封闭列表（也称为探索集）的列表来跟踪已经访问和扩展的节点，以便它们不再被访问和扩展。

2. 在树搜索的情况下，我们不保留这个封闭列表。因此，可以多次（甚至无限次）访问同一节点，这意味着生成的树（通过树搜索）可能包含多次相同的节点。

的优点和缺点

图搜索的优点显然是，如果我们完成了一个节点的搜索，我们将永远不会再搜索它。另一方面，树搜索可以多次访问同一个节点。

图搜索的缺点是它比树搜索使用更多的内存（我们可能有也可能没有）。这很重要，因为在最坏的情况下，图搜索实际上具有指数内存需求，如果没有真正好的启发式搜索或非常简单的问题，它就变得不切实际。

因此，在使用图搜索而不是树搜索（反之亦然）时，需要在空间和时间之间进行权衡。

结论

因此，树搜索和图搜索之间的区别不在于树搜索适用于树，而图搜索适用于图！两者都可以在树或图上工作（但是，鉴于图是树的泛化，我们可以简单地说两者都在图上工作，无论是否是树）并且都产生一棵树！

笔记

上面给出的树搜索和图搜索的定义基于Stuart J. Russell 和 Peter Norvig 所著的《人工智能：现代方法》（第 3 版）一书第 3.3 节（第 77 页）中给出的定义，该书是德- 人工智能中的事实标准书，因此这些定义适用于人工智能的上下文（这也是本站的上下文）。这里有树和图形搜索的伪代码（由 P. Norvig 提供）。

但是，请注意，有时人们可能会使用术语树搜索来指代树遍历，它用于指代搜索树（例如，二叉搜索树或红黑树）中的搜索，即一棵树（即没有循环的图）保持其元素的特定顺序。这是对树搜索有不同定义并认为树搜索仅适用于树的另一个原因。