最近有人问我是否可以找到一种算法来计算给定图的最小成本生成树，其中生成树的总成本由边成本的乘积而不是它们的总和给出。
有几种算法可以计算常规最小生成树，但我不确定如何针对上述情况调整它们。有任何想法吗？
谢谢你。
问问题
3473 次
3 回答
17
由于 log(product of edge costs) = sum (log(edge costs))，只需对边权重进行对数变换，并找到这些权重的最小成本生成树。
于 2010-11-18T19:53:12.877 回答
4
由于对数是单调变换，因此当您取所有权重的对数时以及当您将所有权重保持原样时，最小生成树将完全相同。所以：根据所有权重的总和和所有权重的乘积找到 MST 没有区别。
有关图的最小生成树对 graoh 中权重的单调变换不变这一事实的证明文章，请在 google 中键入 The Saga of Minimum Spanning Tree。第一个链接将是您需要的链接。第 167 页，单调同构。
于 2011-07-14T08:15:45.360 回答
0
我最好的主意 - 通过蛮力找到所有最小的（意味着不必要的边缘）生成树，选择最小的产品。
大多数（或所有）更有效的解决方案不再适用 - 主要是最佳解决方案不再一定包含最佳子问题。（有什么限制？非常重要 - 成本小于 1 的边实际上是负成本，长度为 1 的边是免费的。它们最好都是正的！）
我不确定这个问题是否真的有意义。一方面，您必须要么给出自循环成本（或假设 1），因为我们不能采用零的产品。分割路径的工作方式不同，走同一条路径两次花费 c^2？此外，我觉得这应该是与“成本”不同名称的路径的不同质量
于 2010-11-18T19:55:00.653 回答