如何通过编程将圈时间分组成团队，以尽量减少差异？

Question

考虑到以下(任意)搭圈时间：

John: 47.20
Mark: 51.14
Shellie: 49.95
Scott: 48.80
Jack: 46.60
Cheryl: 52.70
Martin: 57.65
Karl: 55.45
Yong: 52.30
Lynetta: 59.90
Sueann: 49.24
Tempie: 47.88
Mack: 51.11
Kecia: 53.20
Jayson: 48.90
Sanjuanita: 45.90
Rosita: 54.43
Lyndia: 52.38
Deloris: 49.90
Sophie: 44.31
Fleta: 58.12
Tai: 61.23
Cassaundra: 49.38 
Oren: 48.39

我们正在进行一场卡丁车耐力比赛，而不是允许团队挑选，而是编写一个工具来处理最初的排位赛时间，然后吐出最接近的分组。

我最初的调查让我觉得这是一个团状图形类型的情况，但我从来没有玩过绘图算法，我觉得有点超出了我的深度。

什么是最快/最简单的方法，产生3人组与最接近的总体平均圈时间，以消除他们之间的总体优势/差异？

这是我可以使用networkx实现的东西吗?如果可以的话，我如何最好地定义上面的数据集的图表？

Answer 1

当你遇到这样的问题时，一种方法就是利用随机性。

当其他人说他们认为X或Y应该工作时，我知道我的算法至少会收敛到一个局部最大值。如果您可以证明任何状态空间都可以通过成对交换(对于旅行销售人员问题是正确的属性)从其他任何状态空间到达，则该算法将找到全局最优(给定的时间)。

此外，该算法试图最小化组间平均时间的标准差，因此它提供了一个自然的度量，说明你得到的答案有多好:即使结果不是精确的，得到0.058的标准差对你的目的来说也是足够接近的。

换句话说:可能有一个精确的解决方案，但随机化的解决方案通常很容易想象，编码不需要很长时间，可以很好地收敛，并且能够产生可接受的答案。

#!/usr/bin/env python3

import numpy as np
import copy
import random

data = [
  (47.20,"John"),
  (51.14,"Mark"),
  (49.95,"Shellie"),
  (48.80,"Scott"),
  (46.60,"Jack"),
  (52.70,"Cheryl"),
  (57.65,"Martin"),
  (55.45,"Karl"),
  (52.30,"Yong"),
  (59.90,"Lynetta"),
  (49.24,"Sueann"),
  (47.88,"Tempie"),
  (51.11,"Mack"),
  (53.20,"Kecia"),
  (48.90,"Jayson"),
  (45.90,"Sanjuanita"),
  (54.43,"Rosita"),
  (52.38,"Lyndia"),
  (49.90,"Deloris"),
  (44.31,"Sophie"),
  (58.12,"Fleta"),
  (61.23,"Tai"),
  (49.38 ,"Cassaundra"),
  (48.39,"Oren")
]

#Divide into initial groupings
NUM_GROUPS = 8
groups = []
for x in range(NUM_GROUPS): #Number of groups desired
  groups.append(data[x*len(data)//NUM_GROUPS:(x+1)*len(data)//NUM_GROUPS])

#Ensure all groups have the same number of members
assert all(len(groups[0])==len(x) for x in groups)

#Get average time of a single group
def FitnessGroup(group): 
  return np.average([x[0] for x in group])

#Get standard deviation of all groups' average times
def Fitness(groups):
  avgtimes = [FitnessGroup(x) for x in groups] #Get all average times
  return np.std(avgtimes) #Return standard deviation of average times

#Initially, the best grouping is just the data
bestgroups  = copy.deepcopy(groups)
bestfitness = Fitness(groups)

#Generate mutations of the best grouping by swapping two randomly chosen members
#between their groups
for x in range(10000): #Run a large number of times
  groups = copy.deepcopy(bestgroups)       #Always start from the best grouping
  g1 = random.randint(0,len(groups)-1)     #Choose a random group A
  g2 = random.randint(0,len(groups)-1)     #Choose a random group B
  m1 = random.randint(0,len(groups[g1])-1) #Choose a random member from group A
  m2 = random.randint(0,len(groups[g2])-1) #Choose a random member from group B
  groups[g1][m1], groups[g2][m2] = groups[g2][m2], groups[g1][m1] #Swap 'em
  fitness = Fitness(groups)                #Calculate fitness of new grouping
  if fitness<bestfitness:                  #Is it a better fitness?
    bestfitness = fitness                  #Save fitness
    bestgroups  = copy.deepcopy(groups)    #Save grouping

#Print the results
for g in bestgroups:
  for m in g:
    print("{0:15}".format(m[1]), end='') 
  print("{0:15.3f}".format(FitnessGroup(g)), end='')
  print("")
print("Standard deviation of teams: {0:.3f}".format(bestfitness))

运行几次后，标准偏差为0.058：

Cheryl         Kecia          Oren                    51.430
Tempie         Mark           Karl                    51.490
Fleta          Deloris        Jack                    51.540
Lynetta        Scott          Sanjuanita              51.533
Mack           Rosita         Sueann                  51.593
Shellie        Lyndia         Yong                    51.543
Jayson         Sophie         Tai                     51.480
Martin         Cassaundra     John                    51.410
Standard deviation of teams: 0.058

Answer 2

如果我的理解正确，只需对时间列表进行排序，并将前三名、下三名、前三名进行分组。

编辑:我没有正确理解

所以，我们的想法是把N个人分组成N/3团队，使N/3团队的平均次数比每个团队中的3人更接近，就像我错误地解释得越近越好。在这种情况下，我认为您仍然可以从按时间的递减顺序排序N个驱动程序开始。然后，初始化N/3团队的空列表。然后，对于每一名车手，按圈时间的顺序递减，将他们分配给当前总圈时间最小的车队(或者其中一支队伍，如果是平手)。这是一个简单的垃圾箱包装算法的变种。

下面是一个简单的Python实现：

times = [47.20, 51.14, 49.95, 48.80, 46.60, 52.70, 57.65, 55.45, 52.30, 59.90, 49.24, 47.88, 51.11, 53.20, 48.90, 45.90, 54.43, 52.38, 49.90, 44.31, 58.12, 61.23, 49.38, 48.39]

Nteams = len(times)/3
team_times = [0] * Nteams
team_members = [[]] * Nteams

times = sorted(times,reverse=True)
for m in range(len(times)):
    i = team_times.index(min(team_times))
    team_times[i] += times[m]
    team_members[i] = team_members[i] + [m]

for i in range(len(team_times)):
    print(str(team_members[i]) + ": avg time " + str(round(team_times[i]/3,3)))

其输出是

[0, 15, 23]: avg time 51.593
[1, 14, 22]: avg time 51.727
[2, 13, 21]: avg time 51.54
[3, 12, 20]: avg time 51.6
[4, 11, 19]: avg time 51.48
[5, 10, 18]: avg time 51.32
[6, 9, 17]: avg time 51.433
[7, 8, 16]: avg time 51.327

(请注意，团队成员的编号指的是他们从0开始按圈时间递减的顺序，而不是他们最初的顺序)。

其中一个问题是，如果时间变化很大，那么没有硬性限制让每支球队的球员人数精确到3人。然而，就你的目的而言，如果接力赛接近了接力赛，那也许没什么问题，而且在时间上的距离远远小于平均时间的情况下，这种情况可能是罕见的。

编辑，如果你只想在每支球队中有3名球员，那么在所有情况下，代码都可以进行小修改，以便在每一步找到没有指定三名球员的总圈时间最少的团队。这需要对主代码块进行小修改：

times = sorted(times,reverse=True)
for m in range(len(times)):
    idx = -1
    for i in range(Nteams):
        if len(team_members[i]) < 3:
            if (idx == -1) or (team_times[i] < team_times[idx]):
                idx = i
    team_times[idx] += times[m]
    team_members[idx] = team_members[idx] + [m]

对于问题中的例子，上面的解决方案当然是相同的，因为它没有尝试适合每队3名以上或少于3名球员。

Answer 3

下面的算法似乎运行得很好。它需要最快和最慢的人留下来，然后找到中间的人，使群体平均是最接近全球平均水平。由于极值首先被耗尽，尽管选择池有限，但最终的平均值不应该太远。

from bisect import bisect

times = sorted([47.20, 51.14, 49.95, 48.80, 46.60, 52.70, 57.65, 55.45, 52.30, 59.90, 49.24, 47.88, 51.11, 53.20, 48.90, 45.90, 54.43, 52.38, 49.90, 44.31, 58.12, 61.23, 49.38, 48.39])
average = lambda c: sum(c)/len(c)

groups = []
average_time = average(times)

while times:
    group = [times.pop(0), times.pop()]

    # target value for the third person for best average
    target = average_time * 3 - sum(group)
    index = min(bisect(times, target), len(times) - 1)

    # adjust if the left value is better than the right
    if index and abs(target - times[index-1]) < abs(target - times[index]):
        index -= 1

    group.append(times.pop(index))
    groups.append(group)

# [44.31, 61.23, 48.9]
# [45.9, 59.9, 48.8]
# [46.6, 58.12, 49.9]
# [47.2, 57.65, 49.38]
# [47.88, 55.45, 51.14]
# [48.39, 54.43, 51.11]
# [49.24, 53.2, 52.3]
# [49.95, 52.7, 52.38]

排序和迭代二进制搜索都是O(n log )，因此总复杂度为O(n log )。不幸的是，将其扩展到更大的群体可能会很困难。