问题标签 [depth-first-search]

boost 库中实现的深度优先算法只访问每个顶点一次。

是否有任何解决方法可以禁用此选项。我希望只要任何顶点中有分支，就可以访问这些顶点。

任何建议...

编辑：该图是非循环的。

我正在编写一个需要遍历大型对象图的组件，有时深度为 20-30 级。

走图的最高效方式是什么？

A. 将“步骤”排入队列以避免深度递归

或者

B. 一个 DFS（深度优先搜索），它可能会深入许多级别，并且有时会有一个“深”的堆栈跟踪。

我想我要问的问题是：在 .NET 中执行 DFS 是否会导致“深度”堆栈跟踪的性能下降？如果是这样，打击是什么？通过排队在 DFS 中递归处理的步骤，我会更好地使用一些 BFS 吗？

对不起，如果我不清楚。谢谢。

正如标题所暗示的，我正在使用boost::depth_first_search和使用一个访问者（继承自boost::default_dfs_visitor）来实现一些算法。

但是，在算法运行期间，我想在访问者中保存一些信息，以便以后查询。但是，在 DFS 完成后，信息会被删除，所以我假设它使用副本。除了对所有私有变量使用指针之外，有没有办法防止这种情况并让 boost 使用我的副本？

我正在使用BGL来存储我的 DAG。顶点有状态。鉴于其中一个顶点的状态发生变化，我想更新相关顶点。我可以使用 boost::depth_first_search 和自定义访问者来做到这一点。

现在的逻辑是，如果顶点处于特定状态，我不想更新搜索到的顶点及其依赖项。基本上我想控制 dfs 或 bfs 中的顶点排队。在 BGL 中实现这一目标的最佳方法是什么。

谢谢。

我目前正在研究一个使用适应度函数解决 15 个难题的项目。有3种健身功能可以使用，

1. 适应度函数1= 1 - （错位棋子数/棋子总数）；
2. 适应度函数2 = 1-（所有错位瓷砖距离目标位置的距离之和/64）
3. 适应度函数3=（适应度2+适应度1）/2

求解器旨在搜索提高适应度函数 VALUE 的可能移动，直到解决整个拼图板（其中适应度函数 = 1）。我在尝试生成动作时备货，因为求解器会打印不成功的搜索路线以及实际路线，例如 W,S,W,N,S,N,S,N,S,N,S,N,S,N,S ,N,S,N （顺序相反），表示 NWSW。然而，求解器来回搜索多次，并打印出不需要的路线。我想在递归中排除以前访问过的位置，并且只打印有效的移动而不是不成功的移动。代码如下：

我有一个节点列表，其中每个节点都属于一棵或多棵树。（他们不一定有共同的祖先）

我想按照深度优先搜索时找到的相同顺序对节点进行排序。

假设我有一个用于将树根排序在一起的谓词，还有一个用于将共同父级的子级排序在一起的谓词。每个节点都有一个 Parent 访问器和一个 children 枚举器。出于性能原因（如果可能），我想避免使用 Children 枚举。

谓词传递给排序函数的伪代码可能是什么（如果节点 1 小于节点 2，谓词将返回布尔值）。

我试图了解维基百科上的深度有限搜索算法，并且试图弄清楚扩展节点到底意味着什么。我试图寻找答案，但我得到的只是更多的算法，这些算法表明必须扩展节点。

具体来说，stack := expand (node)关于整个功能的说法是什么？

对于我自己的练习，我正在编写一个 XML 解析器。为了填充树，我使用法线std::stack并将当前节点设置为最后一个顶部节点的子节点（应该是深度优先？）。所以我现在对删除节点做同样的事情，我想知道是否有更快的方法。
当前删除代码：

工作得很好，但看起来有点慢。那么有没有更快/更好/更常见的方法来做到这一点？

我正在尝试编写一个算法来确定图形是否连接。我认为我的代码几乎是正确的，尽管我不断收到 StackOverFlowError。我个人认为，因为我正在测试我的算法的图表中有一个循环，所以我的代码不理解它并进入一个循环。但是我正在使用一个数组来查看一个节点是否已经被访问过！所以这不应该发生！无论如何，这是我的代码：

s 是我开始的某个节点，nodes 是节点的 ArrayList，并且与访问的数组具有相同的大小（在本例中为 5）。在开始访问看起来像这样：[假假假假假假]，所以没有节点被访问。listOfChildren() 返回特定节点的子节点（不是所有子节点，只是与节点相邻的子节点）的 ArrayList。我确信 listOfChildren() 有效，因为我测试了 43545454 次。

任何帮助表示赞赏（如果可能的话，对代码进行最少的更改）。谢谢。

更新：

我的图表是有向的..

我定义访问是这样的：

我在构造函数中将其中的所有内容设置为 false 这段代码：

节点是字符串！访问和节点具有相同的长度。这就是为什么我可以将 nodes.indexOf(blabla) 用于访问的数组。

更新2：

这是图表的样子：

我确定问题出在 N3 之后，算法在 N3 之后循环，因为它不知道 N1 已经被访问过。我真的不明白为什么会这样！

更新3

字符串具有不同的名称并且没有重复项.. 例如 indexOf(nodes.get(2)) 给出 2 而不是 0 或其他任何内容..

问题是在访问 N3 之后，算法应该停止并返回 0 或 1，但我不知道该怎么做 :)

根据 AIMA（人工智能：现代方法）中的 Norvig 的说法，深度优先算法并不完整（不会总是产生解决方案），因为在某些情况下，正在下降的子树将是无限的。

另一方面，如果分支因子不是无限的，则说广度优先方法是完整的。但这不是与 DFS 中子树无限的情况相同的“事情”吗？

如果树的深度是有限的，就不能说 DFS 是完整的吗？那么 BFS 是完整的而 DFS 不是完整的，因为 BFS 的完整性依赖于分支因子是有限的！