我有4个团队和大量(高于4个)的球员。每位球员按照自己的喜好排列团队,例如:
1. B 队 2. D 队 3. A 队 4. C 队
最终,我希望每个团队都有偶数个球员,但是也要考虑他们的选择权重。
这是一个匈牙利算法,有更多的人而不是工作机会。有人能帮我找到这个算法吗?我已经搜索了很长时间。
符号说明:
玩家数组:p[1], ..., p[n]
队伍数组:T[1], T[2], T[3], T[4]
意愿矩阵:w[i,j]
;维度=nx4
;w[i,j]
表示pi
加入Tj
的意愿。这里假设对于所有的i
,有w[i,1] + w[i,2] + w[i,3] + w[i,4] = 1
。
成员矩阵:x[i,j]
;维度=nx4
;x[i,j]=1
或0
,取决于pi
是否属于Tj
。
满意度数组:s[1], ..., s[n]
;s[i] := w[i,1] * x[i,1] + ... + w[i,4] * x[i,4]
。
满意度: s := (s[1] + ... + s[n]) / n
。
操作:
假设以下内容:
x[k,q] = 1
(p[k]
属于 T[q]
)x[k,r] = 0
(p[k]
不属于 T[r]
x[h,r] = 1
(p[h]
属于 T[r]
)x[h,q] = 0
(p[h]
不属于 T[q]
操作 swap([k,q][h,r])
在队伍 T[q]
和 T[r]
之间交换选手 p[k]
和 p[h]
。这是:
x[k,q] := 0
,x[k,r] := 1
。x[h,r] := 0
,x[h,q] := 1
。s[k] := s[k] - w[k,q] + w[k,r]
,s[h] = s[h] - w[h,r] + w[h,q]
。s := (s * n - w[k,q] - w[h,r] + w[h,r] + w[k,q]) / n
。现在您可以使用模拟退火算法来最大化满意度 s
。以下是算法的概述:
从任何配置开始(只需将玩家分配到他们出现的团队)
确定一个温度
随机选择两对 [k,q]
和 [h,r]
尝试 swap
操作。如果满意度 s
增加,则接受交换。如果不增加,则仅以一定概率接受它,否则拒绝交换(有关详细信息,请参见模拟退火算法)
重复步骤 3 和 4 多次。
降低温度并返回步骤 3。
备注:
如果玩家在范围 1, ..., 4
(或其他任何范围)内具有偏好,则为每个玩家将这些数字除以它们的总和,以获得满足约束条件 w[i,1] + ... + w[i,4] = 1
的每个玩家的意愿向量。
随机选择两对[h,q]
和[k,r]
必须满足swap
操作的假设。因此,基本上是随机选择两个团队(q
和r
),然后在每个团队中选择一个球员。
swap
操作中的步骤3和4对于最小化求和和乘积的数量至关重要,因此交换尝试很快。
要拒绝swap
,只需再次交换相同的配对即可。
您可以将此问题表示为一种类似于01整数规划问题的形式。
令x_N为描述团队分配的向量:如果人员i在团队Y上,则x_Y(i)=1,如果他们不在团队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个1的向量)
并且对于所有Y∈{A,B,C,D},i∈{1,...,N},x_Y(i)∈{0,1}
你要最大化的实际上是分配矩阵和偏好矩阵的乘积的迹,这是一个半定整数规划算法。我很确定这是NP难问题。
解决这个问题的一种启发式方法是随机将相同数量的玩家分配到团队中。然后,如果它们使目标函数增加,您可以在团队之间进行一系列“交易”。更好的是,您可以在任何给定的分配中在多项式时间内找出哪个交易是最佳的。这不会给您最优的分配,但我认为它会让您接近最优。