Is this minimum spanning tree algorithm correct?最小生成树问题是获取一个已连接的加权图，并找到具有最低总权重的边的子集，同时保持该图的连接状态(因此导致无环图)。 我正在考虑的算法是：
此版本的推动力是一种环境，该环境仅限于"规则满足"而没有任何迭代构造。 它也可能适用于疯狂的并行硬件(即，您期望并行度比循环高几倍的系统)。 编辑： 上面的操作以无状态方式完成(不是在任何循环中最大的边的所有边都被选择/保留/忽略，所有其他边均被删除)。 我不知道它是否有效，但是无论您使用哪种算法都不值得实施。找到所有周期将是致命的巨大瓶颈，它将杀死它。同样，没有迭代就不可能做到这一点。为什么不实施某种标准算法，比如说普里姆的。 为此，您必须详细说明如何查找所有循环，显然没有任何迭代构造，因为这是一项艰巨的任务。我不确定是否有可能。如果您真的想找到一个不使用迭代构造的MST算法，请看一下Prim算法或Kruskal算法，看看是否可以修改这些算法以适合您的需求。 另外，在这种理论架构中是否禁止递归？如果是这样，实际上就不可能在图形上找到MST，因为您根本无法检查图形上的每个顶点/边缘。 @ shrughes.blogspot.com： 我不知道要删除全部，而是要删除全部两个-我一直在草拟算法的各种运行，并假设并行运行可能会多次去除一条边，而我找不到一个没有生成树的情况。我不知道这是否很小。 您的算法定义不明确。如果您有一个完整的图，则算法似乎需要在第一步中除去两个最小元素之外的所有元素。同样，在图形中列出所有循环可能花费指数时间。 详细说明： 在具有n个节点且每对节点之间都有一条边的图形中，如果我的数学正确，则将n！/(2k(nk)！)个循环的大小为k，如果您将循环算作某个子图k个节点和k个边缘，每个节点的阶数为2。 如果两个周期重叠会怎样？哪个最长边最先被去除？是否在两个周期之间共享每个周期的最长边并不重要？ 例如：
有一个-> b-> c->一个循环，还有一个-> b-> d-> a 好的，这是完成正确性证明的尝试。 通过类似于逆向删除算法，我们知道将删除足够的边缘。 剩下的就是要显示不会去除很多边缘。 删除许多边缘可以描述为删除图节点的二进制分区的侧面之间的所有边缘。 但是，只去除了循环中的边缘，因此，对于要去除的分区之间的所有边缘，需要有返回路径来完成该循环。 如果仅考虑分区之间的边缘，则该算法最多只能去除每对边缘中的较大边缘，而这将永远无法去除最小的桥接边缘。 因此，对于任何任意的二进制分区，该算法都无法切断端之间的所有链接。 剩下的就是要表明这扩展到了> 2路分区。 @Tynan可以将系统描述为(某种程度上简化了)描述分类的规则系统。"如果事物在B中，但不在C中，则属于A类"，"连接到Z中的节点的节点也位于Z中"，" M中的每个类别都连接到节点N并具有"子"类别，同样在对于连接到N"的每个节点，M。比这稍微复杂一点。 (我已经表明，通过创建不稳定的规则，您可以对车床进行建模，但这一点也不重要。)它不能显式定义迭代或递归，但可以对带有第二和第三规则的递归数据进行操作。 @Marcin，假设处理器数量不限。毫不费力地表明，该程序可以在O(n ^ 2)中运行，因为n是最长的周期。有了更好的数据结构，可以将其简化为O(n * O(set lookup function)(设置查找函数))，我可以设想可以在恒定时间内评估所有周期的硬件(量子计算机？)。为MST问题提供O(1)解决方案。 反向删除算法似乎提供了部分正确性证明(所提出的算法将不会产生非最小生成树)，这是通过争论mt算法将删除反向删除算法将要消除的每个边缘而得出的。但是我不确定如何证明我的算法不会删除比该算法更多的东西。 嗯... |
