Re: [問題] 大地排關問題
看板Prob_Solve (計算數學 Problem Solving)作者tkcn (sayuan)時間10年前 (2014/03/02 15:04)推噓3(3推 0噓 4→)留言7則, 4人參與討論串3/5 (看更多)
整理一下目前我取得的資訊，雖然說實在還蠻有限的。
首先我認為這個問題應該早就有相關的研究，
所以打算先找相關的文獻，但無奈找不到正確的關鍵字，所以沒進展。
ps. 『求關鍵字！』
後來，想說先從類似的問題開始找起，
發現 Round-robin tournament (循環賽) 其實蠻像的，
一樣是 n 個隊伍兩兩交手，且交手過得隊伍不得再次交手。
但差別在於，Round-robin torunament 的每一場都是相同的競賽，
並沒有像是大地遊戲有不同關卡的區分。
單純只是要排 Round-robin tournament 的話基本上都有解，
但要把每一場對戰對應到大地遊戲的關卡時，
就會發現一支隊伍參與同一個關卡不只一次的狀況。
在大地遊戲中，相較於同一個關卡玩兩次，
遇到相同對手兩次其實不是什麼太大不了的事，
所以我想從這個方向下手其實不太適合。
----
接著想說寫程式來跑跑看，看能看能不能得出什麼規律。
若狀況是 "n 關 m 小隊" 的話，
假設每個小隊每回合都必須參與，且玩遍所有關卡，
並且任意兩個小隊不會重複交手的情況下，不難發現：
1. 小隊數 m 必為偶數 (否則每回合都有小隊無法配對)
2. n*2 >= m (否則場地不足所有小隊參賽)
3. n < m (否則關卡比其他小隊數目還多)
於是就設計了一個跟原 po 概念一致的 DFS，
然後跑出了以下結果：
*03/03 上午 update 1*
---
下方表格有誤，因為 7 關 8 小隊已確認有解。
目前猜測應該是我不應該事先決定好休關的位置。
本來以為休關的位置無所謂，
因為可以用交換 row 或 column 任意變換，
但實際上卻不是如此。
今晚會 update 重跑的結果。
---
*03/03 22:50 update 2*
---
晚上依照前面的說法，拿掉事先決定好休關位置不會有問題的假設。
code 實在很難改，我改了一個多小時才完成...
改完之後試著跑了一下 "6 關 8 隊"，程式居然跟我說有解...
我想這應該是程式有 bug 吧，但仔細驗證了一遍，這組解居然是合法的!
實在太讓人震驚了!!! XD
| | A | B | C | D | E | F |
|---------|-----|-----|-----|-----|-----|-----|
| Round 1 | x | x | 0,1 | 2,3 | 4,5 | 6,7 |
| Round 2 | x | x | 2,4 | 0,6 | 1,7 | 3,5 |
| Round 3 | 0,2 | 1,3 | 5,6 | 4,7 | x | x |
| Round 4 | 1,4 | 0,5 | 3,7 | x | 2,6 | x |
| Round 5 | 3,6 | 2,7 | x | 1,5 | x | 0,4 |
| Round 6 | 5,7 | 4,6 | x | x | 0,3 | 1,2 |
原來關鍵是，有兩關要在相同的兩個回合休關!!
順便更新一下表格，但七關以上的我的程式跑不完..
| n\m | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 |
|-----|---|---|---|---|----|----|----|----|
| 1 | o | | | | | | | |
| 2 | | x | | | | | | |
| 3 | | x | o | | | | | |
| 4 | | | o | o | | | | |
| 5 | | | x | x | o | | | |
| 6 | | | | o | o | o | | |
ps. 跟原先表格的差異只有 n=6, m=8 不同
---
留空的部份表示沒有滿足前提，
而 o, x 當然就是表示有解、無解。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.34.7.189
推
03/02 19:45, , 1F
03/02 19:45, 1F
當然有，DFS 跑的內容基本上就是在填 qaz00123 文末的表格。
※ 編輯: tkcn 來自: 114.34.7.189 (03/02 20:06)
推
03/02 20:52, , 2F
03/02 20:52, 2F
→
03/02 20:54, , 3F
03/02 20:54, 3F
→
03/02 20:55, , 4F
03/02 20:55, 4F
→
03/02 22:30, , 5F
03/02 22:30, 5F
內容 update，目前的表格是錯誤的。
※ 編輯: tkcn 來自: 114.34.7.189 (03/03 10:31)
※ 編輯: tkcn 來自: 114.34.7.189 (03/03 23:01)
內容再次 update，六關八隊是有解的!!
※ 編輯: tkcn 來自: 114.34.7.189 (03/03 23:02)
推
03/04 09:24, , 6F
03/04 09:24, 6F
→
03/04 09:29, , 7F
03/04 09:29, 7F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
