Thuật toán để chỉ định Nhóm dựa trên lựa chọn của người chơi

Question

Tôi đã tìm thấy các câu hỏi rất giống nhau ở đây nhưng tôi không thể tìm thấy giải pháp nào phù hợp với mình. Vì vậy, đây là vấn đề:

Tôi có 4 đội và số lượng người chơi lớn hơn (cao hơn 4). Mỗi người chơi xếp các đội bóng bởi theo ý thích, ví dụ họ:

1. Team B
2. Đội D
3. Đội A
4. Đội C

Cuối cùng tôi muốn có một số chẵn của các cầu thủ trong mỗi đội nhưng được cân nhắc bởi sự lựa chọn của họ.

Đó là một thuật toán Hungary, với nhiều người đàn ông hơn là việc làm. Bất cứ ai có thể giúp tôi tìm các thuật toán cho điều này? Tôi đã tìm kiếm trong một thời gian dài.

Answer 1

Bạn có thể trình bày vấn đề này như một vấn đề lập trình số nguyên sắp xếp 1-0.

Cho x_N là một vectơ mô tả phân công nhóm: người i ở trên đội Y nếu x_Y (i) = 1 và nếu họ không thuộc đội Y thì x_Y (i) = 0. | x_Y | = N, trong đó N là số lượng người chơi.

Ngoài ra, hãy p_Y là trọng số tùy chọn của người chơi cho đội Y, vì vậy p_Y (i) = 4 nếu người chơi tôi thực sự muốn tham gia đội Y và p_Y (i) = 1 nếu họ không muốn tham gia nhóm Y.

(Bạn có thể thay thế tùy chọn có trọng số 1 và 4 bằng bất kỳ thứ gì, chúng chỉ là một ví dụ).

Một thuật toán mà giải quyết vấn đề của bạn phải làm như sau:

Tối đa hóa: x_A * p_A + x_B * p_B + x_C * p_C + x_D * p_D

Đối tượng áp dụng: x_A + x_B + x_C + x_D = 1 (vectơ có N)

VÀ x_Y (i) trong {0, 1} cho tất cả Y trong {A, B, C, D}, i trong {1, ..., N}

Những gì bạn đang tối đa hóa thực sự là dấu vết của sản phẩm ma trận của ma trận gán và ma trận ưu tiên, đó là một lập trình số nguyên semidefinite al gorithm. Tôi khá chắc chắn đó là NP-cứng.

Một lý do để giải quyết điều này là gán ngẫu nhiên số lượng người chơi bằng nhau cho các đội. Sau đó, bạn có thể tạo một loạt các "giao dịch" giữa các nhóm nếu chúng làm tăng hàm mục tiêu. Tốt hơn, bạn có thể tìm ra trong thời gian đa thức mà giao dịch là giao dịch tốt nhất ở bất kỳ nhiệm vụ nào. Điều này sẽ không cung cấp cho bạn một nhiệm vụ tối ưu, nhưng tôi nghĩ rằng nó sẽ giúp bạn khá gần.

Phương pháp này, nhân tiện, là một biến thể trên hill climbing. Về cơ bản, bất kỳ số nào khác trong số các heuristic methods này sẽ có tương tự tương tự trong ngữ cảnh của vấn đề này.

Answer 2

Ký hiệu:

chơi mảng: p[1], ..., p[n]

Đội mảng: T[1], T[2], T[3], T[4]

Sẵn sàng ma trận: w[i,j]; dimension = nx4; w[i,j] = sự sẵn sàng của pi để ở trong đội Tj. Giả định ở đây là w[i,1] + w[i,2] + w[i,3] + w[i,4] = 1 cho tất cả i.

Ma trận thành viên: x[i,j], dimension = nx4; x[i,j]=1 hoặc 0 tùy thuộc vào việc pi có thuộc về Tj hay không.

Mảng hài lòng: s[1], ..., s[n]; s[i] := w[i,1] * x[i,1] + ... + w[i,4] * x[i,4].

Sự hài lòng: s := (s[1] + ... + s[n])/n.

hoạt động:

Giả như sau:

1. x[k,q] = 1 (p[k] thuộc về T[q])
2. x[k,r] = 0 (p[k] không thuộc trong T[r]
3. x[h,r] = 1 (p[h] thuộc về T[r])
4. x[h,q] = 0 (p[h] không thuộc trong T[q]

Các hoạt động swap([k,q][h,r]) giao người chơi p[k] và p[h] giữa đội T[q] và T[r]. Đây là:

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.

Bây giờ bạn đã sẵn sàng sử dụng Simulated Annealing để tối đa hóa sự hài lòng s.Dưới đây là một phác thảo của thuật toán:

1. Bắt đầu với bất kỳ cấu hình (chỉ cần gán cầu thủ đội như chúng hiển thị)

2. Thiết lập một nhiệt độ

3. Pick hai cặp [k,q] và [h,r] tại ngẫu nhiên

4. Hãy thử thao tác swap. Nếu sự hài lòng s tăng, hãy chấp nhận hoán đổi. Nếu không, chỉ chấp nhận nó với xác suất nhất định, nếu không thì hãy từ chối trao đổi (xem thuật toán Annulated Annealing để biết chi tiết)

5. Lặp lại bước 3 và 4 một số lần.

6. Giảm nhiệt độ và quay trở lại 3.

Ghi chú:

Nếu người chơi có sở thích trong khoảng 1, ..., 4 (hoặc bất kỳ khác,) chia cho mọi người chơi những con số bằng tổng của họ để có được vector sẵn sàng của mỗi người trong số họ đáp ứng các ràng buộc w[i,1] + ... + w[i,4] = 1.

Việc chọn ngẫu nhiên hai cặp [h,q] và [k,r] phải thỏa mãn các giả định của hoạt động swap. Vì vậy, về cơ bản nó bao gồm trong việc lựa chọn hai đội một cách ngẫu nhiên (q và r) và sau đó hai người chơi một trong mỗi đội.

Các bước 3 và 4 trong hoạt động swap là điều cần thiết để giảm thiểu số lượng và sản phẩm, vì vậy các thử nghiệm trao đổi rất nhanh.

Để từ chối swap, chỉ cần swap một lần nữa các cặp giống nhau.