问题标签 [breadth-first-search]

我了解 DFS 和 BFS 之间的区别，但我很想知道何时使用其中一种更实用？

谁能举例说明 DFS 如何胜过 BFS，反之亦然？

首先，这是吃豆人的人工智能，而不是幽灵。

我正在编写一个围绕你的图标播放 PacMan 的 Android 动态壁纸。虽然它通过屏幕触摸支持用户建议，但大部分游戏将由 AI 玩。我已经完成了 99% 的游戏编程，但 PacMan 本人的 AI 仍然非常薄弱。我正在寻求帮助来开发一个好的人工智能来确定 PacMan 的下一个旅行方向。

我最初的计划是这样的：

1. 用零值初始化每个方向的分数计数器。
2. 从当前位置开始，使用 BFS 通过将四个可能的初始方向添加到队列中向外遍历。

3. 从队列中弹出一个元素，确保它还没有被“看到”，确保它是一个有效的棋盘位置，并在相应的初始方向上添加一个基于当前单元格的值：

   1. 有一个点：加10
   2. 拥有力量：加50
   3. 有果实：加果实值（因等级而异）
   4. 有一个幽灵向吃豆人移动：减去 200
   5. 有鬼离开吃豆人：什么都不做
   6. 有鬼垂直行进：减去 50
   7. 将单元格的值乘以基于到单元格的步数的百分比，从初始方向开始的步数越多，单元格的值越接近零。

   并将当前单元格中的三个可能方向排入队列。

4. 一旦队列为空，为四个可能的初始方向中的每一个找到最高分数并选择它。

这在纸上听起来不错，但 PacMan 周围的幽灵非常迅速，他在相同的两三个牢房中来回抽搐，直到一个到达他身边。调整幽灵存在的值也无济于事。我最近的点BFS至少可以在游戏结束前达到2级或3级。

我正在寻找用于开发适当 AI 的代码、想法和/或资源链接——最好是前两者。我想在这个周末的某个时候在市场上发布这个，所以我有点着急。任何帮助是极大的赞赏。

仅供参考，这是在GameDev.StackExchange上手动交叉发布的

我想生成一个 DAG（有向无环图）的 BFS 森林。这意味着我的 Tree 类需要是通用树而不是二叉树（换句话说，当我生成森林时，我无法提前知道节点将拥有的子节点数量）。大部分代码都编写并显示在下面，但是我缺少一行代码，这对我来说是一辈子的事！

我的 Tree 类存储一个值参数、一个父引用和一个子列表。我的问题是引用下一个树节点。将所有未访问的邻居添加为当前节点的子节点后，如何到达下一个节点？

编辑：

所以它看起来像这样？

递归调用在哪里？

上面贴出的代码是我的关卡顺序遍历代码。这段代码对我来说很好，但我不喜欢的一件事是我正在显式初始化temp_node = NULL或者我使用 break。但这对我来说似乎不是一个好的代码。

有没有比这更简洁的实现，或者我怎样才能让这段代码更好？

我正在考虑在方案中实现 bfs 以解决 8 难题问题，这是我到目前为止的代码（给出一些我无法调试的错误）::

两者都可用于从单一来源中找到最短路径。BFS 运行于O(E+V)，而 Dijkstra 运行于O((V+E)*log(V)).

此外，我还看到 Dijkstra 在路由协议中的使用非常相似。

因此，如果 BFS 可以更快地做同样的事情，为什么还要使用 Dijkstra 算法呢？

我想存储数百万个节点的图，其中每个节点以无向方式链接到另一个节点（点 A 到 B，自动 B 指向 A）。我已经将 Neo4j、OrientDB 作为可能的解决方案进行了研究，但它们似乎面向有向图，并且 Neo4j 对超过 100 万个节点不是免费的，这对我来说不是一个解决方案。

你能帮我看看其他 NoSQL 数据库（Redis、CouchDB、MongoDB 等）中的哪一个最适合这样的事情吗？如何实现？我想做一个无属性（只给我链接的元素）具有 2 个深度级别的广度优先查询（具有 A<->B、B<->C、C<->D，查询 A 应该给我 B和 C，但不是 D)。

这不是家庭作业。我在考虑树遍历中的一些新问题，这似乎很明显，所以想解决它。

问题与 BFS 之类的级别顺序遍历非常相似。在 BFS 中，我们通常在树的每一层中从左到右行进，但在这里如果我们在第 i 层从左到右行进，则 (i-1) 和 (i+1) 层需要从右到左行进。

例如：

在正常的 BFS 中，我们输出：2、7、5、2、6、9、5、11、4

但我正在寻找我们输出的解决方案：2、5、7、2、6、9、4、11、5

我能够想出一个解决方案。但是，我想看看是否有人提出了比我更好的解决方案。我也特别关注空间复杂度（堆栈大小）的优化。

请按照 C++ 语言给出你的逻辑。如果您在解决方案中不使用任何容器或 STL，我将不胜感激。

根据此处的评论，我提出了一个使用两个堆栈的解决方案。我的解决方案如下。

• 创建堆栈 S1 和 S2 以及队列 Q。队列 Q 将保存最终的 ans。
• 请注意，在压入任何堆栈（S1 或 S2）之前，我们将首先将其排入队列 Q。
• 无论我们从堆栈 s1 中弹出什么，我们都会将其（第一个）右孩子和（然后）左孩子（按此顺序）推入堆栈 s2。（记住第2点）
• 无论我们从堆栈 s2 中弹出什么，我们都会将其（第一个）左孩子和（然后）右孩子（按此顺序）推入堆栈 s1。（记住第2点）
• 从一个堆栈弹出并将其推送到另一个堆栈，直到两个堆栈都为空。Queue 中的最终条目将是 ans。

对我来说似乎没问题（如果不是，请告诉我）。但仍然想知道是否还有其他可能的解决方案（比这更好）。

我正在尝试使用 Boost Graph Library 中包含的广度优先搜索算法编写我自己的连接组件发现版本，并且我需要从 withing 访问祖先（导致发现当前顶点的顶点）顶点访问者的 discover_vertex 回调来设置当前顶点的组件号。有什么方法可以轻松完成吗？

考虑下图：

我试图找到一种方法来枚举从源节点到目标节点的所有可能路径。例如，从 A 到 E，我们有以下可能的路径：

请注意，对于 ACDE，实际上有 2 条路径，因为其中一条使用边 F3，另一条使用边 F5。此外，由于 A 和 C 之间存在循环，因此您最终可能会得到无限数量的路径，但出于此目的，我只对在从源到目标的路径上没有重复节点的路径感兴趣。

我写了一个深度优先搜索（DFS）算法，但问题是当你在 2 个节点之间有多个边时（比如上面的边 F3 和 F5）我不知道如何处理它。我的算法只带回路径A C D E和A C E，而不带回其他路径。在 的情况下A B C E，我理解原因，因为它从 A 开始，然后到 C 并构建这些路径，但是当 DFS 回到节点 B 时，它然后尝试去 C，但是 C 已经被访问过所以它停止了。

无论如何，我只是想知道是否有办法做到这一点，或者这可能是 NP 完全的。

如果您想查看我的 DFS，代码如下（抱歉滥用宏，我在竞赛编程中使用这些，所以有点习惯）。

输出：