我正在设计一个应用程序,该应用程序可以通过组成最佳的团队来帮助用户创建游戏。
例如,假设30个人在民意调查中等着打篮球。篮球比赛由10名球员(5 vs 5(进行。在等待被选中的30个人中,该算法选择了5 vs 5的最佳组合来互相比赛。
(为此,该算法寻找最大概率的玩家的组合。这是通过使用两个表征每个玩家的量化器来计算的:玩家的平均技能和猜测的置信度因素评级。(
我想看看该算法有多快。
它需要完成所有可能的玩家组合。因此,在这种情况下,组合总数为C(30,10(对吗?
我们可以说该算法是O(n!(,n是等待比赛的球员总数?
这个问题是NP完成吗?如果是这样,任何人都可以给我一些简短的方法来解释为什么它是NP完整的(不是一个完整的证据,只是有效的推理就足够了。(
非常感谢!:)
尚不清楚如何将平均技能和置信度因素组合在一起,但很可能是在n
和k
中找到多项式解决方案(球员数量和每个团队的球员数量((与证明p = np。
我的直觉是基于以下事实:子集总和问题是np-hard,而当前的问题似乎比它更困难。
在我们的情况下,即使是一种简单的方法,它会忽略信心因素,并且只会总结球员的技能以获得团队的力量(1(,这似乎是NP的完整。
那是因为即使我们修复了一个团队,知道目标总和,也很难确定是否有另一支球队的得分相同(2(。此外,回答"有平等的团队吗?"回答这个问题。比回答"这支球队最好的匹配?
更容易此外,在所有对团队中找到最佳匹配可能要比找到固定的一个团队的最佳匹配要难,因此,这将是一个直观的证明,即给定的问题比子集总和问题更难。
备注:
(1(不太可能以任何方式考虑信心因素会简化问题(因为在特定情况下,当它们都相等时,我们仍然遇到了无关紧要的置信度因素(。
((2(在子集总和问题中没有关于子集大小的假设。但是,如果将有一种已知的多项式时间算法,该算法将在任何给定的大小中找到一个在多项式时间中的总和为0的子集,我们可以在每个可能的大小上应用它,这将导致任意大小的多项式算法证明p = np(。
(3(总和= 0约束中的值0不是必需的。它可以是任何任意价值。,例如,因为我们固定了大小,所以我们可以简单地从所有元素中减去等于靶标/大小的值,现在我们将搜索具有sum 0的子集。
关于其他问题:
因此,在这种情况下,组合总数为c(30,10(对吗?
no,实际上是C(30,5( * C(25,5(/2,因为我们首先需要为第一支球队挑选5名球员,然后从其余的球员中选出5名球员第二队。执行两个部门,因为否则每对将两次计数,我们可能不想区分团队。
我们可以说算法是O(n!(,n是总数 等待比赛的球员?
蛮力枚举的复杂性为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可能性。