作者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