首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >用联合查找数据结构修正Karger最小割集算法

问用联合查找数据结构修正Karger最小割集算法
EN

Stack Overflow用户
提问于 2020-05-31 12:31:30
回答 1查看 371关注 0票数 2

我试图实现Karger的min算法用同样的方式在这里解释,但我不喜欢这样一个事实,即在we循环的每一步,我们都可以在一个超级节点中选择两个端点。更具体地说,这一部分

代码语言:javascript
复制
// If two corners belong to same subset, 
// then no point considering this edge 
       if (subset1 == subset2) 
         continue; 

有快速解决办法来避免这个问题吗?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-05-31 21:58:37

它可能有助于备份和思考为什么这里有一个联盟-查找结构,为什么它是值得改进的继续声明。

从概念上讲,执行的每个收缩都以下列方式更改了图形:

  1. 将收缩的节点替换为单个节点。
  2. 任何节点的边缘被替换为新的联合节点的边缘。
  3. 前两个节点之间运行的边缘被移除。

那么,问题是如何对图进行实际操作。你找到的代码懒洋洋地这么做。当收缩完成时,它实际上不会改变图形。相反,它使用联合查找结构来显示哪些节点现在是等价的。当它采样一个随机边时,它必须检查该边是否是步骤(3)中被删除的边之一。如果是这样的话,它就跳过它,然后继续前进。这样做的效果是早期收缩非常快(当很少有边缘收缩时,选择作为收缩节点一部分的两条边的可能性非常低),但后来的收缩可能要慢得多(一旦边缘开始收缩,许多边缘可能被删除)。

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

如果您真的想要删除连续语句的所有表象,另一种方法是直接模拟收缩。每次收缩后,遍历所有m个边,并通过查看其是否需要保持不变、指向新的收缩节点或完全删除来调整每个边。这将需要的时间O(m)每收缩的净成本O(mn)的整体最小削减计算。

有一些方法可以让事情变得更快。Karger的原始论文建议生成边的随机排列,并在该数组上使用二进制搜索,巧妙地使用BFS或DFS找到时间O(m)中产生的切线,这比O(m + nα(n))方法对大图的切分略快。其基本思想如下:

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

每个BFS的代价是O(m),其中m是图中的边数,这给出了递归T(m) = T(m/2) + O(m),因为在每一阶段我们都丢弃了一半的边。这解决了O(m)的总时间,虽然你可以看到,这是一个更复杂的方式编码这个算法!

概括地说:

  1. 只需对所提供的代码进行非常小的修改,就可以保留code语句,但仍然可以非常快速地实现随机收缩算法。
  2. 为了在不牺牲算法运行时的情况下消除这种情况,您需要进行一些主要的操作,并更改一些方法,使其比保持连续运行速度稍快一些。

希望这能有所帮助!

票数 3
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/62116263

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档