algorithm - Prim 和 Kruskal 的应用，而不是寻找 MST

Question

我在 codechef 中看到一个问题，其目标是从图中选择边，使得所选边不形成循环，并且所有所选边的权重乘积最大。在社论中给出了 prim 和kruskal 算法在这里有效。事实上，它适用于最大化边的任何对称单调函数。那么究竟什么是对称单调函数以及我们还可以在哪些地方使用这种算法。

Answer 1

我猜作者的意思是:

如果你在生成树上的最终分数是 f(w1, w2, ... wn) 其中 wi 是边权重，那么 f 的权重应该是单调的。这意味着，如果您增加任何权重，f 将始终增加(单调增加)或始终减少(单调减少)。和与积都是单调递增的:

f_sum (w1, w2, ... wn) = w1 + w2 + ... + wn
f_prod(w1, w2, ... wn) = w1 * w2 * ... * wn //non-negative-weights

对称指的是顺序。 f 是对称的，如果你能确保 f(..., wi, ..., wj, ...) = f(..., wj, ..., wi , ...)。应该清楚为什么需要这样做。任何 MST 算法都应该只关心选择哪些边而不关心它们的顺序。和与积都是交换运算，因此是对称的。

之所以可行，是因为给定图形的所有生成树都具有相同数量的边。如果您贪婪地取最大可用边(对于单调递增函数)或最小边(对于单调递减函数)，您将自动最大化 f。

我所知道的大多数应用都是 MST 的应用(主要是近似最优解)。就概率模型而言，最大乘积可以指最大化最终概率，其中边表示单独事件然后组合的概率。我还没有偶然发现任何其他用于构建生成树的函数。