匹配算法效率
Matchmaking algorithm effeciency
我正在设计一个应用程序，它可以帮助用户通过组建最佳团队来创建游戏。
例如，假设有 30 个人在投票中等待打篮球。一场篮球比赛由 10 名球员进行（5 对 5）。
在等待被选中的 30 人中，该算法会选择 5 对 5 的最佳组合进行对战。
（为此，该算法会寻找平局概率最大的玩家组合。这是通过使用两个表征每个玩家的量词计算得出的：玩家的平均技能和置信度猜测的评分。）
我想看看这个算法有多快。
它需要遍历所有可能的玩家组合。所以在这种情况下，组合总数是 C(30,10) 对吗？
我们可以说该算法是 O(n!)，其中 n 是等待游戏的玩家总数吗？
这个问题是NP完全的吗？？如果是这样，谁能给我一个简短的方法来解释为什么它是 NP 完全的（不是完整的证明，只要有效的推理就足够了。）
非常感谢！ :)
尚不清楚应如何将平均技能和置信度因素结合起来，但最有可能的是，在 n 和 k 中找到多项式解（玩家人数和玩家人数每个团队）就像证明 P = NP 一样困难。
我的直觉是基于 Subset Sum Problem 是 NP-Hard 的事实，而当前的问题似乎比它更难。
在我们的例子中，即使是忽略置信度因素的简单方法，只是总结球员技能以获得球队实力 (1)，它似乎也是 NP-Complete。
那是因为即使我们固定了一个队，即知道了目标总和，也很难确定是否有另一队得分相同（2）。此外，回答问题 "is there an equal team?" 比回答 "which is the best match for this team?".
更容易
此外，在所有团队对中找到最佳匹配可能比在一个团队固定的情况下找到最佳匹配更难，因此这将直观地证明给定问题比子集求和问题更难。
备注：
(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种可能性。
我正在设计一个应用程序，它可以帮助用户通过组建最佳团队来创建游戏。
例如，假设有 30 个人在投票中等待打篮球。一场篮球比赛由 10 名球员进行（5 对 5）。 在等待被选中的 30 人中，该算法会选择 5 对 5 的最佳组合进行对战。
（为此，该算法会寻找平局概率最大的玩家组合。这是通过使用两个表征每个玩家的量词计算得出的：玩家的平均技能和置信度猜测的评分。）
我想看看这个算法有多快。
它需要遍历所有可能的玩家组合。所以在这种情况下，组合总数是 C(30,10) 对吗？
我们可以说该算法是 O(n!)，其中 n 是等待游戏的玩家总数吗？
这个问题是NP完全的吗？？如果是这样，谁能给我一个简短的方法来解释为什么它是 NP 完全的（不是完整的证明，只要有效的推理就足够了。）
非常感谢！ :)
尚不清楚应如何将平均技能和置信度因素结合起来，但最有可能的是，在 n 和 k 中找到多项式解（玩家人数和玩家人数每个团队）就像证明 P = NP 一样困难。
我的直觉是基于 Subset Sum Problem 是 NP-Hard 的事实，而当前的问题似乎比它更难。
在我们的例子中，即使是忽略置信度因素的简单方法，只是总结球员技能以获得球队实力 (1)，它似乎也是 NP-Complete。
那是因为即使我们固定了一个队，即知道了目标总和，也很难确定是否有另一队得分相同（2）。此外，回答问题 "is there an equal team?" 比回答 "which is the best match for this team?".
更容易此外，在所有团队对中找到最佳匹配可能比在一个团队固定的情况下找到最佳匹配更难，因此这将直观地证明给定问题比子集求和问题更难。
备注：
(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种可能性。