是否有动态规划方法来计算 k 个最小生成树？
我的老师要求我们实现一个动态编程解决方案来解决这个问题，但我认为这个解决方案不存在，因为我无法使用谷歌找到它。
不管怎样，给定一个图和 ak，比如说 3，你必须从中找到 3 个最好的 MST。如果该图没有 k 个子树，则可以多次返回同一棵树或次优树。
我实在想不出解决办法。
My teacher asked us to implement a Dynamic Programming solution to that problem, but I'm thinking one doesn't exist since I couldn't find it using Google.
Anyway, given a graph and a k, say 3, you have to find the 3 best MSTs from it. If the graph is such that it doesn't have k subtrees, you can return either the same tree multiple times or suboptimal trees.
I can't really think of a solution to it.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
你让我困惑了一段时间，我认为你可能误解了这个问题。 “k-MST”问题包括找到形成子树的 k 个边，使得其边的总和小于或等于从 k 个边的子树中可以获得的所有其他总和。但后来我看到了复数 s。
好吧，对于你的问题，我个人会尝试找到一种 DP 算法来查找与生成“下一个”MST 的方法相结合的 MST。由于这是动态编程，我会考虑重复优化某些内容（在本例中是对每个步骤进行反优化），或者采用各种方式将边划分为在 MST 设置中有意义的子集。可能有几种方法。
但是，在搜索分区和最小生成树时，我发现了这一点，如果您只想得到答案，这可能会更有帮助： http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382005000200004
You had me confused for a while there and I thought you might have misunderstood the problem. The "k-MST" problem consists of finding k edges that form a subtree such that the sum of its edges is less than or equal to all other sums you can get from subtrees of k edges. But then I saw the plural s.
So ok, for your problem, I personally would try to find a DP-algorithm for finding the MST that combines with a way of generating a "next" MSTs. Since this is dynamic programming I'd look into repeatedly optimizing something (in this case de-optimizing for each step) or at various ways of partitioning edges into subsets that make sense in an MST setting. There might be several ways.
However, searching for partitions and minimum spanning trees I found this, which might be more of help if you just want the answer: http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382005000200004