Saya mencoba membuat penjadwal liga olahraga. Saya mengalami kesulitan mengidentifikasi algoritma untuk membantu saya secara efisien mengisi setiap slot.
Contoh data untuk membangun jadwal adalah:
- 10 tim
- Setiap tim bermain satu sama lain 1 kali (diperlukan total 45 pertandingan)
- Setiap tim bermain tidak lebih dari 1 kali per hari
- Dalam pengujian saya, saya menggunakan 9 hari dengan 5 slot per hari.
Combo Table (mengandung 45 combo)
ID
Team1ID
Team2ID
bitDitugaskan
Jadwal Tabel (berisi 45 slot waktu)
scheduleID
homeTeamID
awayTeamID
GameDate
GameTime
Saat ini prosedur saya yang ada mengisi sekitar 90% dari slot sehingga 10% dari slot saya kosong untuk konflik penjadwalan berdasarkan aturan di atas.
Saya mengulangi tabel jadwal saya dalam urutan tanggal / waktu naik.
Slot pertama saya mungkin Sabtu jam 8 pagi.
Saya menanyakan daftar tim yang belum dijadwalkan. Saya kemudian membuat berbagai kemungkinan kombinasi tim-tim itu. Saya kemudian menggunakan array itu untuk menarik 1 catatan acak dari tabel kombinasi saya dari kombinasi yang belum dijadwalkan dan saya menempatkan tim-tim itu pada jadwal. Saya kemudian mengatur kombinasi itu seperti yang digunakan.
Saya mengulangi loop berulang dan setiap kali daftar tim yang tersedia saya semakin kecil dan array saya sebagai hasilnya juga lebih kecil.
Saya menemukan bahwa beberapa hari berjalan dengan baik, dan di hari lain 2 tim terakhir saya yang tersisa sudah bermain di minggu sebelumnya sehingga mereka tidak ditambahkan ke jadwal lagi.
Satu-satunya hal yang saya belum coba adalah "mengatur ulang" hari konflik dan mencobanya lagi untuk melihat apakah saya mendapatkan penempatan yang lebih baik.
Adakah yang punya saran?
sumber
Jawaban:
Inilah algoritma yang saya temukan sendiri. Saya tidak tahu apakah itu sudah ada atau sebenarnya implementasi round robin:
pada dasarnya Anda mulai dengan
dan selalu menjaga 1 di posisi yang sama dan memutar sisanya.
Dengan begitu Anda akan selalu mendapat jadwal pertandingan yang unik. Ini sangat mudah diimplementasikan dan diskalakan dengan sejumlah lawan, bahkan atau tidak merata. Jika Anda memiliki jumlah lawan yang tidak merata, jangan menempatkan tim di posisi 1 dan mereka memiliki putaran bebas.
sumber
Saya pikir Anda melakukannya mundur. Jangan mulai dengan tabel jadwal, mulai dengan tabel / array / apa pun dari semua kombinasi game (45 game). Dari sana, ini adalah proses sederhana untuk menetapkan game ke sehari, berdasarkan pada tim yang hanya bermain sekali sehari. Dan karena pertarungan hanya terjadi sekali (Tim A hanya memainkan Tim B sekali) penjadwalannya mudah karena Anda hanya perlu memastikan bahwa pertarungan belum terjadi (entri-entri itu "unik" seperti itu).
sumber
Saya membuat jadwal 10 tim babak robin tunggal di bawah ini. Butuh waktu sekitar 3 menit.
Info jadwal:
10 tim - 1 round robin (hanya 6 minggu pertama yang ditampilkan)
Tanggal mulai musim 1/6/15 - tanggal akhir 3/5/15
2 pertandingan setiap Selasa, 3 pertandingan setiap Kamis, 5 pertandingan setiap minggu, tanpa tanggal lewati
Kami menggunakan komputer kerangka utama Honeywell yang sudah ketinggalan zaman dan baru berusia di bawah 3 tahun untuk menggabungkan semua ini. Setelah perangkat lunak penjadwalan kami di-debug, dibutuhkan komputer kerangka utama berjam-jam mencari jutaan permutasi & kombinasi untuk menghitung dan membuat pola seimbang untuk 4 hingga 22 tim yang kami cari.
Tidak ada algoritma yang menyelesaikan keseluruhan masalah penjadwalan yang terkait dengan ratusan atau ribuan jenis liga, olahraga, dan situasi potensial. Apa yang kami lakukan untuk menyelesaikan masalah ini adalah mengambil pendekatan berbeda untuk menghitung jadwal. Itu dimulai dengan matematika yang sangat kompleks untuk menentukan pasangan tim round robin yang tepat (pertandingan), tetapi itu baru permulaan. Bagian lain diperlukan untuk membuat jadwal seimbang yang bermanfaat yang dapat diterbitkan dan didistribusikan. Pemain, pelatih, orang tua, dll., Semua harus tahu tidak hanya siapa yang mereka mainkan ; tetapi di mana mereka bermain ; jam berapa mereka bermain ; jika mereka adalah rumah atau pengunjung ; dan untuk banyak liga, sejumlah permainan .
Saya harap ini membantu Anda dan orang lain memahami apa yang perlu kami 3 tahun untuk mencari tahu.
sumber