Algorytm przypisywania zespołu w oparciu o wybór gracza

Question

Znalazłem bardzo podobne pytania tutaj, ale nie mogłem znaleźć rozwiązania, które byłoby dla mnie skuteczne. Oto problem:

Mam 4 drużyny i ogromną (wyższą niż 4) liczbę graczy. Każdy gracz szeregach drużyny ich potrzeb, np:

1. Drużyna B
2. zespołu D
3. Drużyna A
4. Zespół C

W końcu chcę mieć parzystą liczbę graczy w każdym zespole, ale ważeni ich wyborami.

To węgierski algorytm, z większą liczbą mężczyzn niż z pracy. Czy ktoś może mi pomóc znaleźć algorytm dla tego? Długo szukałem.

Answer 1

Można to przedstawić jako rodzaj programowania w przedziale 1-0.

Niech x_N będzie wektorem opisującym przypisanie zespołu: osoba i jest w zespole Y, jeśli x_Y (i) = 1, a jeśli nie ma drużyny Y, to x_Y (i) = 0. | x_Y | = N, gdzie N to liczba graczy.

Niech też p_Y będzie wagą preferowaną przez gracza dla drużyny Y, tak aby p_Y (i) = 4, gdy gracz naprawdę chce być w drużynie Y, a p_Y (i) = 1, jeśli nie chce być w zespole Y.

(Możesz zastąpić ważone preferencje 1 i 4 czymkolwiek, są tylko przykładem).

algorytm, który rozwiązuje problem należy wykonać następujące czynności:

Maksymalizacja: x_A * p_A + x_B * p_B + x_C * p_C + x_D * p_D

zastrzeżeniem: x_A + x_B + x_C + x_D = 1 (wektor z N)

ORAZ x_Y (i) w {0, 1} dla wszystkich Y w {A, B, C, D}, w {1, ..., N}

To, co maksymalizujesz, jest w rzeczywistości śladem macierzowego iloczynu macierzy przypisania i preferencji, która jest seminefinite integer al gorithm. Jestem prawie pewien, że to NP-trudne.

Jedną z heurystycznych metod rozwiązania tego problemu jest losowe przydzielenie równej liczby graczy drużynom. Następnie możesz wykonać serię "transakcji" między zespołami, jeśli zwiększą one funkcję celu. Co więcej, możesz znaleźć czas wielomianowy, który jest najlepszy w danym zadaniu. To nie da ci optymalnego zadania, ale myślę, że to ci się uda.

Metoda ta, nawiasem mówiąc, jest odmianą hill climbing. Zasadniczo każdy z tych innych heuristic methods będzie miał podobny analog w kontekście tego problemu.

Answer 2

postaciach:

tablicy gracza: p[1], ..., p[n]

Tablica zespołu: T[1], T[2], T[3], T[4]

Gotowość matrycy: w[i,j]; dimension = nx4; w[i,j] = gotowość pi do zostania w drużynie Tj. Założeniem jest tutaj, że w[i,1] + w[i,2] + w[i,3] + w[i,4] = 1 dla wszystkich i.

Macierz członkostwa: x[i,j], wymiar = nx4; x[i,j]=1 lub 0 w zależności od tego, czy pi należy do Tj, czy nie.

Tablica satysfakcji: s[1], ..., s[n]; s[i] := w[i,1] * x[i,1] + ... + w[i,4] * x[i,4].

Satysfakcja: s := (s[1] + ... + s[n])/n.

pracy:

przyjęto następujące założenia:

1. x[k,q] = 1 (p[k] przynależy T[q])
2. x[k,r] = 0 (p[k] nie podlega T[r]
3. x[h,r] = 1 (p[h] przynależy T[r])
4. x[h,q] = 0 (p[h] nie należą T[q]

Operacja swap([k,q][h,r]) węzłów graczy p[k] i p[h] między zespołami T[q] i T[r]. Jest to:

1. x[k,q] := 0, x[k,r] := 1.
2. x[h,r] := 0, x[h,q] := 1.
3. s[k] := s[k] - w[k,q] + w[k,r], s[h] = s[h] - w[h,r] + w[h,q].
4. s := (s * n - w[k,q] - w[h,r] + w[h,r] + w[k,q])/n.

Teraz jesteś gotowy do użycia symulowanego wyżarzania, aby zmaksymalizować satysfakcję s.Oto szkic algorytmu:

1. zacząć od dowolnej konfiguracji (wystarczy przypisać zawodników do zespołów jak oni pokazać się)

2. Ustalić temperaturę

3. Wybierz dwie pary [k,q] i [h,r] na losowy

4. Wypróbuj operację swap. Jeśli wzrośnie satysfakcja s, zaakceptuj zamianę. Jeśli tak się nie stanie, zaakceptuj to tylko z pewnym prawdopodobieństwem, w przeciwnym razie odrzuć zamianę (zobacz szczegóły w algorytmie symulowanego wyżarzania).

5. Powtórz kroki 3 i 4 kilka razy.

6. Zmniejszyć temperaturę i powrócić do 3.

Uwagi:

Jeśli gracze mają preferencje w zakresie 1, ..., 4 (lub jakiegokolwiek innego), podziału dla każdego gracza przez te numery ich suma, aby uzyskać wektor gotowości każdego z nich, spełnia warunek w[i,1] + ... + w[i,4] = 1.

Losowy wybór dwóch par [h,q] i [k,r] musi spełniać założenia operacji swap. Zasadniczo polega to na losowym wybraniu dwóch drużyn (q i r), a następnie dwóch graczy po jednym w każdej drużynie.

Kroki 3 i 4 w operacji swap są niezbędne, aby zminimalizować liczbę sum i produktów, dlatego próby wymiany są szybkie.

Aby odrzucić numer swap, wystarczy swap ponownie te same pary.