algorithm - 具有负权重的最小产品生成树

Question

log假设如果所有边的权重都为正，则可以通过取每条边的 ，然后应用 Kruskal 或 Prim来获得最小乘积生成树。但是如果某些权重是负数，我们就不能应用这个过程。因为我们需要包含奇数个负边缘，并且这些边缘必须具有最大权重。这种情况下怎么办？

Answer 1

这是一个简单的解决方案。如果至少有一个负边，则找到使 log(abs(edge)) 和最大化的最优生成树。然后，检查实际产品（没有 abs）是否为负数。如果负输出当前生成树，否则用负边缘替换正边缘之一或用正边缘替换负边缘以获得解决方案。

如果所有边都不是负数，则应该对 log(edge) sum 进行最小化。

复杂性：O(n^2) 与一个简单的解决方案。

关于朴素算法的更多解释：选择具有最低绝对值的边缘进行移除。移除这条边会将树分成两部分。我们可以遍历边缘值最大的那些集合之间的每一对（根据情况应该是正的或负的）。这部分的复杂度是O(n^2)。

我们可能不得不尝试移除多个边以达到最佳解决方案。假设我们遍历每条边，复杂度为 O(n^3)。

我非常有信心这可以改进。

Answer 2

我非常怀疑你可以修改 Prims 算法来解决这个问题，因为负数完全改变了它。如果您设法获得否定结果，则必须最大化绝对值，这意味着必须使用具有最高绝对值的边缘，因此尝试优化 Prims 算法找到的结果并获取 log(abs()) 将行不通，除非不可能得到否定的结果，否则这实际上会返回最佳解决方案。

这使问题变得简单一些，因为我们只需要寻找最佳的否定解决方案，如果我们没有找到任何我们使用带 log(abs()) 的 Prims。

如果我们为每个顶点分配一个值 1，则可以通过创建一个新顶点来合并两个顶点，其中两个顶点的所有边除外，连接它们的边除外，并且该值是删除的顶点和边的值的乘积。

基于此，我们可以通过合并只有一条边的所有节点来开始简化。与每个合并步骤平行，必须将移除的边标记为原始图中使用的边，以便最终可以从标记的边重建树。

此外，我们可以合并所有只有正边或只有负边的节点，删除绝对值最高的边。合并新节点后，可以有多个连接到同一个节点，您可以丢弃除绝对值最高的负边和正边之外的所有边（因此最多有 2 条边到同一个节点）。顺便提一句。一旦我们有 2 条边到同一个节点（遵循上面的删除条件），我们就知道必须存在一个 <= 0 的解决方案。

如果你最终得到一个节点并且它是否定的，那么问题就成功解决了，如果它是肯定的，那么就没有否定的解决方案。如果我们有一个 0 顶点，我们可以以任何顺序合并其余节点。我们更有可能最终得到一个高度连通的图，其中每个节点至少有一个负边和一个正边。如果我们有奇数个负顶点，那么我们希望将节点与偶数个负边合并，反之亦然。

始终按绝对值最高的边合并。如果结果顶点 <= 0，那么您找到了最佳解决方案。否则会变得复杂。您可以查看所有未使用的边，尝试添加它，查看可以删除哪些边以使其再次成为树，只查看具有不同符号的边并建立比率 abs(add_edge/removed_edge)。然后最后以最佳比例进行更改（如果您发现任何具有相反符号的组合，否则没有否定解决方案）。但我不是 100% 确定这是否总是会产生最好的结果。