2

我试图以与此处解释的相同方式实现 Karger 的最小切割算法，但我不喜欢这样一个事实，即在 while 循环的每一步，我们都可以选择一个边缘，它的两个端点已经在一个超级节点中。更具体地说，这部分

// If two corners belong to same subset, 
// then no point considering this edge 
       if (subset1 == subset2) 
         continue;

是否有避免此问题的快速解决方案？

4

1 回答 1

2

备份并思考为什么这里有一个 union-find 结构以及为什么值得对 continue 语句进行改进可能会有所帮助。

从概念上讲，每次执行的收缩都会以下列方式改变图表：

  1. 签约的节点将替换为单个节点。
  2. 入射到任一节点的边被新联合节点的边替换。
  3. 在两个较早的节点之间运行的边被删除。

那么，问题是如何实际对图表执行此操作。您找到的代码懒惰地执行此操作。收缩完成后，它实际上并没有改变图形。相反，它使用 union-find 结构来显示哪些节点现在彼此等价。当它对随机边进行采样时，它必须检查该边是否是在步骤 (3) 中将被删除的边之一。如果是这样，它会跳过它并继续前进。这具有早期收缩非常快的效果（当收缩的边缘很少时，选择两个边缘作为收缩节点的一部分的可能性非常低），但是后期收缩可能会慢很多（一旦边缘开始收缩，很多的边缘可能已被删除）。

这是一个简单的修改，您可以使用它来加快这一步。每当您选择要收缩的边并发现其端点已经连接时，丢弃该边，并将其从边列表中删除，这样它就不会再次被选中。您可以通过将该边交换到边列表的末尾，然后删除列表的最后一个元素来做到这一点。这样做的效果是，每条处理过的边都不会再被看到，因此在算法的所有迭代中，每条边最多只能处理一次。这给出了一个随机收缩阶段的运行时间为 O(m + nα(n))，其中 m 是边数，n 是节点数。α(n) 的因子来自联合查找结构的使用。

如果您真的想删除该 continue 语句的所有相似之处，另一种方法是直接模拟收缩。每次收缩后，遍历所有 m 条边，并通过查看是否需要保持不变、指向新的收缩节点或完全移除来调整每条边。对于整体最小切割计算的净成本为 O(mn)，每次收缩将花费时间 O(m)。

除此之外，还有一些方法可以加快速度。Karger 的原始论文建议生成边缘的随机排列，并巧妙地使用 BFS 或 DFS 在该数组上使用二进制搜索来找到在时间 O(m) 中产生的切割，这比 O(m + nα( n)) 大图的方法。基本思想如下：

  1. 探测边缘列表的中间元素。
  2. 在仅使用这些边形成的图上运行 BFS，并查看是否恰好有两个连通分量。
  3. 如果是这样，太好了！这两个CC是你想要的。
  4. 如果只有一个 CC，则丢弃边数组的后半部分，然后重试。
  5. 如果存在多个 CC，则将每个 CC 收缩为单个节点，并更新一个全局表，指示每个节点属于哪个 CC。然后丢弃数组的前半部分并重试。

每个 BFS 的成本是 O(m)，其中 m 是图中的边数，这给出了递归 T(m) = T(m/2) + O(m)，因为在每个阶段我们是扔掉一半的边缘。这解决了 O(m) 的总时间，但正如你所看到的，这是一种更复杂的方法来编码这个算法！

总结一下：

  1. 通过对提供的代码进行非常小的修改，您可以保留 continue 语句，但仍然可以非常快速地实现随机收缩算法。

  2. 为了在不牺牲算法运行时间的情况下消除这种继续，您需要做一些大手术并改变一些方法，只比保持继续快一点点渐近。

希望这可以帮助！

于 2020-05-31T21:58:37.697 回答