问题标签 [depth-first-search]

我整个星期都在尝试这个，但为了我的一生，我无法弄清楚。

我知道我需要一个辅助函数来递归并返回 pathSoFar。我似乎无法理解递归。

我很困惑，以至于除了递归之外，我什至无法准确地制定出问题所在。

谢谢你的帮助。

编辑：好的，我会澄清一点。让我感到困惑的一件事是当节点没有邻居时返回什么路径。目标路径可能会先返回，但随后，由于助手仍在递归，它可以返回死路。我想我对回溯感到困惑。

我一直在阅读有关迭代深化的内容，但我不明白它与深度优先搜索有何不同。

我明白深度优先搜索会越来越深入。

在迭代深化中，您建立一个级别的值，如果在该级别没有解决方案，则增加该值，然后从头开始（根）。

这和深度优先搜索不一样吗？

我的意思是你会不断增加和增加，更深入，直到找到解决方案。我认为这是同一件事！我会沿着同一个分支走，因为如果我从头开始，我会像以前一样沿着同一个分支走。

我想使用堆栈并返回路径，但我认为这是不可能的。

一个节点必须由它的父节点直接调用，这样它才能接收到它后面的路径，而当这个节点被压入堆栈时，它会丢失到目前为止的路径。使用堆栈会导致一个节点被孤立地评估，并且我无法将节点的父节点的路径传递给节点。

我不能让节点拥有它们后面的路径属性，因为这是一项家庭作业。

我已经被这个难住了一个多星期！

我正在完成一项在伯克利网站的 AI 课程页面上找到的作业，以获取乐趣。我需要为 pacman 游戏编写深度优先搜索，以便它可以找到它的路径。问题是 pacman 卡住了。我将首先粘贴代码以使我所说的更清楚：

现在，如果您在 dfs 下阅读我的代码，您将看到打开列表包含我访问和扩展的所有点。

Path 文件包含为 pacman 设置的方向。当我面临我得到的两个继任者都未被访问的情况时，问题就出现了，我的 pacman 选择了一条通往死胡同的路径，因此它需要回溯。我的 Open 做到了并找到了解决方案，但我无法找到如何在我的路径列表中提供回溯方向的方法。如果您将访问http://inst.eecs.berkeley.edu/~cs188/sp09/projects/search/search.html并下载 zip 并将我的代码粘贴到search.pydfs 搜索下，您将理解我的问题。

So currently i have a DFS with the following pseudocode

How do I alter this function to accept a third argument that limits the depth of the search?

我正在解决这个dfs/bfs问题。

我编写了 DFS 的迭代版本和递归版本。

节点访问的顺序不同，我不明白为什么。

迭代 DFS：

递归 DFS：

在教程问题上，我在迭代 DFS 版本上的输出是

1 4 3 2 6

虽然应该是（根据问题示例输出和递归版本）：

1 3 2 6 4

这里发生了什么事？为什么消除递归会改变访问节点的顺序？

-> Netbeans 项目的完整代码。

我读过很多次关于DFS和BFS的文章，但我一直有这个疑问在我脑海中挥之不去。在很多文章中都提到 DFS 可能会陷入无限循环。

据我所知，通过跟踪访问的节点可以轻松消除此限制。事实上，在我读过的所有书籍中，这个小检查都是 DFS 的一部分。

那么为什么提到“无限循环”是 DFS 的一个缺点呢？是不是因为原来的 DFS 算法没有对访问节点进行这个检查？请解释。

我正在为（链表）图实现 DFS。

我的图形结构示例：http: //i.imgur.com/Pm9jC.png

如您所见，有许多名为“a”的节点。它们在顶点方面是相同的，但在节点方面它们实际上是不同的。实施 DFS 涉及在某个时间点将“a”标记为已访问。这看起来很容易，但我希望你能在这里看到我的问题。有许多“a”标记为已访问。我希望我在这里做错了什么。

问题： - 首先将“a”标记为已访问并将其推送到堆栈 s。这有效地将第一个邻接链表中的节点“a”标记为已访问，但其他邻接链表中的所有其他节点“a”仍标记为“未访问”。- 然后考虑“b”，因为它是“a”的第一个未访问的相邻顶点。将其标记为已访问并将其压入堆栈 s。- 现在我们正在探索“b”。从第二个邻接链表中，“b”的相邻顶点是“a”，这个是未访问的，所以我们再次将它压入堆栈。错误的！

当然，我可以编写一个 markVisit($vertex) 方法，将所有出现的“a”标记为一次已访问，但我认为我在上面的实现中没有正确的方法。谢谢你的帮助。

我想实现一个函数，它从有向循环图 G 中的源顶点 V 找到所有可能顶点的所有可能路径。

现在性能无所谓，我只是想了解一下算法。我已经阅读了深度优先搜索算法的定义，但我没有完全理解要做什么。

我没有任何完整的代码可以在这里提供，因为我不知道如何：

• 存储结果（连同 A->B->C-> 我们还应该存储 A->B 和 A->B->C）；
• 表示图（有向图？元组列表？）；
• 使用多少递归（使用每个相邻的顶点？）。

如何在 Erlang 的有向循环图中从一个给定的源顶点找到所有可能的路径？

UPD：根据到目前为止的答案，我必须重新定义图定义：它是一个非循环图。我知道如果我的递归函数遇到一个循环，它就是一个无限循环。为了避免这种情况，我可以检查当前顶点是否在结果路径的列表中 - 如果是，我停止遍历并返回路径。

UPD2：感谢发人深省的评论！是的，我需要找到从一个源顶点到所有其他顶点没有循环的所有简单路径。

在这样的图表中：

对于源顶点 A，算法应该找到以下路径：

• 甲，乙
• A,B,C
• A B C D
• 广告
• 甲、丁、丙
• A,D,C,B

下面的代码完成了这项工作，但它不能用于具有超过 20 个顶点的图（我猜这是递归的问题 - 占用太多内存，永远不会结束）：

UPD3：

问题是常规的深度优先搜索算法将首先进入路径之一：（A，B，C，D）或（A，D，C，B）并且永远不会进入第二条路径。

无论哪种情况，它都是唯一的路径——例如，当常规 DFS 从 (A,B,C,D) 回溯时，它会返回到 A 并检查是否访问了 D（A 的第二个邻居）。并且由于常规 DFS 为每个顶点维护一个全局状态，因此 D 将具有“已访问”状态。

所以，我们必须引入一个依赖于递归的状态——如果我们从 (A,B,C,D) 回溯到 A，我们应该在结果列表中有 (A,B,C,D) 并且我们应该在算法开始时将 D 标记为未访问。

我试图优化尾递归的解决方案，但该算法的运行时间仍然不可行 - 遍历一个由 16 个顶点组成的小图大约需要 4 秒，每个顶点有 3 条边：

有什么想法可以在可接受的时间内运行吗？

我有一个 dfs 方法将返回向量列表，如何根据向量的长度对元素进行排序。