问题标签 [floyd-cycle-finding]

我正在通过弗洛伊德的循环查找算法并且有一个疑问。

我们是否只将快速指针增加 2？

是否有任何其他值应该是最匹配的？

我想将以下 Haskell 代码翻译成 Agda：

这使我们能够有效地将列表分成两部分：

因此，我尝试将此代码转换为 Agda：

唯一的问题是 Agda 抱怨我错过了floyd [] (y :: ys). 但是，这种情况绝不应该出现。我如何向 Agda 证明这种情况永远不会发生？

这是该算法如何工作的可视化示例：

这是另一个例子：

当兔子（ 的第二个参数floyd）到达列表的末尾时，乌龟（ 的第一个参数floyd）到达列表的中间。因此，通过使用两个指针（第二个的移动速度是第一个的两倍），我们可以有效地将一个列表分成两个。

在一次采访中，我被要求检测链表中的循环节点并计算循环中的节点数。由于我不知道 flyod 算法，我试图找出自己的方法。

这个想法是在这种情况下，两个节点的地址将指向同一个节点（循环节点）。

例如。

1-->2-->4-->5-->7-->3-->4

这里 2->next 和 3->next 是一样的，都是 4 的地址。也就是说链表中有一个循环，4 是循环节点。并且从 4 遍历到 4 将给出循环中的节点数。

有没有办法我们可以继续使用这种方法？？？？

我对此有一些问题。首先，我使用 Floyd-warshall 在有向图上显示所有最小周期并且它有效，但后来我尝试将它与无向图一起使用，但它不像我需要的那样工作。

例如，假设我有这个图表：

这应该看起来像这样：

无论如何，由于您可以将无向图表示为有向图（就像我在示例矩阵中所做的那样），Floyd Warshall 应该可以工作，但结果不是我所期望的。使用相同的图形示例，这是具有最小路径成本的矩阵：

最小路径成本：

这是带有路径的矩阵：

因为我只对循环感兴趣，所以我只需要矩阵的对角线。

无论如何，让我们取 0 - > 0：结果是 (0 4 0)，成本是 16

无论如何，因为我正在寻找最小周期，所以我期望类似：

0 -> 0, Path (0 4 2 0) （或 0 2 4 0 因为是无向图，但我只需要其中一个），成本为 30。

这实际上是 floyd-warshall 代码：

我真的不知道我需要改变什么才能得到正确的结果（或者这可能是正确的结果，我认为不是）。

现在我记得阅读堆栈溢出答案时，快跑者和慢跑者总是会在链表循环中发生冲突，并且速度差 2 是任意的。

如果快跑者和慢跑者之间的差异是 2，那么我无法想出一个反例，但是如果跑者之间的差异是 3，那么我似乎无法在下面的示例中让跑者发生碰撞.

假设我们在一个链表循环中有 2 个跑步者，慢的和快的。循环有 8 个节点，第一个节点标记为 0，第二个节点标记为 1，依此类推。慢在索引 0 处，快在 1 处，那么它们永远不会发生碰撞：

这个例子和循环中的跑步者总是会发生碰撞的说法是矛盾的，因为快跑者可以不断跳过慢跑者。

我还没有上过算法课程，所以请尽量简单地解释我做错了什么。

该算法使用快速和慢速指针来检测链表中的循环。我的问题是，如何证明循环中两个指针碰撞的点到循环开始的距离等于链表头部到循环开始的距离？

考虑以下链表：

上面的列表有一个循环如下：

在白板上绘制链表，我尝试手动解决不同的指针步骤，看看指针如何移动 -

(slow_pointer_increment, fast_pointer_increment)

因此，针对不同情况的指针如下：

前两对增量 - (1,2) 和 (2,3) 工作正常，但是当我使用对 (1,3) 时，算法似乎不适用于这对。是否有关于我们需要增加多少步骤才能使该算法成立的规则？

尽管我为较慢和较快的指针搜索了各种增量步骤，但到目前为止，我还没有找到一个相关的答案来说明为什么它不适用于此列表中的增量 (1,3)。

我正在阅读算法书并自己实现书中写的所有方法。我学习了以龟兔算法而闻名的弗洛伊德的寻环算法，这里是实现。请让我知道我是否执行不正确或有任何改进建议。谢谢 ！

此代码用于在单个链接列表中查找循环，我从http://blog.ostermiller.org/find-loop-singly-linked-list了解了它，但无法理解为什么代码已经写成它已经写的方式。

该解决方案由 Stephen Osteriller 设计，并由 Daniel Martin 证明为 O(n)。

最后也提到了这一点：

这个解决方案是 O(n)，因为 sinceScale 随着对 next() 的调用次数线性增长。一旦 sinceScale 大于循环的大小，可能需要再调用一次 next() 来检测循环。

有一种明显的标准方法来查找链表是否具有循环，然后返回循环开始处的节点，这是具有慢/快指针的 floy 算法。
代码和逻辑很清楚，除了 1 件事。
该方法基于这样的假设，即指针将遇到的循环中的节点与从列表头部到循环开始的步数完全相同。那部分是我不明白的。
因此，如果 Slow 和 Fast 都从列表的头部开始，当 Slow 完成 k 步并到达循环的开头时，Fast 将完成 2k 步并且实际上是 k 步进入循环。
如此快的速度领先于慢速 k 步，落后于慢速（在循环的开始处） N - k 其中 N 是循环大小。
由于在每一步中，快接近慢，而快在慢 N - k 节点之后，快将在 N - k 步骤中变慢。
此时，slow 将执行 N - k 步，并将在节点 N - k 中。
Fast 将完成 2(N - k) 步，并将在节点 2N - 2k + k = 2N - k 处（因为 fast 在节点 k 处）。
由于这是一个循环 2N - k = N - k，因此它们在节点 N - k 处相遇。
但是为什么 N - k 节点距离循环开始有 k 步？
我在这里有什么误解？