python - 如何以编程方式将单圈时间分组以最小化差异？

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