单循环赛赛程排布的遍历法生成与评价指标分析.docx

单循环赛赛程排布的遍历法生成与评价指标分析
 
 
Summary：运用针对树形结构以固定搜索路线枚举去穷尽所有可能性方法的“深度优先遍历法”进行单循环赛赛程排布。并且1）提供了一些降低搜索范围的手段;2）提供了几种评价赛程好3。
深度优先遍历法可行性可通过递归执行次数判断。
对于任何大于1的整数n都可以执行该法，有限步内可以完成，仅仅是运行时间的问题。甚至当n较小时，可手动推演。具体方案数与递归次数见表4。
可以看出对称性的实现机制：对比对称性参与与否，方案数呈2[n/2]倍关系。可得知这些数据的内在意义是：步骤①完成的[n/2]场对阵，形成了[n/2]个对称性，对称性会在对阵双方接下来进行的第一场中实现掉。
由图2、图3统计结果，可推测递归数对数与n呈线性关系，算法归为指数算法，进而推测此法运行时间，将时间复杂度过高难以解决的n找出。偶数n>10，奇数n>23则因递归数过多导致运算时间过长，不宜推广。
4 评价指标分析
简化表示如下：
cij——第i队第j个间隔场次数;
[r]、R——“平均相隔场次”及其无分母表示;
f、F——“整个赛程间隔场次的最大偏差”及其无分母表示;
g、G——“选手之间相隔场次的最大偏差”及其无分母表示;
d——“平均相对离差”;
[s]、S——“平均离差”及其无分母表示;
z、Z——“离差的离差”及其无分母表示。
指标的选取：
选取R、F、G、S、Z，用作衡量赛程优劣的依据。
以上指标源于姜启源总结的衡量赛程优劣的指标 [6]：“平均相隔场次”[r]、“平均相对离差”d、“整个赛程间隔场次的最大偏差”f 、“球队之间相隔场次的最大偏差”g。本文也沿用这幾个指标，作为判断依据。
本文关注点还有不均匀性的不均匀性：
记表征各参赛体i其各自赛程内不均匀性的值为si，各si间不均匀性的比较，更可体现各参赛体不公平的差异性。为避免开方等非有理运算引出浮点计算与舍入误差，用离差代替方差进行评价。
d与[s]的差距仅在于“相对”二字。概念d是[s]“相对”意义的引申。将整体进行考虑的话，平均离差[s]在表达不公平的普遍性量化意义上更具优势，同时避免了在去分母过程中，测量作为分母的尴尬。
为了不引进浮点数而造成舍入引起的等值误判，保持各指标大小形容赛程优劣的意义，其仅与n和常数相关的分母均可舍去，只保留分子。
得到R、F、G、S、Z五个指标。
在五个指标中，R越大越好。在满足手段1的排法中，F、G越小越好 [8]。S与Z都是越小越好。
这些指标能否同时达到最佳需要用以下过程验证。
n为大于3的奇数时，遍历法获得的这仅有两种的方案，五个指标完全一致，五个指标同时达到极值。这更印证了此两种方案，有着某些意义上的等价性。
n为大于2的偶数时，各裁选手段下全部解可以通过遍历法得到。
表5通过n=4、6、8筛选极值后观测得到，可知指标能否同时达到极优值：
F与R等价（分类讨论可推出F=n2（n-2）/2-R），G包含于F、R，S相拮于其余所有，Z独立于F、R而相拮于G。不能说这些指标没有意义，但其中某些指标取到最优是与其他指标最优不一定甚至一定不兼容的。选何种指标作为判定依据，需要根据具体需要做出抉择。
在实际的应用过程中，往往并不需要所有符合裁选手段的结果。在n越来越大时，