Xếp lịch thi đấu thể thao

1) Bài toán xếp lịch thi đấu thể thao

Bài toán đặt ra là xếp lịch thi đấu vòng tròn 1 lượt cho n đấu thủ. Mỗi đấu thủ phải đấu với n-1 đấu thủ còn lại và mỗi đấu thủ chỉ đấu nhiều nhất là 1 trận mỗi ngày. Yêu cầu xếp lịch sao cho số ngày thi đấu là ít nhất.

Dễ dàng thấy rằng tổng số trận đấu là .

Như vậy nếu n chẵn, ta có thể xếp n/2 cặp đấu với nhau mỗi ngày và số ngày thi đấu ít nhất sẽ là n-1 ngày. Ngược lại nếu n lẻ, thì n-1 ta có thể xếp (n-1)/2 trận mỗi ngày và vì vậy chúng ta cần n ngày. Giả sử n = 2k thì n chẵn do đó ta cần ít nhất n – 1 ngày.

2. Giải thuật chia để trị cho bài toán xếp lịch thi đấu

– Giả sử lịch thi đấu là 1 bảng gồm n dòng (tương ứng với n đấu thủ) và n-1 cột (tương ứng với n-1 ngày). Ô (i,j) biểu diễn đấu thủ mà i phải đấu trong ngày j. Nhiệm vụ của chúng ta là lấp đầy các ô này sao cho quy tắc của bài toán.

– Chiến lược chia để trị như sau: thay vì xếp cho n người, ta sẽ xếp cho n/2 người sau đó dựa trên kết của lịch thi đấu của n/2 người ta xếp cho n người. Quá trình phân chia sẽ dừng lại khi ta phải xếp lịch cho 2 đấu thủ. Việc xếp lịch cho 2 đấu thủ rất dễ dàng: ta cho 2 đấu thủ này thi đấu 1 trận trong 1 ngày. Bước khó khăn nhất chính là bước xây dựng lịch cho 4, 8, 16, … đấu thủ từ lịch thi đấu của 2 đấu thủ.

 

3) Xây dựng lịch thi đấu

Lịch thi đấu của 2 người sẽ là bảng gồm 2 dòng và 1 cột: ô(1,1) = 2 (người 1 đấu với người 2 trong ngày 1) và ô(2,1) = 1 (người 2 đấu với người 1 trong ngày 1).

Lịch thi đấu của 4 người là bảng gồm 4 dòng và 3 cột. Lịch thi đấu của người 1 và người 2 trong ngày 1 là lịch thi đấu của 2 người. Lịch thi đấu của người 3 và người 4 được xây dựng tương tự lịch của người 1 và người 2. Lịch này có được bằng cách cộng lịch thi đấu của người 1 và người 2 với 2. Nghĩa là ô(3,1) = ô(1,1) + 2 = 4 và ô (4,1) = ô(2,1) + 2 = 3. Hai cột còn lại của bảng được lấp đầy theo quy tắt: lấy góc trên bên trái (tính luôn phần chỉ số dòng) lấp đầy góc dưới bên phải và lấy góc dưới bên trái lấp đầy góc trên bên phải.

Lịch thi đấu cho 8 đấu thủ cũng được xếp theo quy tắc tương tự: lấy lịch thi đấu của 4 đấu thủ lấp vào góc trên bên trái. Cộng thêm 8/2 = 4 vào các ô của góc trên bên trái để có góc dưới bên trái. Lấy góc trên bên trái lấp đầy góc dưới phải. Lấy góc dưới trái lấp đầy góc trên phải.

4 Replies to “Xếp lịch thi đấu thể thao”

    1. Giống Mergesort.
      Chia đôi ra, xếp cho 2, 4, 8.. người.
      Điểm chính là gộp kết quả xếp cho 2 người để mở rộng lên 4 người, 4 lên 8, …
      Độ phức tạp mình nghĩ cũng trong khoảng: nlog(n),
      Phương trình đệ qui của nó có thể như sau:
      T(n) = T(n/2) + T(n/2) +…. (mình cũng chưa biết là nó tốn bao nhiêu phép tính để thực hiện việc gộp các kết quả từ 2 – 4, 4 – 8,…)
      Ý tưởng sơ khởi là vậy. Chúc bạn vui!

      Like

Kita welcomes your comments...

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s