Lập kế hoạch cạnh tranh

Question

Tôi cần phải tạo lịch biểu của sự kiện thể thao.

Có 30 đội. Mỗi đội phải chơi 8 trận. Điều này có nghĩa là không thể cho mỗi đội thi đấu lại tất cả các đội khác, nhưng tôi cần phải tránh hai đội đó thi đấu nhiều lần với nhau.

Ý tưởng của tôi là tạo tất cả các kết quả phù hợp (cho 30 đội: (30*29)/2 = 435 matches) và chọn từ danh sách này 120 trận đấu (8 trận cho mỗi đội: 8 * 30/2 = 120 matches).

Đây là nơi tôi đang gặp khó khăn: làm cách nào tôi có thể chọn 120 kết quả phù hợp này? Tôi đã thử một số giải pháp đơn giản (tham gia trận đấu đầu tiên của danh sách, sau đó cuối cùng, v.v.) nhưng dường như họ không làm việc với 30 đội. Tôi cũng đã cố gắng để tạo ra tất cả các kết hợp phù hợp có thể và tìm thấy một trong những đang làm việc nhưng với 30 đội, đây là quá nhiều thời gian tính toán.

Có một thuật toán hiện có mà tôi có thể triển khai không?

CẬP NHẬT

Những gì tôi cần để sản xuất là một lịch trình đơn giản, mà không cần loại bỏ. Mỗi đội chơi 8 trận, và đó là tất cả. Vào cuối ngày, sẽ không có một người chiến thắng nào.

Mỗi đội sẽ có lịch biểu của mình và lịch biểu này sẽ không thay đổi khi họ thắng hoặc thua. Việc lập kế hoạch được thực hiện cho cả ngày và không thay đổi.

UPDATE 2

Lúc đầu, tôi không muốn đặt quá nhiều trở ngại đối với câu hỏi của tôi, nhưng có vẻ như không có bất kỳ hạn chế (trừ mỗi đội không thi đấu nhiều hơn một lần với nhau) , chỉ cần chọn ngẫu nhiên 8 trận đấu cho mỗi đội.

Vì vậy, đây là một số chi tiết:

Trong sự kiện thể thao này, có 6 differents thể thao (bóng đá, bóng ném, bóng rổ, và vân vân). Điều này có nghĩa là có 6 trận đấu đồng thời. Một vòng mới được bắt đầu sau mỗi 15 phút.

Mỗi đội sẽ phải chơi 8 trận đấu và mỗi môn thể thao ít nhất một lần.

6 môn thể thao này diễn ra tại ba địa điểm khác nhau. Điều này có nghĩa là trong ngày, mỗi đội sẽ phải di chuyển từ nơi này sang nơi khác. Những động thái này nên được giảm càng nhiều càng tốt.

Một nhóm không thể chơi hai trận đấu liên tiếp.

Answer 1

Bạn có chắc chắn không thể nhận 32 đội :-) không?

Điều đó sẽ làm cho mọi việc trở nên đơn giản hơn - có cấu trúc giải đấu tiêu chuẩn, nhưng có số người thua cuộc từ mỗi vòng chơi trong biểu đồ của riêng họ. Tôi nghĩ điều này sẽ tối đa hóa số lượng đội giành được ít nhất một trận đấu trong sự kiện.

Với 30 đội, bạn có thể có 2 đội chơi một 'thân thiện' và có một ở vòng đầu tiên. Nhưng tổ chức trở nên phức tạp hơn nhiều.

Answer 2

Tôi không biết của một thực hiện, nhưng đây là một giải pháp khả thi cho bạn:

Hãy ba nhóm 9 đội và ghép chúng mỗi với tất cả những người khác, vì vậy mà mỗi lần đóng chống lại tất cả những người khác. Mỗi trong số 27 đội hiện đang chơi 8 trận.

Bây giờ, hãy thực hiện ba nhóm còn lại, một nhóm cho mỗi nhóm.

Sửa đổi một số trò chơi của mỗi đội:

1-2 -> 1-10, 2-10 
3-4 -> 3-10, 4-10 
5-6 -> 5-10, 6-10 
7-8 -> 7-10, 8-10 

Answer 3

Bạn có thể nhìn vào một số hợp đã được biết đến phương pháp tiếp cận:

Ví dụ: Swiss Chess system

Edit:

Sau khi đọc yêu cầu của bạn một lần nữa - mà mỗi đội phải chơi mỗi đội khác đúng một lần, và đó là một chiến thắng không nhất thiết phải quyết định. Có vẻ như một hệ thống Round Robin đơn lẻ sẽ làm những gì bạn muốn. Bạn chỉ có thể thả bất kỳ trận đấu bổ sung nào trên số 8 mà bạn cần.

Answer 4

Nó khá đơn giản thực sự, chỉ cần đội lên đội i với i-4, i-3, i-2, i-1, i+1, i+2, i+3, i+4. Điều này có thể được thực hiện bằng cách sử dụng thuật toán dưới đây.

import java.util.*; 

public class Test { 

    public static void main(String[] args) { 

     int TEAMS = 30, MATCHES = 8; 
     int[] matchCount = new int[TEAMS]; // for a sanity check. 
     List<Match> matches = new ArrayList<Match>(); 

     for (int team1 = 0; team1 < TEAMS; team1++) 
      for (int team2 = team1 + 1; team2 <= team1 + MATCHES/2; team2++) { 
       matches.add(new Match(team1, team2 % TEAMS)); 

       // Just for a sanity check: 
       matchCount[team1]++; 
       matchCount[team2 % TEAMS]++; 
      } 

     System.out.println(matches); 

     // Sanity check: 
     System.out.println(matches.size()); 
     System.out.println(Arrays.toString(matchCount)); 
    } 

    static class Match { 
     int team1, team2; 
     public Match(int team1, int team2) { 
      this.team1 = team1; 
      this.team2 = team2; 
     } 
     public String toString() { 
      return team1 + " vs " + team2; 
     } 
    } 
} 

Output:

[0 vs 1, 0 vs 2, 0 vs 3, 0 vs 4, 1 vs 2, 1 vs 3, 1 vs 4, 1 vs 5, 2 vs 3, 2 vs 4, 2 vs 5, 2 vs 6, 3 vs 4, 3 vs 5, 3 vs 6, 3 vs 7, 4 vs 5, 4 vs 6, 4 vs 7, 4 vs 8, 5 vs 6, 5 vs 7, 5 vs 8, 5 vs 9, 6 vs 7, 6 vs 8, 6 vs 9, 6 vs 10, 7 vs 8, 7 vs 9, 7 vs 10, 7 vs 11, 8 vs 9, 8 vs 10, 8 vs 11, 8 vs 12, 9 vs 10, 9 vs 11, 9 vs 12, 9 vs 13, 10 vs 11, 10 vs 12, 10 vs 13, 10 vs 14, 11 vs 12, 11 vs 13, 11 vs 14, 11 vs 15, 12 vs 13, 12 vs 14, 12 vs 15, 12 vs 16, 13 vs 14, 13 vs 15, 13 vs 16, 13 vs 17, 14 vs 15, 14 vs 16, 14 vs 17, 14 vs 18, 15 vs 16, 15 vs 17, 15 vs 18, 15 vs 19, 16 vs 17, 16 vs 18, 16 vs 19, 16 vs 20, 17 vs 18, 17 vs 19, 17 vs 20, 17 vs 21, 18 vs 19, 18 vs 20, 18 vs 21, 18 vs 22, 19 vs 20, 19 vs 21, 19 vs 22, 19 vs 23, 20 vs 21, 20 vs 22, 20 vs 23, 20 vs 24, 21 vs 22, 21 vs 23, 21 vs 24, 21 vs 25, 22 vs 23, 22 vs 24, 22 vs 25, 22 vs 26, 23 vs 24, 23 vs 25, 23 vs 26, 23 vs 27, 24 vs 25, 24 vs 26, 24 vs 27, 24 vs 28, 25 vs 26, 25 vs 27, 25 vs 28, 25 vs 29, 26 vs 27, 26 vs 28, 26 vs 29, 26 vs 0, 27 vs 28, 27 vs 29, 27 vs 0, 27 vs 1, 28 vs 29, 28 vs 0, 28 vs 1, 28 vs 2, 29 vs 0, 29 vs 1, 29 vs 2, 29 vs 3] 
120 
[8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8] 

Nếu bạn muốn một thiết lập ngẫu nhiên hơn, bạn chỉ có thể gán một số ngẫu nhiên từ 1 đến 30 cho mỗi đội.

---

Cập nhật Để đối phó với những hạn chế bị sang trọng: Hãy để trận đấu i có thể thao i mod 6.

Answer 5

Thuật toán của nhà môi giới có thể hoạt động. Funnily đủ Tôi không thể tìm thấy một mô tả tốt trong mạng, vì vậy tôi sẽ cố gắng giải thích hệ thống.

Có hiệu quả, mỗi đội sẽ yêu cầu đội khác ghi điểm cho trận đấu và trận đấu điểm số cao nhất được chọn. Điều này được lặp lại cho mỗi đội và trận đấu. Lịch trình kết quả được lưu và tổng số điểm được tính. Sau đó, với các điểm bắt đầu khác nhau (nghĩa là bạn chỉ có thể ngẫu nhiên thứ tự nhóm) điều này được thực hiện lại và nếu tổng số điểm cao hơn, lịch trình này được chọn thay thế. Bạn lặp lại điều này cho đến khi bạn tìm thấy một lịch biểu cho điểm số cao hoặc đủ sau một số lần thử được xác định trước.

Tổng số điểm có thể được tính theo khoảng cách mà mỗi đội di chuyển, số càng nhỏ càng tốt. Rõ ràng là bạn không chọn các trận đấu phá vỡ các quy tắc của bạn (quá nhiều trận đấu thuộc loại tương tự, cùng một đội chơi với nhau một lần nữa).

chấm điểm có thể đi một cái gì đó như thế này:

1. Nếu cùng một địa điểm cho các đội: 100 điểm (ví dụ: nếu cho cả = 200).
2. Để di chuyển giữa các địa điểm, điểm số được xác định cho cả hai đội tùy thuộc vào độ dài, tức là A -> B và B -> A 50 điểm (họ ở gần) A -> C và C -> A 30 điểm (không quá gần) B -> C và C -> B 0 điểm (chuyến đi chúng tôi muốn làm càng ít càng tốt).
3. Nếu nhóm chưa chơi môn thể thao này: 100 điểm.
4. Nếu đội đã chơi môn thể thao này một lần: 50 điểm.

Tất nhiên vấn đề với BA là tìm giá trị tốt cho các thông số khác nhau, do đó bạn sẽ cần phải dành chút thời gian để tìm chúng.

Answer 6

Nếu bạn muốn một thuật toán đơn giản sẽ tạo ra một lịch trình mà các đội không chơi với nhau nhiều hơn một lần không khó với các tham số đã cho. Đây là ví dụ cho 10 đội và 5 vòng, giải pháp được hiển thị dưới dạng mảng trong đó nếu giá trị của lịch biểu [i] [j] bằng 0 thì các đội không chơi cùng nhau và nếu đó là số sau đó nó hiển thị trong đó vòng họ chơi với nhau.

1 2 3 4 5 6 7 8 9 10 
1 [0, 5, 0, 4, 0, 3, 0, 2, 0, 1] 
2 [5, 0, 4, 0, 3, 0, 2, 0, 1, 0] 
3 [0, 4, 0, 3, 0, 2, 0, 1, 0, 5] 
4 [4, 0, 3, 0, 2, 0, 1, 0, 5, 0] 
5 [0, 3, 0, 2, 0, 1, 0, 5, 0, 4] 
6 [3, 0, 2, 0, 1, 0, 5, 0, 4, 0] 
7 [0, 2, 0, 1, 0, 5, 0, 4, 0, 3] 
8 [2, 0, 1, 0, 5, 0, 4, 0, 3, 0] 
9 [0, 1, 0, 5, 0, 4, 0, 3, 0, 2] 
10[1, 0, 5, 0, 4, 0, 3, 0, 2, 0] 

Vì vậy, từ bảng này trong vòng đầu tiên các đội bóng (1, 10), (2, 9), (3, 8), (4, 7), (5, 6) chơi, trong lần thứ hai quanh đội (1, 8), (2, 7), (3, 6) ... vv

Để sản xuất bảng này các thuật toán được khá tầm thường, đây là một số mã python:

#!/bin/env python 

def simpleNRooks(size, rounds, schedule): 
    ''' Place n rooks on board so that they don't hit each other in each round, 
     nor reuse the spots from previous rounds ''' 
    for i in range(size): 
     for j in range(rounds): 
      if size-j*2-i-1 < 0: 
       schedule[i][2*size-j*2-i-1] = j + 1 
      else: 
       schedule[i][size-j*2-i-1] = j + 1 

# parameters 
teams = 10 
matches = 5 

# prepare the schedule, 0's designate free space 
schedule = [[0 for i in range(teams)] for j in range(teams)] 

simpleNRooks(teams, matches, schedule) 

print 'Final schedule' 
for i in range(teams): 
    print schedule[i] 

Nếu bạn muốn lấy cấu trúc dữ liệu khác (ví dụ danh sách các cặp theo vòng), bạn có thể sử dụng nguyên tắc tương tự, nhưng thay đổi các vòng lặp.

Answer 7

Tôi đang thêm một câu trả lời riêng biệt với các ràng buộc mới, vì tôi nghĩ rằng nó rõ ràng hơn là thêm vào câu trả lời cũ của tôi.

1. Chia 30 đội vào 5 nhóm mỗi người trong số 6 đội: A B C D E

2. Trong giai đoạn đầu tiên nhóm A và B chơi.

3. Sau đó, C & D, E & A, B & C, D & E, cho 4 phân đoạn mười lăm phút tiếp theo.

Vì vậy, vào cuối 5 * 15 phút: Mỗi đội đã chơi hai lần, với ít nhất một khoảng thời gian nghỉ giữa các lượt đi.

Có 20 tiết và mọi người đã chơi 8 lần.

Việc cho phép một nhóm ở nhóm B, ví dụ, chơi với 8 đội khác từ 17 đội khác trong nhóm A, B & C.

Ví dụ chơi Một đội chống lại các đội B phù hợp, sau đó, đội B so với các đội C phù hợp, sau đó đảo ngược danh sách, sau đó trong nhóm, sau đó MOD 2, MOD 3 giữa các nhóm và trong nhóm.

Điều đó chỉ để giảm thiểu thời gian đi lại và đảm bảo mọi đội chơi mọi loại trò chơi. Nhưng giải quyết điều đó cho một nhóm, và bạn có thể áp dụng cùng một giải pháp cho tất cả những người khác?