深度优先搜索算法中的重复元素

Question

我正在用Java编写一个程序，其中必须实现三种搜索算法，其中之一是深度优先图搜索算法。我的程序遍历由邻接矩阵表示的连通图，并使用前沿和已探索集合来执行每个算法。

前沿存储已扩展父节点的未探索子节点，而已探索集合存储已扩展的节点。已探索集合的目的是避免重复，从而避免无限循环。

我的前沿使用链接阻塞双端队列实现，而我的已探索集合使用链接散列表实现。

然而，在测试该算法实现的初始版本时，我注意到仍然存在少量的重复项，特别是当目标节点不存在时，算法肯定必须访问图中的每个节点。最终我意识到，这是因为当一个节点被扩展时，它的所有子节点都被添加到前沿，但只有其中一个被探索。因为图是连通的，所以其他路径可能存在于节点中，这可能导致在将其添加到已探索集合之前，该节点多次遇到。

这引出了我的问题：我应该解决它吗？

深度优先搜索应该首先探索形成图的树的一侧，然后回溯，这意味着即使它在树的一侧遇到了次优的目标节点，它也应该返回那个节点而不是以前尚未探索的（更优的）节点。

然而，如果我正在实现一个已探索集合以避免重复，则在某些情况下允许出现重复似乎相矛盾。

我认为真正的错误可能在于没有深入理解算法，因此真诚地希望能得到帮助，谢谢您。

- user2012620

---

你能具体说明一下“次优目标节点”是什么意思吗？你有多个可能的目标吗？距离是否重要？如果是，那么深度优先搜索算法不是开始的正确选择。 - us2012

不客气，我的程序不支持多个目标，但是以我下面使用的例子为例。第一个“b”将与起始节点相邻，因此路径长度将为1，但第二个“b”（相同的节点，但沿着更长的路径遇到）将具有路径长度> 1。这就是我所说的“不太优秀”。该程序旨在用于任务，并且我需要实现广度优先，深度优先和迭代加深，因此其适用性并不是实施的因素。然而，这证明是一个障碍，因为我需要在ITDS之前完成此操作。 - user2012620

好的。DFS是我们下面讨论过的，通常用于扩展整个图或搜索单个节点（有时用于检测循环）。但是，如果您想要最短路径等内容，您需要查看其他算法。对于您实现DFS的任务，只需进行讨论的更改（不要重新推送已访问的节点），那么就可以了！ - us2012

@us2012 不要要求别人接受你的答案，这不是评论的目的。 - casperOne

Answer 1

通常称为深度优先搜索算法的算法不需要所谓的“frontier”(边界)，正如你所称呼。然而，在A*图搜索中，这个概念被使用（通常被称为“open set”）。

对于标准的深度优先搜索，你只需要一个节点的堆栈：将初始节点压入堆栈，然后在每一步中弹出一个节点，检查它并将其所有邻居(*)推到堆栈顶部。然后重复此步骤。

(*)请记住将推入堆栈的所有节点标记为已访问（我相信你在问题中称之为“探索集合”），不要推入已经访问过的节点。

通过使用堆栈，可以避免你所描述的问题。

如果你确实想要维护那个frontier/open set, 确保它永远不包含重复项：使用不允许重复项的数据结构(例如set)。

(附注: 如果你的图节点具有自然编号，并且你期望DFS访问大部分节点，你可能也可以使用数组/向量作为你的探索集合/closed set。)

- us2012

---

首先，感谢您的回答。我的程序使用了链接阻塞双端队列提供的推送和弹出方法，因此我有效地将其用作堆栈。在这里，我只是使用frontier/open list这个名称来描述您所描述的内容，但可能我应该举个例子来使问题更清晰：想象一下：1.检查a 2. a不是目标节点，因此扩展'a'（扩展导致b和c） 3. b和c被推入堆栈 4. b恰好是目标节点，但c先被探索 5. 在从c导出的路径的扩展中，再次遇到b - user2012620

@user2012620 可能会再次遇到 b，但是不会将其再次推入堆栈，因为在第一次将其推入堆栈时已将 b 标记为已访问。 - us2012

好的，谢谢你，这真的是我困惑的根源。因为我们实际上没有检查 b，只是在回溯后将其添加到前沿进行检查（因为如果我们知道它是目标，我们就不会继续搜索），所以我不确定算法是否应该返回第二个遇到的 'b' 作为目标，而不是第一个 'b'。请注意，如果它从未允许将第二个 'b' 推入堆栈，则此操作是不可能的。 - user2012620

@user2012620 很高兴能帮到你 - 但我仍然不确定我们是否解决了根本问题。我怀疑你实际上根本不需要DFS，请看一下我在你的问题下面的评论。 - us2012