图搜索和树搜索有什么区别？

Question

在人工智能中，图搜索和树搜索版本在深度优先搜索（DFS）、A*搜索方面有何区别？

- Rayhanur Rahman

Answer 1

根据现有答案，似乎对于这个概念存在很多混淆。

问题总是一个图

树搜索和图搜索的区别不在于问题图形是树还是一般图形。通常假设你正在处理一般图形。区别在于用于搜索图形的遍历模式，可以是图形状或树形状。

如果你正在处理树形问题，则两种算法变体都会导致等效结果。因此，您可以选择更简单的树搜索变体。

图搜索和树搜索的区别

基本的图搜索算法如下所示。使用起始节点 start、以successors为指向方向的边和goal规范用于循环条件。 open 保存当前正在考虑的节点（“open list”）。请注意，以下伪代码在某些方面不正确（2）。

树搜索

open <- []
next <- start

while next is not goal {
    add all successors of next to open
    next <- select one node from open
    remove next from open
}

return next

根据您如何实现 select from open，您可以获得不同变种的搜索算法，例如深度优先搜索（DFS）（选择最新的元素）、广度优先搜索（BFS）（选择最旧的元素）或统一代价搜索（选取路径代价最低的元素），通过选择具有最低 代价加启发式 值的节点进行的流行的A星搜索等。

上述算法实际上被称为树搜索。如果在起始状态中存在多条指向它的直接路径，则它将多次访问基础问题图的状态。如果一个状态位于定向循环中，则甚至可能无限次访问该状态。但每次访问对应于我们的搜索算法生成的不同节点中的一个。这种明显的低效率有时是有用的，稍后会解释。

图搜索

正如我们所看到的，树搜索可以多次访问一个状态。因此它将探索在此状态后找到的"子树"多次，这可能是昂贵的。图搜索通过在封闭列表中跟踪所有已访问的状态来修复这个问题。 如果已知 next 的新继承者，则它不会插入开放列表中：

open <- []
closed <- []
next <- start

while next is not goal {
    add next to closed
    add all successors of next to open, which are not in closed 
    remove next from open
    next <- select from open
}

return next

比较

我们注意到图搜索需要更多的内存，因为它要跟踪所有已访问的状态。这可以通过更小的开放列表来补偿，从而提高搜索效率。

最优解

一些实现“选择”方法的技巧可以保证返回最优解——即最短路径或者具有最小成本（对于拥有边缘代价的图形）。当节点按照成本递增的顺序扩展时，或者成本是非零正常数时，这基本上是可行的。实现此类选择的常见算法包括单调费用搜索，或者如果步骤成本相同，则使用BFS或IDDFS。IDDFS避免了BFS的过度内存消耗，通常推荐在步长恒定的未知搜索（也称为暴力搜索）中使用。

A*

此外，当与一个可接受启发式方法配合使用时，（非常流行的）A*树搜索算法也可以提供最优解。然而，只有在与一个一致（或“单调”）启发条件（比可接受性更强）配合使用时，A*图搜索算法才能提供此功能。

(2) 伪代码的缺陷

为了简单起见，所示代码不包括以下内容：

• 处理失败的搜索，即仅适用于可以找到解决方案的情况

- ziggystar

---

很棒的详细回答！您能详细说明一下“树形问题”的含义吗？此外，您如何建议存储算法到达目标所经过的路径，而不是完整遍历的路径？ - Brian

@Brian 树形问题意味着你正在搜索的图是一棵树。至于你的第二个问题：这取决于具体的问题。一个可能的解决方案是，如果可行的话，将每个扩展节点的路径与节点一起存储。 - ziggystar

树搜索中，一个“单个状态”可以被访问多次，而非节点。因为搜索树中的每个节点都对应着状态空间图中的单条路径，并且最多只会被树搜索访问一次。（尽管这不适用于迭代加深搜索，该算法按深度限制逐渐遍历树，但在每次迭代中，每个节点也只会被访问一次。） - Nader Ghanbari

@NaderhadjiGhanbari 不管是在问题图中还是在遍历图中，对于顶点来说，使用state或node哪个更合适取决于上下文。但是，在问题图的顶点中使用state，在遍历图中使用node可以明确答案。我会尽快重写它。谢谢。 - ziggystar

@berimbolo 是的，这是可能的。请注意，您可以通过改变一些小事实来创建许多不同的算法变体。例如，通过将开放列表视为有限封闭列表，使树搜索行为有点像图形搜索。并非所有这些微调都有名称。 - ziggystar

Answer 2

树是图的一种特殊情况，所以适用于一般图的算法也适用于树。树是一种图，其中每对节点之间恰好有一条路径。这意味着它不包含任何循环，正如先前的答案所述，但是没有循环的有向图（有向无环图，DAG）不一定是树。

然而，如果您知道您的图有一些限制，例如它是一棵树或DAG，则通常可以找到比未受限制的图更有效的搜索算法。例如，在树上使用A*或其非启发式对应物“迪杰斯特拉算法”可能没有太多意义（在那里只有一条可供选择的路径，您可以通过DFS或BFS找到），或者在DAG上使用（其中可以通过按照拓扑排序获得的顶点顺序来查找最优路径）。

至于有向与无向，无向图是有向图的一种特殊情况，即遵循规则“如果从u到v有一条边（链接，转换），则从v到u也有一条边”。

更新：请注意，如果您关心搜索的遍历模式而不是图本身的结构，则这不是答案。请参见，例如ziggystar的答案。

- njlarsson

---

嗯，这个问题的背景对我来说并不是完全清楚的，但在看了你的答案之后，@ziggystar，我确实有一种感觉，提到A*和AI表明你可能是正确的，而我的答案则是脱离了上下文的。我把"tree search"解释为“搜索树”。而不是“使用树形遍历模式搜索一般图形”，这正是你的答案所暗示的。 - njlarsson

@njlarsson，我在我的答案中包含了你的重新表述。这对于澄清很有帮助。 - ziggystar

在答案中添加了这个注释。我怀疑我的答案对于通过Google等途径找到这里的许多人来说是正确的，即使它可能与Rayhanur Rahman想要的上下文不符。 - njlarsson

我见过很多学生在学习搜索算法时遇到困难，你的回答只会误导他们。 - Nader Ghanbari

这个问题是关于搜索算法，而不是关于图论的一般性问题。因此，我不确定这个答案对这里有多大帮助，因为它实际上并没有区分输入到搜索中的图和搜索创建的图或树之间的区别。 - mlibby

答案也涉及到搜索算法，但确实不是发布者所问的内容。请看答案中的“更新” - 我在2014年3月意识到我误解了问题。我没有删除答案的原因是它仍然可能对通过搜索来到这里的某些人有用。 - njlarsson

Answer 3

图和树的唯一区别在于是否存在环。图可以包含环，而树不行。因此，在树上实现搜索算法时，无需考虑环的存在，但是在处理任意图形时，必须考虑它们。如果不处理环，算法可能最终会陷入无限循环或无尽递归。

另一个需要考虑的问题是您要处理的图形的方向属性。在大多数情况下，我们处理代表每个边缘的父子关系的树。有向无环图（DAG）也具有类似的特征。但是，双向图形是不同的。双向图中的每个边缘表示两个邻居。因此，这两种类型的图形的算法方法应有所不同。

- Sufian Latif

---

此外，如果你确实拥有一棵树，在A*算法中就不需要进行重复检测。然而，你仍然需要一种方法来提取最终路径，因此可能仍需要使用关闭列表。 - Nathan S.

一般来说，树是一个有向图，任意两个顶点之间最多只有一条路径。也就是说，图和树之间有两个不同之处：有向性和路径唯一性。在DAG上运行的算法无需检查循环，而在树上运行的算法无需检查重复项。 - thiton

术语有所不同，但树并不总是被视为有向的。对于一个有根树，即当指定一个节点为根时，存在一个暗示的方向，但树不必是有根的。此外，一般图可以是有向的或无向的。此外，如果您只要求两个顶点之间最多有一条路径，则还包括森林。树通常被定义为连通图，即必须有精确地一条路径。 - njlarsson

这个答案更关注于图论中树和图的区别，而不是不同类型的搜索算法。 - mlibby

Answer 4

图形与树

• 图形有循环
• 树没有循环，“例如，在您的脑海中想象一棵树，分支没有直接连接到根，但分支与其他分支有连接，向上”

但是在AI图形搜索和树搜索的情况下

图形搜索具有一个好的属性，无论使用哪种算法，每当算法探索新节点并将其标记为已访问时，该算法通常会探索从当前节点可达的所有其他节点。

例如，考虑以下具有3个顶点A B和C的图形，并考虑以下边缘

A-B，B-C和C-A，嗯，有一个从C到A的循环，

当从A开始进行DFS时，A将生成一个新状态B，B将生成一个新状态C，但是当探索C时，算法将尝试生成一个新状态A，但是A已经被访问，因此将被忽略。酷！

那么树呢？好吧，树算法不会将已访问的节点标记为已访问，但是树没有循环，它如何进入无限循环？

考虑这个树，其中有3个顶点，考虑以下边缘

A-B-C以A为根，向下。假设我们正在使用DFS算法

A将生成一个新状态B，B将生成两个状态A&C，因为树没有“如果探索了一个节点，则标记该节点已访问”，因此可能DFS算法会再次探索A，从而生成一个新状态B，因此我们陷入了无限循环。

但是你是否注意到了什么，我们正在处理无向边，即A-B和B-A之间存在连接。当然这不是一个循环，因为循环意味着顶点必须>= 3并且所有顶点都不同，除了第一个和最后一个节点。

例如A->B->A->B->A不是一个循环，因为它违反了循环属性>= 3。但确实A->B->C->A是一个循环>= 3个不同的节点已检查，第一个和最后一个节点已检查。

再次考虑树边缘，A->B->C->B->A，当然这不是一个循环，因为有两个B，这意味着不是所有节点都不同。

最后，您可以实现树搜索算法，以防止两次探索相同的节点。但是这会产生后果。

- Mohamed Horani

---

这个答案令人困惑，因为它似乎混淆了问题是树还是图以及搜索算法本身在搜索过程中使用树还是图的情况。 - mlibby

Answer 5

简单来说，树不包含循环，而图可以。因此，在搜索时，我们应该避免在图中出现循环，以便不会陷入无限循环。

另一个方面是，树通常具有某种拓扑排序或类似二叉搜索树的属性，这使得与图相比搜索更快、更容易。

- Madhi

Answer 6

我将补充@ziggystar的回答（其他答案涉及数据结构中树和图的区别，这不是问题所涉及的，问题是关于树和图算法遍历你的图的比较）。

这种有点混乱的术语来自Russell和Norvig的《人工智能：一种现代方法》：

- 树搜索算法 - 是用于解决搜索问题的任何特定算法。 - 图搜索算法 - 是一种增强了一组已探索状态的树搜索算法。

这两个算法都表示为树！之所以称Graph-Search算法为Graph-Search算法，是因为它可以直接表示在我们的搜索问题的图上（再次作为树）。

看一下罗马尼亚的地图。这是我们的搜索问题的图形。

现在，我们可以应用许多算法来找到从Arad到Bucharest的路径（广度优先搜索、深度优先搜索、贪婪搜索 - 我们心中想要的任何东西）。然而，所有这些算法都可以分为树搜索算法和图搜索算法。

- 树搜索算法将我们的Arad-to-Bucharest问题的解表示为一个树。请注意重复的“Arad”节点。 - 图搜索算法也将我们的Arad-to-Bucharest问题的解表示为一棵树，但我们从树中删除了重复的“Arad”节点。 - 然而，由于这种消除重复状态的方式，我们有了一种更好的方法来表示它 - 直接在罗马尼亚地图上（即我们搜索问题的图形上）！因此是“Graph-Search算法”中的“Graph”。

以下是伪代码。请注意，Tree-Search算法和Graph-Search算法之间唯一的区别是探索状态集合的添加。

- Evgenia Karunus

Answer 7

你可以查看第13页幻灯片获取伪代码。

- avimimoun