我的老师要求我们为这个问题实施一个动态编程解决方案，但我认为一个不存在，因为我无法使用谷歌找到它。
无论如何，给定一个图表和 ak，比如 3，你必须从中找到 3 个最好的 MST。如果该图没有 k 个子树，则可以多次返回同一棵树或次优树。
我实在想不出解决办法。
问问题
3547 次
1 回答
3
你让我困惑了一段时间，我认为你可能误解了这个问题。“k-MST”问题包括找到形成子树的 k 条边，使得其边的总和小于或等于您可以从 k 条边的子树中获得的所有其他总和。但后来我看到了复数 s。
好吧，对于您的问题，我个人会尝试找到一种 DP 算法来找到与生成“下一个”MST 的方式相结合的 MST。由于这是动态编程，我会考虑反复优化某些东西（在这种情况下，对每个步骤进行去优化）或以各种方式将边缘划分为在 MST 设置中有意义的子集。可能有几种方法。
但是，搜索分区和最小生成树时我发现了这一点，如果您只想要答案，这可能会更有帮助：http ://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382005000200004
于 2010-07-10T10:31:04.833 回答