当使用边权重相乘来表示成本时，如何寻找最小生成树的算法

Question

最近有人向我询问是否能找到一种算法来计算给定图的最小成本生成树，其中生成树的总成本是由边缘成本的乘积而不是它们的总和给出的。

有几种算法可以计算常规最小生成树，但我不确定如何为上述情况进行调整。您有什么想法吗？

谢谢。

- AlexTex

Answer 1

由于 log(边权值的乘积) = 边权值的对数之和，因此可将边权值进行对数转换，然后找到这些权值的最小生成树。

- Aniko

---

哦，好的回答！如果不明显，我只想提一下限制条件——所有成本必须为正数，并且应该都大于1。 - jon_darkstar

@Aniko：非常有趣的方法。 - AlexTex

我认为你甚至不需要进行对数转换。标准的最小生成树算法只使用边权重之间的比较，而对数是单调函数，因此不会改变排序顺序。 - jonderry

@Aniko，（0-1]是日志的可接受范围，但AlexTex必须注意零加权边缘，因为log（0）未定义。 - Dijkstra

@Dijkstra 好观点。当然，如果存在0权重边，则问题是微不足道的，因为包含它的任何生成树都将是乘积为0的产品最小值。 - Aniko

Answer 2

由于对数是单调变换，当你对所有权重取对数或保留所有权重时，最小生成树将完全相同。 因此：按所有权重的总和或所有权重的乘积找到MST没有区别。

要查看证明最小生成树不受图中权重单调变换影响的文章，请在谷歌上搜索“The Saga of Minimum Spanning Tree”，第一个链接即为所需页面。第167页，单调同构。

- Yulia

Answer 3

我最好的想法 - 通过暴力找到所有最小生成树（即无用边），挑选乘积最小的那个。

大多数（或全部）更有效的解决方案都不再适用 - 主要是因为最优解不再必然包含最优子问题。 （有哪些限制？非常重要 - 成本小于1的边实际上是负成本，长度为1的边是免费的。它们最好都是正的！）

我不确定这个问题是否真正有意义。首先，您必须给出自环成本（或假定为1），因为我们不能用零来相乘。分割路径的工作方式不同，两次经过同一路径的旅行成本为c ^ 2？此外，我认为这应该是一条具有不同名称的路径的不同质量。

- jon_darkstar

---

为了讨论方便，我们可以假设所有成本都是大于等于1的正数。谢谢您的想法。 - AlexTex