平衡5v5团队(技能)

Question

我正在尝试编写一个算法，以获得10名球员的名字和MMR评分的元组列表(ELO系统)，该算法将输出2支球队，这应该是尽可能平衡的。

首先，从数学上讲，我应该围绕平均MMR还是中值进行平衡？如果有人有更具传奇色彩的方法，我很想听听。除此之外，我有时会收到这个msg (

Traceback (most recent call last):
  File "<pyshell#22>", line 1, in <module>
    Red,Blue=closest(lst,1591)
  File "C:\Users\Daniel\AppData\Local\Programs\Python\Python39-32\dd.py", line 45, in closest
    lst.remove(Red[1])
ValueError: list.remove(x): x not in list)

是什么导致了这种情况？

import random
import statistics
def avgmmr(lst,num):
    sumi=0
    for i in range(num):
        #print(lst[i][1])
        sumi+=lst[i][1]
    
    return sumi/num


def closest(lst,avg):
    cavg=0
    bestdiff=1000
    Red=[]
    placeholder=[]
    randi=random.randint(0,9)
    newavg=((avg*5)-lst[randi][1])/4 "choosing 1 player random and checking the neeeded avg with him"
    for i in range(1,5)
        for j in range(1+i,8):
            for k in range(j+1,8):
                for s in range(k+1,8):
                    curravg=(lst[i][1]+lst[j][1]+lst[k][1]+lst[s][1])/4  "checking the current avg of 4 players"
                    currdiff=abs(newavg-curravg)
                    if (newavg==curravg) : 
                        Red.append(lst[i],lst[j],lst[k],lst[s])
                        return Red
                    elif(currdiff<bestdiff): "checking if we found the closest to the avg so far"
                        cavg=curravg
                        bestdiff=abs(newavg-cavg)
                        placeholder=[i,j,k,s]
    Red=[lst[randi],lst[placeholder[0]],lst[placeholder[1]],lst[placeholder[2]],lst[placeholder[3]]]
    Red.append(avgmmr(Red,5))
    lst.pop(randi)
    lst.remove(Red[1])
    lst.remove(Red[2])
    lst.remove(Red[3])
    lst.remove(Red[4])
    bavg=avgmmr(lst,5)
    lst.append(bavg)
    return Red,lst

Answer 1

关于平衡中位数或平衡平均值

• 平衡中间层是一个糟糕的想法。考虑极端例子eam1=999,999,1000,10000,10000和team2=0，0,1000,1001,1001:两者都有相同的中位数1000，但很明显，Partition Problem.

比eam1=999强得多。means使这个问题成为team2.

• Balancing

贪婪数分划

我不想费心去理解和调试您的代码，但这里有一个greedy number partitioning的实现。

这是一个简单的贪婪算法：

• 按球员的rating;
• Consider排序接下来的两名球员；
• 将这两名球员中较强的一名添加到当前较弱的球队中；
• 将这两名球员中较弱的一名添加到当前较强的球队中。

由于其贪婪的性质，不能保证找到最优解。然而，它肯定会找到7/6的近似值。也就是说，保证比率(average rating of stronger team with this algorithm) / (average rating of stronger team in optimal solution)在1到1.167之间。

import random

def get_rank(player):
    return player[1]

def make_teams(players):
    sorted_players = sorted(players, key=get_rank)
    team1 = []
    team2 = []
    total_diff = 0
    for p1, p2 in zip(sorted_players[::2], sorted_players[1::2]):
        current_diff = get_rank(p2) - get_rank(p1)
        if total_diff * current_diff >= 0:
            team2.append(p1)
            team1.append(p2)
            total_diff -= current_diff
        else:
            team2.append(p2)
            team1.append(p1)
            total_diff += current_diff
    return team1, team2

players = [(name, random.randint(1200, 2500)) for name in ['Yao', 'Ilshat', 'Juan', 'Hannah', 'Sadaph', 'Anand', 'Khadija', 'Mohammed', 'Donglai', 'Morgan']]

team1, team2 = make_teams(players)

avg1 = sum(r for n,r in team1) / len(team1)
avg2 = sum(r for n,r in team2) / len(team2)
avg = (avg1*len(team1) + avg2*len(team2)) / len(players)

print(players)
print(avg1, team1)
print(avg2, team2)
print('ratio: ', max(avg1, avg2) / avg)

# [('Yao', 1757), ('Ilshat', 2318), ('Juan', 1560), ('Hannah', 1380), ('Sadaph', 2462), ('Anand', 1332), ('Khadija', 1644), ('Mohammed', 1449), ('Donglai', 1531), ('Morgan', 2284)]
# 1738.4 [('Hannah', 1380), ('Mohammed', 1449), ('Khadija', 1644), ('Yao', 1757), ('Sadaph', 2462)]
# 1805.0 [('Anand', 1332), ('Donglai', 1531), ('Juan', 1560), ('Morgan', 2284), ('Ilshat', 2318)]

# ratio:  1.0188