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

Question

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

Answer 1

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

这让问题变得更简单了，因为我们只需要寻找最好的负解，如果我们没有找到任何我们使用 Prims with log(abs())。

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

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

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

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

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