当成本通过乘以边权重给出时找到最小生成树的算法
最近有人问我是否可以找到一种算法来计算给定图的最小成本生成树，其中生成树的总成本由边成本的乘积而不是它们的总和给出。
有几种算法可以计算常规最小生成树，但我不确定如何针对上述情况调整它们。有什么想法吗？
谢谢。
I was recently asked if I could find an algorithm to compute the minimum cost spanning tree of a given graph, where the total cost of the spanning tree is given by the product of the edge costs rather than by their sum.
There are several algorihms to compute the regular minium spanning tree, but I am unsure of how to tweak them for the case mentioned above. Any ideas?
Thank you.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
由于 log(边成本的乘积) = sum (log(边成本))，只需对边权重进行对数变换，并找到这些权重的最小成本生成树。
Since log(product of edge costs) = sum (log(edge costs)), just log-transform the edge-weights, and find the minimum cost spanning tree for these weights.
由于对数是单调变换，因此当您取所有权重的对数时以及当您保留所有权重时，最小生成树将完全相同。
所以：根据所有权重之和和根据所有权重的乘积求MST没有区别。
对于事实证明的文章
那
图的最小生成树
对于 graoh 中权重的单调变换是不变的，
类型
最小生成树的传奇
在谷歌。
第一个链接就是您需要的链接。
第167页，单调同构。
Since a logarithm is a monotone transformation, the minimum spanning tree will be exactly the same when you take the log of all weights and when you leave all weights the way they are.
So: there is NO difference in finding the MST according to the sum of all weights and according to the product of all weights.
For the article of the proof of the fact
that
a minimum spanning tree of a graph
is invariant towards monotone transformation of the weights in the graoh,
type
The Saga of Minimum Spanning Tree
in google.
And the first link will be the one you need.
Page 167, monotone isomorphism.
我最好的想法 - 通过蛮力找到跨越树的所有最小（意味着不必要的边缘），选择具有最小产品的一个。
大多数（或全部）更有效的解决方案不再适用 - 主要是因为最佳解决方案不再必然包含最佳子问题。 （有什么限制？非常重要 - 成本小于 1 的边实际上是负成本，长度为 1 的边是免费的。它们最好都是正的！）
我不确定这个问题是否真的有意义。首先，您必须给出自循环成本（或假设 1），因为我们不能将乘积为零。分割路径的工作方式不同，同一条路径行驶两次要花费 c^2？此外，我觉得这应该是具有与“成本”不同名称的不同质量的路径
My best idea - Find ALL minimal (meaning to unnecessary edges) spanning trees by brute force, pick the one with smallest product.
Most (or all) more efficient solutions no longer apply - mainly bc optimal solutions NO LONGER necessarily contain optimal sub problems. (What are the restrictions? Very important - edges of cost less than 1 are actually negative cost, edges of length 1 are free. they BETTER be all positive!)
I'm not sure if this question is really meaningful. For one, you must either give self-loop costs (or assume 1) because we can't take product with zero. Splitting a path works differently, traveling the same path twice costs c^2? Furthermore, I feel like this should be a different quality of a path with a different name than 'cost'