1

最小生成树问题是采用连通加权图并找到其总权重最低的边的子集，同时保持图连接（并因此产生无环图）。

我正在考虑的算法是：

  • 查找所有循环。
  • 从每个循环中删除最大的边缘。

这个版本的推动力是一个仅限于“规则满足”的环境，没有任何迭代构造。它也可能适用于疯狂并行的硬件（即，您希望并行度比周期多几倍的系统）。

编辑：

以上以无状态方式完成（在任何循环中不是最大边的所有边都被选中/保留/忽略，所有其他边都被删除）。

4

7 回答 7

1

如果两个周期重叠会发生什么？哪一个的最长边最先被移除？每个周期的最长边是否在两个周期之间共享是否重要？

例如：

V = { a, b, c, d }
E = { (a,b,1), (b,c,2), (c,a,4), (b,d,9), (d,a,3) }

有一个 a -> b -> c -> a 循环，还有一个 a -> b -> d -> a

于 2008-09-01T05:16:46.487 回答
1

您的算法定义不十分明确。如果您有一个完整的图表，您的算法似乎需要在第一步中删除除两个最小元素之外的所有元素。此外，在图中列出所有循环可能需要指数级时间。

阐述：

在具有 n 个节点且每对节点之间有一条边的图中，如果我的数学正确，则有 n!/(2k(nk)!) 个大小为 k 的循环，如果您将循环计为某个子图k 个节点和 k 个边，每个节点的度数为 2。

于 2008-09-01T05:21:53.293 回答
1

@shrughes.blogspot.com：

我不知道要删除除两个之外的所有内容-我一直在草拟算法的各种运行，并假设并行运行可能不止一次删除一条边我找不到没有生成树的情况. 是不是最小我不知道。

于 2008-09-01T05:29:56.987 回答
1

为此，您必须详细说明您希望如何找到所有循环，显然没有任何迭代构造，因为这是一项不平凡的任务。我不确定这是否可能。如果您真的想找到不使用迭代构造的 MST 算法，请查看Prim或Kruskal 的算法，看看您是否可以修改它们以满足您的需要。

此外，这种理论架构是否禁止递归？如果是这样，实际上可能无法在图上找到 MST，因为您无法检查图上的每个顶点/边。

于 2008-09-01T06:46:27.300 回答
1

我不知道它是否有效，但无论你的算法是什么都不值得实施。找到所有周期将是一个巨大的瓶颈，会扼杀它。在没有迭代的情况下这样做也是不可能的。你为什么不实现一些标准算法，比如说Prim 的.

于 2008-09-01T07:17:30.567 回答
0

@Tynan 该系统可以被描述为（有些过于简化）描述分类的规则系统。“如果事物在 B 中但不在 C 中，则它们属于 A 类”，“连接到 Z 中的节点的节点也在 Z 中”，“M 中的每个类别都连接到节点 N 并且具有“子”类别，也在M 表示连接到 N 的每个节点”。它比这稍微复杂一些。（我已经证明，通过创建不稳定的规则，您可以为车床建模，但这不是重点。）它不能明确定义迭代或递归，但可以使用第二和第三规则等规则对递归数据进行操作。

@Marcin，假设有无限数量的处理器。证明程序可以在 O(n^2) 中运行是微不足道的，因为 n 是最长的周期。有了更好的数据结构，这可以减少到 O(n*O(set lookup function))，我可以设想可以在恒定时间内评估所有周期的硬件（量子计算机？）。给出 MST 问题的 O(1) 解。

反向删除算法似乎提供了正确性的部分证明（所提出的算法不会产生非最小生成树），这是通过争论 mt 算法将删除反向删除算法将删除的每条边而得出的。但是我不确定如何证明我的算法不会删除比该算法更多的内容。

嗯……

于 2008-09-01T19:47:27.847 回答
0

好的，这是完成正确性证明的尝试。通过类比反向删除算法，我们知道将删除足够多的边缘。剩下的就是表明不会有太多的边缘被移除。

去除多条边可以描述为去除图节点的二元分区边之间的所有边。然而，只有一个循环中的边被删除，因此，对于要删除的分区之间的所有边，需要有一条返回路径来完成循环。如果我们只考虑分区之间的边，那么算法最多可以删除每对边中较大的边，这永远不会删除最小的桥接边。因此对于任意的二元划分，算法不能切断边之间的所有链接。

剩下的就是表明这扩展到> 2路分区。

于 2008-09-01T21:33:42.067 回答