2019/05/12
引言
昨天看比赛的时候，看到了各个队伍的对战，这种应用应该是排列组合中的算法，但不是很明确。搜索了一下相关的算法，看到有用分治法的。这里来把这部分的问题来描述一下。
问题分析
问题来源于最近的MSI比赛：
小组赛共计6支队伍，按照双循环赛事，共计比赛5天，
每天打6场，每个队每天打2场，第3天的上半轮（即前三场）完成第一轮循环赛，共计30场比赛。
转化为数学形式：
小组赛共计n支队伍，按照双循环赛事，共计比赛n-1天，每天打n场，每个队伍每天打两场，小组赛共计n支队伍，按照双循环赛事，共计比赛n(n-1)场，每支队伍与其他任意一支队伍交手2次，前n(n-1)/2场比赛，完成一轮循坏比赛，即每一只队伍已经与其他任意一支队伍交手1次。
（上面这个说明并不是非常的具体，说明我对这个问题的理解还是不够深入 2019/05/12）
我感觉还有具体的，对于每天的限制什么的，可能要假设比赛多少场什么的。这个应该算是非常经典的排列组合算法吧。
经过思考之后，加入一些限制条件，重新进行问题定义
现在2n支队伍（这里是不考虑队伍为奇数的情况），共计进行2n (2n -1)场比赛；每天至少进行m (m>=1)轮比赛，每轮n场比赛，那么2n * (2n -1) / (nm) = 2(2n - 1) / m，要保证天数是完整的，
同时保证每天的轮数都相等；前面说过的每个队每天要进行m场比赛，而且赛程安排必须保证每天对阵的m个队伍不同
解决思路
（ 这个问题并不是为了提供多好的算法，而是说，我来记录一下我的思路过程 2019/05/12）
- 前面的问题定义已经清楚了，但是因为这个参数并没有确定，所以有时候直接去思考宏观上的通用方式有点麻烦，有很多细节问题需要思考，所以我这里选择将m定义为2轮；因为1轮就不需要考虑梅每天队伍碰撞的问题了。
- 同时因为是双循环赛，分为上半轮循环和下半轮循环，就是说，可以单纯的安排上半场比赛，即1轮循环赛；下半轮的时候，第一小轮不和上班论的最后小轮不比赛碰撞即可（因为m = 2）。
- 再来进行细节讨论，整体上，最终对战的比赛已经确定，每只队伍反正就是对战(n - 1 )场，他们队伍之间匹配问题，已经是固定的，只需要进行排列他们比赛场次的问题即可。
（到这里我感觉到这个m好像也是有一定确定关系的 2019/05/12） - 已经确定m = 2，那么一共就是比赛2 n * ( 2n - 1) / n * m = 2*n - 1 天
- 其实到现在这个情况，貌似很简单了就。我凑够一轮小比赛，共n场，每天两轮，保证每个队伍都对战不同的就可以了；然后先考虑把一场循环弄完，也就是整轮循环就是对战5个不同的队伍。（但我怀疑我是不是想的简单了，因为他们那些什么分治法，好像考虑的更多，我这个还是有点陷入比赛安排的细节了）
思考过程
- 首先，在看到问题之后，根据MSI的比赛情况，写出了自己对赛制的理解；
- 进一步抽象，看到了文章[1]对问题的描述，利用符号来对具体的书进行代表；但是这里有一个问题，他们同时对n这个队伍数也进行了限制，而且，对于比赛天数什么的，我也没有进行假设，所以说，从问题的定义来看，并不完整；
- 思考解决的办法，在看到这个东西的第一想法，是通过搜索的角度来进行解决；但搜索到的一些算法都是跟分治法相关；
- 在仔细观察了问题之后，第二步中需要思考的问题真的很重要，我看了一些单循环的问题，每天就是打一场，这个很直白，但对于这个问题来说，他并没有说明；但我仔细想了想，很多参数，比如说，每天一共比几场，每天每只队伍比几场，都是收到限制的，并不是完全就很随意；如果能把所有的情况都考虑清楚，问题应该是很好回答的。这个过程，就很像很早的时候，以前学习这个相应的公式推理的时候，就最后一个题，那个n的内容，叫什么想不起来了。
- 思考了几个必要的限制条件，两个队伍的比赛，那么队伍总数最好是2*n，这样的话，如果是6支队伍，也就是说一轮比赛下来是3场，这3场情况下就可以保证所有的队伍都参战了。那么我可以给这个赛制安排加上一个限制，每天最起码进行n场比赛，即一轮比赛；那么最后问题的最后结果定义就是：
现在2n支队伍（这里是不考虑队伍为奇数的情况），共计进行2n (2n -1)场比赛；每天至少进行m (m>=1)轮比赛，每轮n场比赛，那么2n * (2n -1) / (nm) = 2(2n - 1) / m，要保证天数是完整的，
同时保证每天的轮数都相等；前面说过的每个队每天要进行m场比赛，而且赛程安排必须保证每天对阵的m个队伍不同（开始解决思路的书写
- 限制m参数实现基本算法（解决思路进行到第5步）
- 查看了很多现有的博客，他们都是针对的单循环赛，利用的都是分治法，我也看不懂，感觉他们写的不具体；但我自己模拟了一下，如果是直接利用他们所说分治法，对于非2^n的情况就无法满足，而且在文章[2]中也找到了同样的说辞，跟我的想的一样，必须进行一些改进，可以在分治法的基础上。
参考文献
[1]分治法：循环赛日程安排问题
[2]循环赛算法分析
网友评论