问题标签 [union-find]

我必须使用联合查找算法来解决旅行商问题。除了我刚刚发现的一个问题外，我几乎完成了它。当它处理每条边时，它会检查一个循环，这是对整个父数组的事情完成的。问题是，当它到达我需要添加的最后一条边才能完成问题时，由于技术上是一个循环，它不会添加边，因此无法完成路径。我如何区分无用的循环和表明我们已经完成的循环？

这是我到目前为止得到的代码

这是它按顺序经过的边缘

Warren 的抽象机器中的练习 2.2 ：教程重构

要求对术语 f(X, g(X, a)) 和 f(b, Y) 进行表示，然后对这些术语的地址进行统一（分别表示为 a1 和 a2）。

我已经为这些术语构建了堆表示，它们如下：

现在我被要求跟踪统一（a1，a2），但是按照第 20 页的算法，我得到：

我的错误在哪里？

所以这就是我想要做的：我有一个包含几个等价关系的列表：

我想合并共享一个元素的集合。这是一个示例实现：

它打印

这是正确的，但当等价关系太大时，速度太慢了。我查看了关于联合查找算法的描述：http ://en.wikipedia.org/wiki/Disjoint-set_data_structure 但我仍然在编写 Python 实现时遇到问题。

请给出一个简单的方法来分析联合查找算法的时间复杂度。在这两种情况下 1. 标准方法 2. 加权联合启发式方法

我知道在标准版本中，它的时间复杂度是：O(n^2) ，如果是加权联合启发式方法，它是：O(m + n logn)

但我没有得到，它是怎么来的。假设：假设有 n 个元素和链表数据结构，每个节点都指向链表的头部，m=make set 操作。

我有一些比较昂贵的结构。（它们实际上是具有不同分支的树。）为它们计算哈希值也很昂贵。

我想为eq运算符创建一个装饰器，它将缓存一些结果以加快速度。这有点类似于记忆。

特别是，我希望发生这样的事情。假设我们有 3 个对象：A、B 和 C。我们比较 A 和 B。调用eq运算符，返回 True，结果被存储。我们将 B 与 C 进行比较。eq运算符像以前一样被调用。现在我们比较 A 和 C。现在算法应该检测到 A 等于 B 并且 B 等于 C，所以它应该返回 A 等于 C 而不调用昂贵的eq运算符。

我想使用 union-find 算法，但它只允许缓存equalities，不允许缓存不等式。

假设我们有 2 个彼此相等的对象：A 和 B。还假设我们有另一对相等的对象：C 和 D。联合查找算法将正确地将它们分为两类（A，B）和（C , D)。现在假设 A不等于 C。我的算法应该以某种方式缓存它并防止eq运算符进一步在对 (A, C), (B, C), (A, D), (B, D) 上运行，因为我们可以推断出所有这些对都不相等。Union-find 不允许这样做。它只保存了正等式，当我们必须比较许多不相等的对象时会惨遭失败。

我目前的解决方案是这样的：

如果哈希函数很容易计算，这个解决方案就可以了，但事实并非如此。我们将对很可能相等的对象调用 cache.find，因此我们很少需要调用原始的相等运算符。但是，正如我所说，哈希函数在我的树上非常慢（它基本上需要遍历所有树，比较每个节点上的分支以删除重复项），所以我想删除它。我想缓存负面结果。

有谁知道解决这个问题的好方法？我不仅需要缓存正面的比较结果，还需要缓存负面的比较结果。

更新：

我目前对我有用的解决方案如下：

这加快了 eq 和 hash。

我想知道，为什么在联合查找算法中- 你按它们的高度合并两棵树 - 将较小的一棵附加到较高的一棵（在没有路径压缩的更简单的变体中）。

如果您通过元素的数量将它们合并 - 将具有较少元素的树附加到具有更多元素的树上，这会是一种更糟糕的方法吗？

它关于使用不相交集的链表表示的朴素联合查找算法：
Find_Set(x) 操作返回一个指向包含元素 x 的集合的代表的指针。这需要 O(1) 时间，因为包含 x 的节点直接有一个指针指向 x 的代表。但在此之前，首先我们需要在所有不相交的集合中找到包含元素 x 的特定节点。所以这个搜索不是 O(1)。我不明白 Find_set(x) 是 O(1 )（如书中给出的），当我们不知道包含 x 的节点属于哪个不相交集合时。

如果我在最后一步 (7) 中使用了规则，有人可以和我核对一下吗？

更新：

括号内的数字是参与联合的每个集合的元素数（权重（？））。大写字母是集合的名称。

据我了解：我们使用元素的数量作为排名？这越来越令人困惑，每个人都对相同的东西使用不同的术语。

我们有工会：

1. U(1,2,A)
2. U(3,4,B)
3. U(A,B,C)
4. U(5,6,D)
5. U(7,8,E)
6. U(D,C,F)
7. U(E,F,G)

路径压缩涉及将根分配为路径上每个节点的新父节点 - 这可能会降低根的等级，并且可能会降低路径上所有节点的等级。有没有办法解决这个问题？有必要处理这个吗？或者也许可以将等级视为树高度的上限而不是确切的高度？

谢谢！

我在尝试使用路径压缩实现 UnionFind 结构算法时遇到问题（不再使用 stackoverflow（呵呵））查找算法。

我有标准的整数数组，数组可以变得非常大->它可以正常工作，直到 60.000.000 个元素。

我的联合函数如下所示：

我的 isInSameSet 看起来像这样：

我在 Find 中尝试过迭代方式：

和尾递归：

我的代码中有什么遗漏吗？有没有其他方法可以解决此类问题？

@edit：将构造函数添加到代码中：

@edit2（更好的解释和新发现）：对于少于 60.000.000 个元素，问题不再存在于 stackoverflow 中，这足以解决我的问题。

我这样称呼测试联盟：

所以结尾对是这样的：

这只是测试手段的最优化选项的唯一示例:)

然后我检查 0 的代表是否是表中的最后一个元素（100 个元素为 99）并且它有效。

问题是，我的算法只有在初始元素都在它们自己的联合中时才有效（0:0、1:1、2:2、3:3）。如果我已经设置了不同的联合（0:2、1:6、2:1、3:5，...），我的测试算法将停止工作。

我已将其缩小为查找功能中的问题，可能与路径压缩有关