algorithm - 哪些算法可以用来解决这种相似性最小化平衡概率？

Question

我到处都看过，但显然我似乎找不到正确的关键字来搜索合适的解决方案，所以问题来了:

---

*

I have a set of P elements [A, B ....Y, Z], and a matrix of PxP values which represent the similarity between every pair of elements (so the main diagonal is 100% and every other cell has a number between 0% and 100%). I want to partition this set into groups of N elements, so that the solution tends to minimize the average inner similarity of the groups

.*

---

你们能告诉我如何做到这一点吗？我曾尝试研究标准的分区算法，但大多数算法都不适用，因为权重取决于对，而不是个人。

谢谢!!

Answer 1

不幸的是，这个问题是 NP-hard 问题，这意味着不太可能有一个多项式时间算法来解决每个实例的最优问题。我将减少最大二分法。在这个问题的决策问题变体中，我们得到一个图 G 和一个数字 k，并要求将 G 的顶点分成两个大小相等的部分，使得两个部分之间的边数至少为 k。 These slides通过从更一般的最大割问题中归约，证明最大二分法是 NP 难的，其中两个部分不需要具有相同数量的顶点。

给定一个图 G = (V, E) 和数字 k，归约是:

• 创建矩阵 X，其中如果 (i, j) 是 G 中的一条边，则 X[i][j] = X[j][i] = 1，否则为 0。
• 选择 N = |V|/2。 (这将导致输出 2 组。)

在这个构造的输入上为你的问题运行任何精确的算法，并让这个算法提供的最优解具有平均相似度 y。 y = (y1+y2)/2，其中 y1 和 y2 是每组的平均相似度。我们称第一组中相似无序对(即无序对 (i, j) 使得 X[i][j] = 1)的数量为 z1。由于我们需要处理的唯一相似性分数是 1 和 0，y1 只是 z1 除以第一组中无序对的总数，正好是 (|V|/2)(|V|/2-1 )/2，所以 y1 = 2*z1/((|V|/2)(|V|/2-1))。对于 y2 也是如此。因此，对于 z1 和 z2，y = (z1+z2)/((|V|/2)(|V|/2-1))。由于分母是常数，通过最大化平均组内相似度 y，您的算法也最大化了 z1+z2，即它最大化了组内相似对的总数。

要注意的关键是，在任何解决方案中，原始图的每条边都必须出现在一个组内或两个不同的组之间:也就是说，对于任何解决方案 Y，nEdgesWithinAGroup(Y) + nEdgesBetweenGroups( Y) = |E|，因此最小化组内边的数量与最大化组间边的数量相同。

由于假设您的问题的算法返回一个具有最小可能 y 的解决方案，并且我们在上面已经确定这也意味着 z1+z2 的最小可能值，而且后者意味着最大可能数量之间-组边，它遵循两组之间的边数，|E| - z1 - z2，是最大可能的。因此，要解决最初的最大二分法问题，剩下的就是将这个值与给定的 k 值进行比较，如果 >= k 则返回 YES，否则返回 NO。

上面的意思是，给定任何多项式时间算法来解决您的问题，以及 NP-hard 最大二分法问题的任何实例，我们可以在多项式时间内构造您的问题的实例，解决它，并转换解决方案到原始最大二分问题的解决方案——也就是说，它意味着我们可以在多项式时间内解决 NP-hard 问题。这意味着您的问题本身就是 NP-hard。