algorithm - 匹配算法效率

Question

我正在设计一个应用程序，它可以帮助用户通过组建最佳团队来创建游戏。

例如，假设有 30 个人在投票中等待打篮球。一场篮球比赛由 10 名球员进行(5 对 5)。在等待被选中的 30 人中，该算法会选择 5 对 5 的最佳组合进行对战。

(为此，该算法会寻找抽签概率最大的玩家组合。这是通过使用两个表征每个玩家的量词计算得出的:玩家的平均技能和猜测的置信度评分。)

我想看看这个算法有多快。

它需要遍历所有可能的玩家组合。所以在这种情况下，组合总数是 C(30,10) 对吗？

我们可以说该算法是 O(n!)，其中 n 是等待游戏的玩家总数吗？

这个问题是NP完全的吗？？如果是这样，谁能给我一个简短的方法来解释为什么它是 NP 完全的(不是完整的证明，只要有效的推理就足够了。)

非常感谢! :)

Answer 1

尚不清楚应如何组合平均技能和置信度因子，但最有可能的是，在 n 和 k 中找到多项式解(玩家数量，和每队球员的数量)就像证明 P = NP 一样困难。

我的直觉是基于一个事实 Subset Sum Problem是NP-Hard，目前的问题似乎比它更难。

在我们的案例中，即使是忽略置信度因素的简单方法，并且只是总结球员技能以获得团队实力 (1)，它似乎也是 NP-Complete。

那是因为即使我们固定了一个团队，即知道目标总和，也很难确定是否有另一个团队具有相同的分数 (2)。此外，回答“是否有平等的团队？”这个问题。比回答“哪支球队最合适？”更容易。

此外，在所有团队对中找到最佳匹配可能比在一个团队固定的情况下找到最佳匹配更难，因此这将直观地证明给定问题比子集求和问题更难。

---

备注:

(1) 以任何方式考虑置信度因素都不太可能简化问题(因为在特定情况下，当它们都相等时，我们仍然会遇到不相关置信度因素的情况)。

(2) 在子集求和问题中，没有对子集大小做任何假设。然而，如果有一个已知的多项式时间算法可以找到一个在多项式时间内总和为 0 的子集，对于任何给定的大小，我们可以将它应用于每个可能的大小，这将导致任意大小的多项式算法(这将证明 P = NP)。

(3) sum = 0 约束中的值 0 不是必需的。它可以是任意值。 例如因为我们固定了大小，我们可以简单地从所有元素中减去一个等于 targetSum/size 的值，我们现在将搜索总和为 0 的子集。

---

关于其他问题:

So in this case the total number of combination is C(30,10) right ?

不对，实际上是C(30, 5) * C(25, 5)/2，因为我们首先需要为第一队选出5名球员，然后再从其余的球员中选出5名球员作为第一队第二队。执行除以二是因为否则每对将被计算两次，我们可能不想区分团队。

Can we say that the algorithm is O(n!) with n being the total number of players waiting to play ?

暴力枚举的复杂度为 O(n^2k/(k! * k!))，其中 n 是玩家总数，k 是团队规模。因此，对于小的 k 是可以的。如果我们将 n 和 k 都视为变量，则该方法是 NP 完全的。

之所以如此复杂，是因为组合的公式如下:

C(n, k) = n * (n - 1) * .. * (n - k + 1)/(1 * 2 * .. * k),

根据上一点，有 C(n, k) * C(n - k, k)/2 种可能性。