作者qaz00123 (00123)
看板Prob_Solve
標題[問題] 大地排關問題
時間Fri Feb 28 01:10:43 2014
本身不是資工系但是以前有稍微接觸演算法
最近剛好營隊要排對戰表想說自己來寫寫看
大概規則是 ( 文字表達能力薄弱orz 文末附上對戰表的大概樣子 )
n關 m小隊
總共有n個時段，
每小隊都要玩到每一關，
每個時段中每關要有兩個小隊在同一關
同個時段不可以有小隊同時出現在不同的兩關
每關會休關 n-m/2 個時段
盡量不重複對上之前對過的小隊
目前想法是用DFS慢慢找
每找到一組可行的解就記錄對上重複小隊的次數
然後找最小的。
想問問看有沒有更好的方法？
( 雖然我還在磨DFS要怎麼實做出來orz )
======================================================
對戰表大概是 (假設是六關八小)
時段一 時段二 時段三 時段四 時段五 時段六
第一關 1vs2 休關 休關
第二關 3vs4 休關 休關
第三關 休關 休關
第四關 5vs6 休關 休關
第五關 7vs8 休關 休關
第六關 休關 休關
======================================================
先謝謝大家:D
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.139.22
1F：→ tkcn:想了幾種方法，你提出的這種是我覺得最好的 02/28 23:27
2F：→ tkcn:但我會設計成先找 "容許 0 次重複"，接著 1 次，逐漸放寬 02/28 23:28
3F：→ tkcn:否則我擔心狀態太多 DFS 會跑不完 02/28 23:29
※ 編輯: qaz00123 來自: 59.124.91.73 (03/01 00:34)
4F：→ qaz00123:了解！！！我再來試試看 不過有點好奇其他方法是什麼0.0 03/01 00:35
5F：→ tkcn:例如: 先排好每個小隊每一輪會對到誰，這樣都可以排出不重複 03/01 00:46
6F：→ tkcn:但是這樣最終會造成關卡重複。 03/01 00:47
7F：→ qaz00123:了解了 謝謝~ 03/01 23:19