Jak programować grupowo czasy okrążeń w zespoły, aby zminimalizować różnicę?

Question

Przy następujących (arbitralne) czasy okrążeń:

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 

Robimy gokartowy wyścig wytrzymałościowy, a pomysł, raczej niż umożliwiając zbieranie zespół jest napisać narzędzie do przetwarzania wstępnych razy kwalifikacyjne i a następnie wypluć najbliżej dopasowane grupy.

Moje wstępne badanie sprawia, że ​​mam wrażenie, że jest to sytuacja typu wykresu klikowego, ale nigdy nie grałem z algorytmami graficznymi. Czuję się raczej z dala od mojej głębi.

Jaka byłaby najszybsza/najprostsza metoda generowania grup 3 osób o najbliższym średnim łącznym czasie okrążenia, aby znieść ogólną przewagę/różnicę między nimi?

Czy jest to coś, czego mogę użyć networkx do osiągnięcia, a jeśli tak, jak najlepiej zdefiniować wykres, biorąc pod uwagę powyższy zestaw danych?

Answer 1

Gdy pojawia się taki problem, jednym z podejść jest zawsze zwiększanie losowości.

Podczas gdy inni ludzie mówią myślą X lub Y powinny działać, wiem mój algorytm będzie zbiegać do co najmniej lokalne maksima. Jeśli możesz pokazać, że dowolna przestrzeń stanów może być osiągnięta z dowolnej innej zamiany parami (właściwość, która jest prawdziwa, powiedzmy, z problemem Travelling Salesperson), wówczas algorytm znajdzie optimum globalne (dany czas).

Co więcej, algorytm próbuje zminimalizować odchylenie standardowe średnich czasów w grupach, dzięki czemu zapewnia naturalny wskaźnik skuteczności odpowiedzi: Nawet jeśli wynik jest nieścisły, uzyskanie standardu odchylenie 0,058 jest prawdopodobnie więcej niż wystarczająco blisko dla twoich celów.

Innymi słowy: może istnieć dokładne rozwiązanie, ale losowe rozwiązanie jest zwykle łatwe do wyobrażenia, nie zajmuje dużo czasu na kodowanie, może ładnie zbiegać się i jest w stanie wygenerować akceptowalne odpowiedzi.

#!/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)) 

Running to kilka razy daje odchylenie standardowe 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

Najprostszymz będzie po prostu utworzyć 3 wiadra - szybkie wiadro, średnie wiadro i powolne wiadro - i przypisać wpisy do wiader według ich czasów kwalifikacyjnych.

Następnie zespól najwolniejszego z wolnych, najszybszych z postu i mediany lub średniej z mediów. (Nie jestem pewien, czy mediana lub średnia to najlepszy wybór z mojej głowy.) Powtarzaj, aż skończy ci się wpis.

Answer 3

Jeśli dobrze rozumiem, po prostu posortuj listę razy i zgrupuj pierwsze trzy, następne trzy, w górę w pierwszej trójce.

EDIT: Ja nie rozumiem

Tak, chodzi o to, aby zabrać ludzi N i grupę ich do N/3 zespołów, dzięki czemu średni czas N/3 drużyny [zamiast 3 ludzie w każdym zespole, jak błędnie zinterpretowałem] jak najbliżej. W tym przypadku, myślę, że możesz zacząć od sortowania sterowników N w malejącej kolejności. Następnie zainicjuj pustą listę zespołów N/3. Następnie dla każdego kierowcy w malejącej kolejności czasu okrążenia, przydzielaj je drużynie z najmniejszym bieżącym łącznym czasem okrążenia (lub jedną z tych drużyn, w przypadku remisów). Jest to wariant prostego algorytmu pakowania bin.

Oto prosta implementacja Pythona:

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))) 

którego wyjście jest

[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 

(Zauważ, że liczba członków zespołu odnosić się do nich w kolejności czasu okrążenia malejącym, zaczynając od 0, a niż do pierwotnego zamówienia).

Jedną z kwestii jest to, że jeśli czasy są bardzo zróżnicowane, nie ma żadnych ograniczeń co do liczby graczy w każdej drużynie dokładnie 3. Jednakże, dla twoich celów, może to jest w porządku, jeśli zamyka przekaźnik, i prawdopodobnie jest to rzadkie zjawisko, gdy rozpiętość w czasie jest znacznie mniejsza niż średni czas.

EDIT Jeśli chcemy tylko 3 zawodników z każdej drużyny, we wszystkich przypadkach, wówczas kod może być modyfikowany do trywialnie na każdym kroku odnaleźć drużyna z najmniejszą całkowity czas okrążenia, które nie mają już trzy przydzieleni gracze.Wymaga to niewielkiej modyfikacji w głównym bloku kodu:

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] 

Na przykład błąd w pytaniu powyżej rozwiązanie jest oczywiście identyczne, ponieważ nie próbują dopasować bardziej lub mniej niż 3 graczy jednej drużyny.

Answer 4

Poniższy algorytm wydaje się działać całkiem dobrze. Przyjmuje najszybszych i najwolniejszych ludzi, a następnie znajduje osobę w środku, tak aby średnia dla grupy była najbliższa średniej globalnej. Ponieważ wartości ekstremalne są wykorzystywane w pierwszej kolejności, średnie na końcu nie powinny być aż tak daleko, pomimo ograniczonej puli selekcji.

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] 

Sortowanie i powtórzyć przeszukiwanie binarne są zarówno O (n log n) zatem całkowita złożoność O (n log n). Niestety, rozszerzenie tego na większe grupy może być trudne.