math - 根据玩家的选择分配团队的算法

Question

我在这里发现了非常相似的问题，但我找不到适合我的解决方案。所以这里的问题是:

我有 4 支球队和大量(超过 4 人)的球员。每个玩家根据自己的喜好对球队进行排名，例如:

B组

D组

A队

C组

最后，我希望每支球队都有偶数的球员，但要根据他们的选择来加权。

这是一种匈牙利算法，人多于工作。谁能帮我找到这个算法？我已经找了很长时间了。

Answer 1

您可以将其表示为一种 1-0 整数规划问题。

设 x_N 是描述团队分配的向量:如果 x_Y(i) = 1，人 i 在团队 Y 中，如果他们不在团队 Y 中，则 x_Y(i) = 0。|x_Y| = N，其中 N 是玩家数量。

另外，让 p_Y 是玩家对 Y 队的偏好权重，如果玩家 i 真的想加入 Y 队，则 p_Y(i) = 4，如果他们不想加入 Y 队，则 p_Y(i) = 1 .

(你可以用任何东西替换加权偏好 1 和 4，它们只是一个例子)。

解决您的问题的算法必须执行以下操作:

最大化:x_A*p_A + x_B*p_B + x_C*p_C + x_D*p_D

受制于:x_A + x_B + x_C + x_D = 1(N 个向量)

AND x_Y(i) in {0, 1} 对于 {A, B, C, D} 中的所有 Y, i in {1, ..., N}

您要最大化的实际上是分配矩阵和偏好矩阵的矩阵乘积的迹线，这是一种半定整数规划算法。我很确定那是 NP 难的。

解决此问题的一种启发式方法是将相同数量的玩家随机分配给团队。然后，如果他们使目标函数增加，您可以在团队之间进行一系列“交易”。更好的是，您可以在多项式时间内找出在任何给定任务中哪个交易是最好的交易。这不会给你一个最佳的分配，但我认为它会让你非常接近。

顺便说一下，这种方法是 hill climbing 的变体。 .基本上，任何其他 heuristic methods在这个问题的上下文中会有类似的模拟。