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

你可以把它表示为一种 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 个的向量）

和 {0， 1} 中的 x_Y（i） 对于 {A， B， C， D} 中的所有 Y，{1， ...， N} 中的 i

你所最大化的实际上是赋值矩阵和偏好矩阵乘积的轨迹，这是一种半定整数规划算法。我很确定这是NP难的。

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

顺便说一句，这种方法是爬山的一种变体。基本上，在这个问题的上下文中，任何其他启发式方法中的任何一种都会有类似的类比。

符号：

播放器阵列：p[1], ..., p[n]

团队阵列：T[1], T[2], T[3], T[4]

意愿矩阵： ;维度 = ;= 愿意加入团队。这里的假设是，对于所有 .w[i,j]nx4w[i,j]piTjw[i,1] + w[i,2] + w[i,3] + w[i,4] = 1i

隶属度矩阵： ， dimension = ; 或者取决于是否属于。x[i,j]nx4x[i,j]=10piTj

满意度数组： ; .s[1], ..., s[n]s[i] := w[i,1] * x[i,1] + ... + w[i,4] * x[i,4]

满意度： .s := (s[1] + ... + s[n]) / n

操作：

假设如下：

1. x[k,q] = 1 (p[k]属于T[q])
2. x[k,r] = 0 (p[k]不属于T[r]
3. x[h,r] = 1 (p[h]属于T[r])
4. x[h,q] = 0 (p[h]不属于T[q]

该操作在团队和 之间交换球员和 。这是：swap([k,q][h,r])p[k]p[h]T[q]T[r]

1. x[k,q] := 0, .x[k,r] := 1
2. x[h,r] := 0, .x[h,q] := 1
3. s[k] := s[k] - w[k,q] + w[k,r], .s[h] = s[h] - w[h,r] + w[h,q]
4. s := (s * n - w[k,q] - w[h,r] + w[h,r] + w[k,q]) / n.

现在，您已准备好使用模拟退火来最大限度地提高满意度。以下是该算法的草图：s

1. 从任何配置开始（只需在球员出现时将球员分配到球队）

2. 建立温度

3. 随机选择两对[k,q][h,r]

4. 尝试操作。如果满意度增加，请接受交换。如果没有，则仅以一定的概率接受它，否则拒绝交换（有关详细信息，请参阅模拟退火算法）swaps

5. 重复步骤 3 和 4 多次。

6. 降低温度并返回 3。

言论：

如果玩家在范围内（或任何其他）有偏好，则将每个玩家的这些数字除以它们的总和，以获得每个玩家的意愿向量满足约束。1, ..., 4w[i,1] + ... + w[i,4] = 1

随机选择两对，并且必须满足操作的假设。因此，它基本上包括随机选择两支球队（和），然后每支球队两名球员。[h,q][k,r]swapqr

操作中的第 3 步和第 4 步对于最大限度地减少总和和乘积的数量至关重要，因此交换试验速度很快。swap

要拒绝 ，只需再次使用相同的对。swapswap