Hiện tại mình đang tạo lập trình một chương trình nhỏ bằng python. Mình có một giải đấu có n vận động viên và mỗi vận động viên chỉ được phép đấu với k đối thủ khác nhau. Mỗi đối thủ sẽ có điểm số trên bảng xếp hạng. Hãy viết chương trình để sắp xếp lịch thi đấu tối ưu sao cho điểm số trung bình của các đối thủ của 2 vân động viên bất kỳ không quá chênh lệch.
VD: n = 4, k = 2.
Vận động viên thứ nhất đấu với vận động viên thứ 2 thì ở lịch của vận động viên thứ 2 cũng phải có đấu với vận động viên thứ 1.
Mình đã biểu diễn lịch thi đấu dưới dạng một đồ thị.
Như vậy thì bài toàn trở thành có một đồ thị n đỉnh và mỗi đỉnh chỉ có thể được nối với k đỉnh khác phân biệt. Bây giờ cần khởi tạo một đồ thị ban đầu thỏa mãn yêu cầu nêu trên. Sau đó thực hiện một bước chuyển trạng thái để trở thành đồ thị mới. Mình sẽ dùng một hàm lượng giá để đánh giá xem đồ thị này có phải là đồ thị tối ưu mà mình cần hay không. Hàm lượng giá này thực hiện theo yêu cầu là điểm số trung bình của các đối thủ của 2 vân động viên bất kỳ không quá chênh lệch.
Mình chỉ chuyển 2 cạnh của đồ thị để ra trạng thái gần nó nhất.
Nhưng mình không biết cách phải hiện thực nó. Có bạn nào có ý tưởng để hiện thực nó không.
Còn nếu bạn nào có ý tưởng hay hơn phương pháp sử dụng đồ thị thì có thể nêu ra ý tưởng giúp mình.
Mình thực sự rất cảm ơn.
Xây dựng bước chuyển trạng thái trong đồ thị
Như đề bị thiếu dữ kiện
-
Điểm ban đầu của mỗi vận động viên là bao nhiêu?
-
Trong một trận đấu giữa A và B
- Nếu A thắng, A được cộng bao nhiêu điểm? B trừ bao nhiêu điểm?
- Nếu A và B hoà thì mỗi người được cộng bao nhiêu hay giữ nguyên?
- Ví dụ với n = 4 và k = 2 thì input và output là gì?
- Điểm số của các vận động viên được cung cấp từ input nha bạn.
- Ở đây chỉ yêu cầu xếp lịch thi đấu nha bạn. Mình không xét tới trường hợp thắng hay thua vì vậy điểm số của các vận động viên không thay đổi.
- Về input và output:
File input.txt sẽ có nội dung như sau:
3 2
7
18
6
Có nghĩa là n = 3, k = 2. Có 3 vận động viên và điểm xếp hạng lần lượt là 7, 18 và 6.
File output.txt sẽ có nội dung như sau:
2
3
1
3
2
1
- Vận động viên thứ 1 đấu với đối thủ 2 và 3.
- Vận động viên thứ 2 đấu với đối thủ 1 và 3.
- Vận động viên thứ 3 đấu với đối thủ 2 và 1.
Hi vọng là đã đủ dữ kiện cho các bạn.
Giải đấu có 3 người, mỗi người đấu 2 trận thì điểm số có quan trọng nữa đâu. 
Tổng quát hơn, giải đấu có n người, mỗi người đấu n-1 trận thì cứ sắp xếp mỗi người đấu hết tất cả người còn lại, không quan tâm điểm số từng vận động viên nữa:
- Người 1 đấu với 2, 3, 4, …, n
- Người 2 đấu với 1, 3, 4, …, n
- Người k đấu với 1, 2, …, k-1, k+1, …, n
- Người n đấu với 1, 2, …, n-1
Bạn có thể cho ví dụ với n người, mỗi người đấu k trận, với 0 < k < n-1?
Như: n = 6, k = 3; n = 7, k = 4,…
Mình gần hiểu cái đề, nhưng có ví dụ để test thì hay hơn. 
Về hướng giải có thể dùng k-means.
1D k-means. https://cs.au.dk/~larsen/papers/1dkmeans.pdf
Tức là chia n VĐV thành k+1 đoạn (hay k+1 pots) xem từ cuối trang 3 phần Algorithms.
Chắc không được vì sẽ có những nhóm không đủ người đấu.
Mình chỉ nghĩ bài này là dạng bài clustering, còn chia sao chưa tính nữa. K-means là mình đưa đại. Có thể có clustering algorithm khác phù hợp hơn. Nhưng paper mà rog đưa có vẻ hay hay.
Một ý khác, sử dụng graph theory, mình cũng nhớ là có giải thuật chia thành các subgraph sao cho subgraph có nhiều edge nhất (gần giống Kn). Giải thuật dùng để phân nhóm bạn bè trên mạng xã hội.
vd như n = 9, k =4: Điểm số của từng vận động viên lần lượt là 7,18,6,25,12,8,21,14,16
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?