111

关于人工智能中的 DFS、A* 搜索，图搜索和树搜索版本有什么区别？

4

7 回答 7

197

从现有的答案来看，这个概念似乎有很多混淆。

问题始终是图表

树搜索和图搜索之间的区别并不在于问题图是树还是一般图。总是假设您正在处理一般图表。区别在于用于搜索图的遍历模式，可以是图形或树形。

如果您正在处理树形问​​题，则两种算法变体都会产生相同的结果。因此，您可以选择更简单的树搜索变体。

图和树搜索之间的区别

您的基本图形搜索算法如下所示。具有起始节点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-star 搜索，依此类推。

上述算法实际上称为树搜索。如果在起始状态中有多个指向它的有向路径，它将多次访问底层问题图的状态。如果它位于有向循环上，甚至可以无限次访问一个状态。但是每次访问都对应于我们的搜索算法生成的树中的不同节点。正如稍后解释的那样，有时需要这种明显的低效率。

图表搜索

正如我们所见，树搜索可以多次访问一个状态。因此，它将多次探索在此状态之后找到的“子树”，这可能会很昂贵。图搜索通过跟踪封闭列表中的所有访问状态来解决此问题。如果一个新找到的后继者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

比较

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

最佳解决方案

一些实现方法select可以保证返回最佳解决方案 - 即最短路径或具有最小成本的路径（对于具有附加到边的成本的图）。只要节点按成本增加的顺序扩展，或者成本是非零正常数，这基本上就成立。实现这种选择的常用算法是统一成本搜索，或者如果步骤成本相同，则为BFS或IDDFS。IDDFS 避免了 BFS 的大量内存消耗，并且通常建议在步长不变时用于不知情的搜索（又名蛮力）。

一个*

此外，（非常流行的）A*树搜索算法在与可接受的启发式算法一起使用时提供了最佳解决方案。然而， A*图搜索算法仅在与一致（或“单调”）启发式（比可接受性更强的条件）一起使用时才做出这种保证。

(2) 伪代码的缺陷

为简单起见，呈现的代码不会：

  • 处理失败的搜索，即只有在找到解决方案时才有效
于 2013-03-07T20:50:11.227 回答
8

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

但是，如果您知道您的图有一些限制，例如它是树或 DAG，您通常可以找到比无限制图更有效的搜索算法。例如，在树上使用 A* 或其非启发式对应物“Dijkstra 算法”可能没有多大意义（无论如何只有一个路径可供选择，您可以通过 DFS 或 BFS 找到）或在有向无环图中（可以通过按照拓扑排序获得的顺序考虑顶点来找到最佳路径）。

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

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

于 2012-05-21T12:59:15.217 回答
3

图和树之间的唯一区别是循环。图可能包含循环，树不能。因此，当您要在树上实现搜索算法时，您不需要考虑循环的存在，但在处理任意图时，您需要考虑它们。如果不处理循环，算法最终可能会陷入无限循环或无限递归。

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

于 2012-05-21T06:20:37.043 回答
2

图与树

  • 图有循环
  • 树没有循环“例如，想象你头脑中的任何一棵树，分支与根没有直接连接，但分支与其他分支有连接，向上”

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

图搜索有一个很好的特性，即每当算法探索一个新节点并将其标记为已访问时，“无论使用何种算法”，该算法通常都会探索从当前节点可到达的所有其他节点。

例如，考虑以下具有 3 个顶点 AB 和 C 的图，并考虑以下边

AB、BC、CA，从C到A有一个循环，

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

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

考虑这棵具有 3 个顶点的树并考虑以下边

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

A 将生成一个新状态 B，B 将生成两个状态 A 和 C，因为 Trees 没有“标记已访问的节点是否已被探索”，因此 DFS 算法可能会再次探索 A，从而生成新状态 B，因此我们进入了一个无限循环。

但是您注意到了吗，我们正在研究无向边，即 AB 和 BA 之间存在连接。当然这不是一个循环，因为循环意味着顶点必须 >= 3 并且所有顶点都是不同的，除了第一个和最后一个节点。

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

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

最后，您可以实现树搜索算法，以防止两次探索同一节点。但这有后果。

于 2016-03-29T08:35:05.387 回答
1

我将添加到@ziggystar 的答案（其他答案是指作为数据结构的树和图之间的差异，这不是问题所在，问题是指用于遍历图的树 VS 图算法！）。

这个有点令人困惑的术语来自Russell 和 Norvig 的“ Artificial Intelligence A Modern Approach ”：

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

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

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

现在，我们可以应用许多算法来找到从阿拉德到布加勒斯特的路径（广度优先搜索、深度优先搜索、贪婪搜索——任何我们内心想要的）。然而，所有这些算法都可以分为树搜索算法和图搜索算法。

树搜索算法将我们的 Arad-to-Bucharest 问题的解决方案表示为一棵树。注意重复的“Arad”节点。

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

这是给你的一些伪代码。请注意，树搜索算法和图搜索算法之间的唯一区别是添加了探索状态集。

于 2021-12-11T18:38:40.570 回答
1

简而言之，树不包含循环，而图形可以包含在哪里。因此，当我们进行搜索时，我们应该避免在图中出现循环，以免陷入无限循环。

另一方面是树通常具有某种拓扑排序或类似于二叉搜索树的属性，与图相比，它使搜索变得如此快速和容易。

于 2017-05-21T09:15:23.357 回答
0

您可以查看幻灯片 13中的伪代码。

于 2021-05-04T22:11:58.403 回答